2022年ちみ競プロまとめ

忙しくて文章を書く暇がない。
お久しぶりです。

今年の自分競プロかんたんまとめです。
レートを見てもらった方がはやそう。

めっっっっちゃ鈍いけど伸びてはいる

ここ4か月。ここだけ見ると成長してないように見える

ここ1年で1320→1429で+109。まあかなりノロノロしていますが、ここ3か月くらいの手ごたえ自体は悪くなく、個人的な実感として下振れる頻度がかなり下がってきたように思えます。これはよいこと。

ただ、黄diffをコンテスト中に倒して上振れ！！できる実感が殆どなく、崖回にぶちあたるとそのまま沈んでいってしまうのが現状、って感じです。これに関しては得意分野を見つけるとかした方が良いのかな～　数学（と英語）が出来なくて大学受験失敗しているくらいなので、数学分野への解像度が低いのは何とかしたいんですが…（国語と物化と社会だけで大学受験受かるわけないだろ！！）。

4月ごろから職場出勤日（定時開始1時間前に出勤して、その1時間でやっている）のあさかつ（バチャ）のほか、水青diffを埋め直す個人バチャなどである程度苦手分野をつぶすことを試みています。最近、コンテスト中の水diff打率はかなり良い感じです。青もたまーに解けるし、コンテスト後のACもそんな時間がかからず（これ通せたじゃん）となることが多いので、青diff打率もこのまま頑張ればもうちょっとは上がるんじゃないかな～とも。伸びは遅いけれど、自分にまだ伸びしろがありそうと思い続けることが大事なので…。

ただ、やっぱり伸びが芳しくないです。かなしい…。

青くらいまでは個々のセンス関係なく行ける領域だとは（今の所）思っているので、諦めずに続けていこうと思います。

ちょいちょいパフォーマンスが低いABC回を自分で振り返ると、だいたい問題文の誤読なんですよね。これ、直すにはどうすればいいんだろう。

原因がわかっているだけまだマシではありますが…。

＿＿＿

3年くらい前、twitterを眺めていてたまたま飛び込んできた記事を見かけて、縁もゆかりもなかった競プロを始めたんですが、まあ周りにやっている人はだれ一人いなかったんですよね～。

そこから（クイズ系の知り合いだった）kysくんと競プロ伝いに再会し、今年は中本會、twitter及びスプラトゥーン伝いで面識を持った競プロの人もそこそこ増えました。有難いことです。競プロはだいたい知り合いの皆さんの方が格上ですが…。

kztasaくんと再会したのもすごいな。彼ととあるテレビ番組（ここでは内緒）で対決したのももう13年前ですよ。時の流れは速いですね。

すぐやめるかも、と思って手を出した途端、（下手だけど大きな）一趣味になってくれた他、また新しい交友関係を見出せるツールにもなってくれたような気がして、この趣味には改めて感謝というきぶんです。それだけに、いつも付き合ってくれている人に、少しでも追い付きたいな、と感じています。

今年は上記のことをよく感じる一年でした。

鬼が笑わない程度に来年のことを書きますと、とにかく青コーダーになるのが目標です。できれば3月までに。

他の趣味である競技クイズの熱がいつ復活して競プロの時間が減っちゃうか分かりませんが（？）、まだまだ頑張っていこうと思いますよ。先日のABCのEをコンテスト後にACしたとき、「これコンテスト中通せて良いでしょ～～」と反省したけど、「ちゃんとAC出来るんだから自信を失う必要はないはずだよな～」と思えました。もう若者とは言えない年ですが、自分の成長をきちんと感じながら、努力できたら最高だなと思います。

年末年始もたぶん精進してそう。

みなさん良いお年をお過ごしください。それでは。

スプラトゥーンのお誘いいつでもお待ちしています！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！

ABC271とARC149の反省

　お久しぶりです。

　相変わらず結構毎日忙しいのですが、競プロは変わらず趣味として続けております。レートはほとんど伸びていませんが…

　また主に自分の整理の為、ということで、時間の許す限り振り返りを文字にしておこうかなと考えたので、久しぶりに復活です。

まずは土曜日のABC271。

ABC271 うーん

66分5完3ペナ。

Cの貪欲の判例が最初思いつかず、投げた後にWAが出て、ドツボにはまる前にDEを通してきた後に、Cに戻って悪戦苦闘した感じです。Fは40分考える時間あったのに通せなかったのは鍛錬不足ですわね。

しかしまあDEを通すのがあっさり行けたこともあり、自分としてはそこそこパフォーマンスが出てほぼhighestに。「もう1問解けたな…」って時が一番悔しいので何とも言えないですが…。

 A - 484558

　16進数に直すだけですが、めんどう。

　pythonだとhex()を使えばいいという説があるのですが、これはこれで大文字変換がいる。'0123456789ABCCDEF'と文字列を書いた方が早かったかも。

 B - Maintain Multiple Sequences 

　上手くリスト内リストへ格納できますか？系統の問題、初めて見たかも。

C - Manga

　ぱっと考えて反例を思いつかず、貪欲を投げちゃいました。

　ソートし忘れで1WA（バカ）、そもそもの嘘解法で1WA、よくわからんミスで1WA。

　結局ダブった巻数をすべて（-1）にして、deque()の末尾に放り込んだ後、左側がとれるなら左の巻数を取って、だめなら右から2冊取る、を繰り返すコードを書いてAC。ここさえすんなりと行けていたなら…。

atcoder.jp

D - Flip and Adjust 

　表裏で2通りあるので、普通の考えれば2の100乗、状態数が必要になるのですが、Sが10000以下という表記があるため、状態数は最悪10000個×100枚分で収まる。

　1枚めくるごとに辞書D[i]=['HTTT']みたいに更新して、使い回しDPのようにコードを書きました。カードの置き方の一例を示せばよいので、辞書の中身の通りは1つあればそれだけしか記録しなくてよいです。文字列の追加は文字列分だけ時間がかかっちゃうので、リストにしてappend→最後に文字列出力という手順を取りました。

atcoder.jp

　TLでは復元が話題になっていましたが、復元…？？（苦手分野）

　あまり復元というのを考えなくてよい方法だったかなとは。

E - Subsequence Path

　2*10**5という制約を見て、UnionFindとかダイクストラかなーと一瞬思いましたが、道が使えるのはEの部分列＝Eiの道のスタートに居る人しか進む権利が無いので、1か所ずつ順番の遷移で済む、ということに他なりません。なので、K回遷移させれば終わりです。

　この都市に至るまでの最短距離を10**10としたあと、最小値を順番に更新すればおしまい。ダイクストラと疑いドツボにはまった人も多いらしかったのですが、自分は２，３分ほどの考察で済んで幸運でした。実装もかなり軽かったですしね。

atcoder.jp

　F - XOR on Grid Path

　結論から言うと、半分全列挙でした。

　N=20なら半分に分割して2**10オーダーにして間に合う、という至極当然の発想ではあるんですが、フォローしていたり同じdiscord鯖に入っている暖色erによるとかなり設定が自明とのことで、いやはや、何も云い訳が出来ないですな。ダーツの例の問題しか問題設定知らなかったんですよね。半分全列挙のことを英語で" Meet in the middle "というらしいのですが、うわなるほどね、と思わされる感じがすごいです。知識不足！

　xor、まだお友達（よそよそしい表現）になっていないので良く忘れがちなのですが、ある数字にxorして0にするには同じ数字をぶつければよいです。従って、スタートから真ん中まで、ゴールしてから真ん中までのxor値が一致すればそれで問題なし。

以下はコンテスト後AC。

atcoder.jp

G,Hは問題未確認。Gは時間をかければ行けそう。

続いてARC149。

考察が得意じゃないのがバレるARCのパフォーマンス歴

ARCは本当に安定していません。緑パフォもまだとりますし、水色を何とか確保していても水下位パフォであることも多く、正直分のいい勝負はさせてもらっている感触はないです。（自分の力不足がもちろん原因ですが…）

当日、10時過ぎからゆる～り3km泳いだ後、買い物に行ったり部屋で作業をしたりして夕方仮眠を取ったのですが、これがまあ最悪の方向に転んでしまいまして、疲れはさほど感じないけど、頭が酸欠の状態に近くどうもこれはまずいのではないか、と夕食を食べながら考えておりました。しかしまあunratedで不参加に出来る選択が、利口だと思えるレートには達していないこともあり、n度目のhighest更新チャレンジと相成りました。果たして結果は＿＿＿（ﾄﾞｺﾄﾞｺﾄﾞｺﾄﾞｺ

ぎりぎりだったが

何と前日のABCと同じパフォで耐えきり、実に半年ぶりのhighest更新です。微々たるものですが、そりゃあ嬉しいものです。参加できてよかった。下手なりに考えた甲斐があったというものです。

A - Repdigit Number

桁の数字1~9と、N桁なのでおおよそ10*Nの計算量。

数が大きすぎるので、逐一modを取っておく、という動作について、自分はかなり早い段階で履修すべき技術（茶くらい？）と認識していたのですが、kysくん「我々はそりゃあ手足のように使えますけど、これ発明しようと思ってもけっこう編み出す無理じゃないですか？」という言葉に「確かにな」と思いました。知ってるか知らないかで緑のdiffが出来たのかな。

自分は1~9のそれぞれで最大桁数だけ記録して、最後にソートでどれが一番大きくなるか判定しています。

atcoder.jp

 B - Two LIS Sum 

Bの設定にとっかかりがなさすぎて、当初Cの問題文を先に読んで10分くらい考えていたのですが、いくらなんでもBの正解者が多すぎる、ということでBにトンボ返り。

で、3例くらい適当に作って紙で実験してみたんですが…ん、これもしかして片方さえ最長に並べれば良くない？と気づく。ここまで15分。

流石に未証明で投げるほどまだ時間は使っていないので少し考えていたのですが、

・Aを1~Nと順番に並べる。この状態からBのLISの長さを増やすために任意の場所2点をswapさせようとするが、swapするとAのLISは少なくとも1減るにもかかわらず、BのLISは増えるかどうかすらわからない

ということに気付きます。

あ、じゃあ片方さえきれいに並べれば最長だ、と自分の中で決まりまして、A,BそれぞれでソートしたもののLISを求めて無事AC。これで目標というかノルマ達成だ～

atcoder.jp

 C - Avoid Prime Sum

 　こういうのって、偶奇を気にしたあと、市松模様に埋めるのが定石じゃない（どこから市松模様そう思ったんだ？）と当初思っていたのですが、それだとN=3の中心のマスが上下左右4つに応対しなければいけません。偶数を足して合成数になる奇数は7（7+2と7+8）しかないので、極力偶数・奇数の組み合わせが少なくなるような勢力図を示す必要がありそうでです。

　Nが偶数の時は真ん中で横に区切ればよいです。

　N=4の場合だったら、

 [1,3,5,7]

 [9,11,13,15]

 [2,4,6,8]

 [10,12,14,16]

 となり、2行目+3行目さえなんとかすればよいです。

自分は[1,3,5,7]と[2,4,6,8]を中心に持ってきて、片方のリストをひっくり返して、合計9になるように配置しました。さすがにN=4で見つかるのだから、Nが大きくなっても合成数に合計がなる組み合わせは1つは見つかるでしょ、と高をくくり、実装。

問題は奇数です。

困ったときはNが小さい時から実験なので、N=3を一先ず埋めてみることに。

3,9,1

5,7,8

4,2,6

が該当します。表の左側は二行目と三行目、右側は一行目と二行目の間に、奇数・偶数の境目があるイメージです。

で、ここからNが奇数の時に全部応用できないかなと考えていたのですが、終了30分前にN=5やN=7のときも1~9の数字を使うんだから、N=3を中央部にカパッとうめれば、わざわざ「7 」みたいな数を見つける必要ないのでは？と気づきます。

流石に偶数+奇数で3の倍数となる数は十分にあるはずですので、Nが奇数の時は

・N=3の結果を真ん中にｽﾞﾄﾞｰﾝする

・偶数+奇数=3の倍数となる（1~9）の入っていない組み合わせを、境界にN-3個入れる

・使った数字を辞書で管理しておいて、残った奇数は上半分、残った偶数は下半分に入れる

で実装。汚いコードになりましたが、無事ACしました。やった～～

↓ほんとうに汚い。

atcoder.jp

本来ならもう30分早くACしても良かった難易度だと振り返って思いますが、今までのARCで負けるたびに反省してきた「手を動かして実験すること」が一応実践できて、それが実を結んだ形になりましたので、手ごたえがしっかり残った感じです、嬉しい。

上記の「7」みたいな数とその相方を見つける段階も、「N=3を埋め込む」を思いついたためその辺をサボれたのもファインプレーだったかなと思います。ぎりぎりだったけど、今まで続けてきたことが生かされているのかもな、と感じる時間でした。

D,E,F。歯が立たず！ｗ

苦しんでいるのだけは伝わるレート

自分は情報系の出身ではないですし、情報系に向いているかと聞かれたらそうではないと自信を持って言えるのですが、競プロは結構いろんなことを経験させてくれる/思い起こさせてくれるなと強く思います。クイズやっているときも同じことを考えていたような気がするな。

もちろん自分がまた失敗する回も来るでしょうし、ひどく落ち込むことも確実にあると思いますが、自分が少しずつ経験値を貯めていけている感覚を大事にしながら青を目指して行ければなと思います。またがんばりますよ。

え？kysくんもう黄色になるの？

AtCoder Beginner Contest 242(ABC242)の反省

　今週の火曜日から右足がおかしいな、と思っていたら傷口からばい菌が入ったらしいです。38度の高熱が突然出た上に、ひざ下から足の甲までが腫れあがってしまい、しばらく歩行困難な状態になってしまいました。やらなければならない仕事は在宅でなんとかこなしていたものの、治る見込みが立たないため病院に駆け込み診断を仰いで休養しております。もう少し悪ければしばらく入院と言われちゃいました。

　とまあしばらく足に触った瞬間「ｷﾞｬｰｰ」とトムばりの叫び声をあげてしまいかねない状態でしたが、痛み自体はかなり治まっております。しかしまあ痛いことには変わりはなく、明日また診断を仰ぎに行く予定です。

　この一週間は目の前の文章を読む集中力さえ維持するのに厳しく、週末のABCはどうしたもんかなと毎晩魘されながら考えていたものですが、参加できなくはなさそう、という判断でratedで突撃することにしました。我ながらアホですね。　

チャンス回ではあったが

　ABCE4完で1402パフォ、この病状を鑑みるとよくもまあ落とさずに済んだとは思いますが、D解けてないのはまずいでしょう。

　Gを見た瞬間にMoを思いつけないのもけっこうまずく、もうちょっと幅広い勉強というか座学をしないと、後ろの問題へのチャンスを手放し続ける気さえしました。

A - T-shirt

　Aにしてはかなり煩雑な部類。けれど、サンプルケースがかなり親切でしたね。

B - Minimize Ordering 

　これの方がA問題に相応しくないですか？

　リストで受け取って、ソートして、joinするだけ。

atcoder.jp

C - 1111gal password

  ついに動的計画法がC問題ですか。DはDPのDと言われて久しい気もするんですが、時代はとにかく突き進んでゆくものです。

　1の位が1,9とそれ以外の遷移を気を付ければ終わり。

atcoder.jp

E - (∀x∀)

 　Dを眺めていて首をひねってしまったのでEをチラ見したところ、0文字目まで同じ、1文字目まで同じ…という回文をカウントする、という桁DPで行けるな、ってところまでは分かったのでDより先に実装。個人的な感想ですが、EはDよりも発想は簡単ですが、実装自体の難易度を含めるとDEはどっこいどっこいかDの方がややムズくらいかな、と感じました。

　ABCZAZという例だったら、

　　（最初から）0文字被っている回文:Aより早い文字は0個→0*26**2

       1文字被っている回文:Bより早い文字は1個→1*26**1（AABBAAとか）

       2文字被っている回文:Cより早い文字は2個→2*26**0（ABBBBAとか）

       最後にABCCBAが該当するかをチェックすればよいです。

　　でも実装に時間がかかったのは大いに反省するべき。

　　26の累乗に関してはどうせ何度も使うので、先に累乗modを計算しておきましょう。

atcoder.jp

D - ABC Transform

　10**18の文字が見えたのでlogベースの計算量になるはず。例を書き出してみて、ぐっと睨めば…と思っていたのですが、時間内に思いつけませんでした。

　再帰で計算するにしても、tは1ずつしか減らず、10**18の計算量が間に合わない→一足飛びに計算できないかと悩んでしまったのが良くなかったですね。tは1しか減らなくてもｋは半々に減っていき、0になった瞬間にO(1)で出せる、という事実に気付くことが出来れば…。

　ひとまず療養して、ある程度体を動かせる状態にまで回復させるところから。

　今回のFもGもまあ題材としては手が届きそうな問題なので、時間を見つけて自分の中でしっかり落とし込んで解説ACしたい。

AtCoder Regular Contest 136(ARC136)の反省

わかりやすく狼狽している

　お久しぶりです。クイズの方の例会も無事終わったため（boothで記録集を見かけた際にはよろしくお願いします？）、徐々に競プロに時間を割き戻している（割き戻す:という動詞はない）感じです。その間コンテストにはもちろん出ていたんですが、まあ分かりやすくドツボでしたね。考察スピードも実装の素早さ/バグらせなさもステータスとしてはかなり弱いので、愚直にインプットして経験を積むしか手立てが無いことは既に分かり切っているのですが、かなり厳しい期間でした。

　青パフォ（以上）取らないとあまり喜べない身分だとは思いますが、少しだけレートを戻したこともあり今回のARCの反省です。

A - A ↔ BB

　見た瞬間に貪欲だな、とわかるんですが、文字列Sの中のAをBBに変換した後、BBを取り出す作業でバグらせそうな悪い予感がした。（2文字分見ないといけないことが実装のストレスになりそうだった）

　少し時間がかかってもいいやと思い直し、「AをBBに変換」「文字列・連続個数に変換」「そのままつなげる」の3ステップに丁寧に分け実装しました。

atcoder.jp

B - Triple Shift

　不変量（みたいなもの）があるはずなので、そこを見つけることからスタートしました。

　例えば（1,2,3）をswapしたら（3,1,2）及び（2,3,1）となるのですが、転倒数に注目するとそれぞれ0,2,2となります。右端の数字を左端に置く過程で、右端の1つの数字・他の2つの数字の左右関係が真逆になるので、打ち消しあうか+1*2/-1*2になるかで、どうあがいても転倒数の合計のmod2、というか偶奇は変わりません。

　(1,2,3)をswapさせると（3,2,1）には決してなりませんが、転倒数としては0と3で偶奇が異なって無理なのはあってそうだな、となります。

　残りは数字が重複しているパターンの考察です。

　（1,1,2）をswapさせて出来る（2,1,1)、(1,2,1）の転倒数は0,2,1で、偶奇が一致しません。「1が1を飛び越える」というswap作業を経るときは、転倒数の変化がないため、偶奇の調整が可能となるためです。

　あとは、「AとBの構成要素が全部同じか」「重複してないか」「転倒数の偶奇は同じか」を見ればゴールです。実際のコンテスト中の自分は、「右から詰めていけば、最後の左2項目が入れ替わるかどうかまで同じにできる」→「愚直にswapしていけばいいけど、右端から埋めていく際に、該当する数字が2つあったとき枝分かれが増えない？」→「あ、結局どうとでもなるじゃん、しかも転倒数か」の思考をたどったため、「数字の重複パターン」に気付いた形です。転倒数のライブラリ、用意してそうで全然用意しておらず、大昔の借り物をぺたっと貼ってAC。

atcoder.jp

C - Circular Addition

　どういう操作をやるのか整理してから考察を始めます。

　どうやら、連続する長さ（1~N）に+1をしていく作業で、最短何回で建設可能ですか？と言い換えられるらしい。これに気付いたところで60分経過・残り60分。

　どうせ隣同士の最小値か差だろ、と考え（3,1,4,1,5）→（2+3+3+4+2）//2=7までたどり着いたものの、自分で考えていたケース（（2,2,3,3,3）とか）が想定解答に一致せず、ここで止まってしまいました。ここを乗り越えれば優勝でしたね。

　考えるべきだった考察は、隣同士の差の合計をスコアとするとき、(3,1,4,1,5)と(13,11,14,11,15)が等価であるということです。結局max(A)の値はまあ少なくとも必要、という至極当然な部分に迫ることが出来ずジ・エンドという感じでした。うーん黄色diffだったのか。実に惜しいことをしたぜ。。

D - Without Carry

　6次元DPか～書きたくねえな～と思ってたらゼータ変換の典型らしい。

　勉強しなきゃ～

C通せば優勝だった

　A早解き回とも言えなくもないですが、Bをロジカルに解けて非常にすっきりしました。C通せばまあ1850くらいのパフォにはなっていたらしい。ARCは夢がありますね。

　今年中に青コーダーになりたい！というお気持ちがまた強くなってきましたので、また自分なりに経験を積み重ねていければと思います。

AtCoder Regular Contest 132(ARC132)の反省

　のわ～という結果。しばらく競技クイズの例会の問題準備で忙しくしているんですが、精進をさぼる理由にはならないんだよなあ（しょぼん）

A - Permutation Grid

　一意に定まる～の部分を見落とし、複数種類出来るものだと勘違いしたので、慎重に考察しすぎてしまった。問題文の見落とし・誤読をする癖は直さないと本当にまずいですね。そのまま工夫せずに1WA。

B - Shift and Reverse

　ひっくり返す動作が最大2回であることに気付くのが遅い～

　久々に自分で狼狽している様子が丸わかりでした。

atcoder.j

C - Almost SortedはDPだろうな～と思いきや、ずらしていくDPか～

立式できなかったので修行あるのみですね

　年末年始、クイズの方で結構忙しいのですが、青を目指して青黄の高diffを一発通せるようになりたいところ。がんばりましょう～

AtCoder Beginner Contest 233(ABC233)の反省文

ABC233の反省をします。

　1137位。パフォは1358でレートは微増でした。3WA無くして15分早かったらパフォ1500くらいは出るはずなので、早解き回として青は取れたなーという気分です。

　ちなみにVScodeはまだ慣れていないので、コードテストでベタ打ちしています。は？

 A - 10yen Stamp

　A問題にしてはまだ難しい部類な気がする。

　(10-1)を事前に足せば終わり。

B - A Reverse

　Aとどっちが難しいのかわからん。

　そのままひっくり返す。

C - Product 

　「袋に入っているボールの個数の総積は $10^5$ を超えない」で一瞬手が止まったけれど、結局全探索気味でも間に合う部類っていう意味だった。

　DPチックに辞書を作って終わり。

　バグを取るのに時間を要したのがダメでしたね。5分で解けたい。

D - Count Interval

　部分列なので累積和取るのは自明に近い。

　累積和の値を辞書に入れつつ、自分より左に該当する数字があるかどうか見て足して行けば終わり。

　Submission #28127354 - AtCoder Beginner Contest 233

E - Σ[k=0..10^100]floor(X／10^k)

結局この図が全てだと思う

1,2,2,5の合計15の一の位と、answerの一番下の一の位は同じ

あとは合計の十の位（以降）を足して下から決めれば終わり…のはずなのだが、

直に計算しちゃて1WA、s=s+'r'みたいなのをO(1)と間違って覚えている癖があって1WA、繰り上がりを忘れて1WAと3回余分なロスを食らっています。ﾊｽﾞｶｼｰ

F - Swap and Sort

　ソートだしまずはUnionFindでセットを見つける…ところまでは自明なのだが、グループを作成したらしたで、どの順序で動かせば最短手（にしないと、上限を超える可能性がまあある）になるのか見当が付かず終わってしまった。葉から確定すればいいんですね。

　Gは再帰でやる奴だな～と思ったけど、分割基準に確信が持てず見送り。

　全体的には早解き青確保ｹﾞｰの回だったので喪失感はまありますが、緑diffとはいえ考察を自分としては早めにできたことは良かったかなと思います。レート落とさなかったしね。

　明日のARC、得点配分が400-400-600-…なのでWA無しでまず2問片付けるところからですね。頑張りまーす。

前置き

　競プロについて長めの文章を書くときの置き場を設けることにしました。続けるかもしれないし、続かないかもしれない。

　自分のスペックとしては、私立大学（薬学）→大学院→社会人という経歴をたどってきました。大学受験数学も大学数学もぜんぜんできませんし、通った大学の学部も情報系ではないです(仕事も情報系ではないです）。2年前にふと思い立ち競プロを始め、今はこんな感じ。

「精進量とレートが比例する」という説をあまり信じていない

ぐへー

青diff埋めがひとまずの目標　年内は厳しそう。

  他の趣味として、競技クイズ（12年くらい続いている）と、字を書いたり字を読むこと（古い文章が好き）、スポーツ観戦（ほぼすべてのスポーツを見る）、水泳（やる）とかありますが、基本的にここでは触れません。