競プロはじめました

AtCoder で競技プログラミングを始めて，先日青色になったので，慣習に従って（？）振り返り記事を書いてみます．

f:id:ygussany:20201004190446p:plain

きっかけ

特に決定打は無いのですが，GW 明けの休日になんとなく「久しぶりにプログラムでも書くか～」と思い，せっかくなので計算量（実践）の勉強を兼ねることを想定して，AtCoder の門を叩きました．プログラミング経験としては，大昔に遊びで書いていたのと，前前前世ぐらいで少し実験コードを書いたことがある程度で，競プロっぽいものは特に経験が無く初めてでした．

軽い気持ちで始めたのですが，ここまで人生を破壊されハマってしまうとは…… *1

5 月

AtCoder Problems に登録して，とりあえずリハビリということで Training 300 問を解きました．2 週間半ぐらいで終わったので，あまり難易度の変わらない茶・緑 diff の問題を埋め，5 月が終わりました．当時は特に公言せず，潜伏していました．

この期間で印象に残っているのは以下の問題です．

文字列の出現回数を数え，辞書順に出力するだけの問題ですが，始めて 2 日目の自分には解けず，翌日に持ち越し，合計 20 回の提出をしてようやく AC を得ています．この問題で，文字列のハッシュ（ロリハもどき）という概念を会得し，二分ヒープを実装するなど，競プロの洗礼を受けた気持ちになりました．

6 月

水 diff 埋めに移行し，だいたい 1 ヶ月弱で（直近のコンテスト分を除き）完了しました．

水 diff で特に印象に残っているのは以下の問題です．結構手強かったのですが，この問題で某典型テク（ネタバレ回避の気持ち）*2 を会得しました．

また，PAST という検定が無料開放されていたので，これを受け 76 点で中級の称号を得ました．不服だったようです．

すると，opt (@opt_cp) さんから以下の問題を教えていただき，血が滲む思いでなんとか解いたら少しバズりました．

7 月

水 diff まで埋まったので，青 diff を埋めていました．これもだいたい 1 ヶ月で埋まりました．とはいえ，青ぐらいになってくると体感難易度のバラツキ（得意・苦手）が顕著になってきて，たまに当日中に解けないということも出てきました．この頃から，「好き（問題リンク）」「良い問題（問題リンク）」のような，情報量が無（ネタバレ回避の気持ち）のツイートをするようになりました．

技術的には，セグメント木を履修したのが大きかったように思います．色々教えていただいた皆様，ありがとうございました．

8 月

青 diff まで埋まったので，黄 diff を埋めていました．さすがに平均的に難しくなってきて，1 日に 2 ～ 3 問解くのがやっとになってきました．また，日を跨ぐどころか週を跨ぐ問題や，犯罪 AC *3 をしてしまうような問題も現れ，ここから先を自力縛りで進むのはかなり厳しいなという気持ちになってきました．しかし，やはり自力で解けると嬉しいので，とりあえず（犯罪でも）自力 AC するように頑張り続けました．

また，コンテストに出ることを少し考え始めて，練習として直近の ABC などのバチャをやるようになりました．具体的には，ABC162 ～ 177 と，周辺の企業コンテストを，9 月のデビュー戦までにやりました．平均で 2000 ぐらいのパフォーマンスになっているという感覚で，最低は ABC 174 で 1400 弱，最高は東京海上日動で 2800 強（外れ値）という感じです．

他には，yukicoder で opt さんが問題セットを組んだコンテストに参加してみて，こんなに問題作れるのスゲー！と思いました．裏話とか色々はこちらへ．

9 月

引き続き黄 diff を埋め続け，なんとか 9 月中に埋め終わることができました．

ABC178 *4 で (rated) コンテストデビューをし，青パフォで茶色になるというちょっと悔しい結果に終わりました．一応ギリギリ全完できたのですが，E のマンハッタン距離のからくりに気付くのに 40 分以上かかってしまったのが痛かったです．

続く ABC179 では黄パフォを取ることができ，緑を飛ばして入水しました．これは実はかなり大きく，翌日に ACLC 1 があり，そちらの rated 対象が 1200 以上だったので，滑り込みで rated にできました．そして翌日もなんとか黄パフォを取れ，ここでも大きくレートが上がりました．

9 月最後のコンテストは ACLC 2 のはずだったのですが，前日の yukicoder コンテストに爆破されたらしく，ACL Beginner Contest として変更されました．こちらでも黄パフォは取れたのですが，青にはギリギリ届かず，9 月中の青入りはなりませんでした．

他には，opt さんとつる (@theory_and_me) さんと共にチーム KARAOKE_NO_IKITAMI として ACPC day3 に参加し，7 完 20 位という成績を収めることができました．実装をほとんどお任せしてしまったのですが，分担や戦略など，個人戦とは違うおもしろさがあるなあと思いました．

10 月

青になりました！！！！！

おまけ（犯罪 AC 集）

犯罪 AC は結構おもしろいので，いくつか例を挙げてみます．あまり詳細には説明しませんが，ネタバレを強く回避されたい方は読まない方がよいかもしれません．以下に挙げたもの以外にもあったような気がするので，思い出したら追加するかもしれません．*5

AGC035-B  Even Degrees

はじめてのはんざい！は無意識という離れ業でした．適当に向き付けた後，次数の偶奇が合っていない頂点同士を結ぶパスを探索して，それに沿って向き付けを反転するということを繰り返していましたが，明らかに 2 乗時間の解法です．しかし意外と高速に動作して 0.1 sec 程度で通ってしまっていました（提出コード）．99999 頂点のスターなどを入力すると無事 TLE してくれるので，完全な嘘 AC でしたとさ．*6

ARC017-C  無駄なものが嫌いな人

要素数 32 以下のナップサック問題で，ナップサックにちょうど収まる解の数え上げです．ド典型ながら，当時の自分が全く知らないテクニック *7 を要求される問題で，おそらく初めて犯罪 AC をした問題になります．*8 全探索しても 2^32 ≒ 4･10^9 程度なので，適当に枝刈りを入れれば何とかなります．要素を重みの降順に取捨選択することにして，残りの総和が小さすぎたり，残りの最小値が大きすぎたり，残りをどう組み合わせても，適当な素数で割った余り（前計算しておく）を欲しいものに合わせられなかったりする場合に探索を打ち切ることにすると，0.5 sec 以内で通りました（提出コード）．

ABC027-D  ロボット

10^5 で 2 sec なのですが，2 乗時間の愚直な DP を頑張って軽めに書いてみたら 1.6 sec ぐらいで通りました（提出コード）．良い問題だったので，綺麗な解法を自力で思い付けなかったのが悔しく，印象に残っています．

ABC033-D  三角形の分類

2000 で 7 sec なのですが，3 乗時間の自明な解法を頑張って軽めに書いてみたら 6.969 sec で通りました（提出コード）．なお，こちらは犯罪をした後にちゃんと解きました．

ABC163-E  Active Infants

計算量も正当性も保証できないヒューリスティクス（左右への振り分けで大きく差があれば，悪い方は探索しない）を絶妙に調整することで通しました（提出コード）．56, 62 行目に現れる 99/100 という謎の係数を，1 にすると探索精度が下がって WA となり，9/10 にすると探索し過ぎて TLE となるという黒魔術です．この問題はバチャの序盤で当たった問題で，バチャが終わった後も考え続け，2 週間ほど解けなかったので，このような力尽くの AC を得てから解説を読みました．

EDPC-Z  Frog 3

2･10^5 で 2 sec なので，2 乗時間では並大抵の高速化だと厳しそうです．しかし，これもヒューリスティックな枝刈り（基本的にはあまり遠くを見なくてよいはず）を入れた愚直 DP で頑張ると，0.1 sec ぐらいで通りました（提出コード）．EDPC の難易度は W >> X >> Z >> V > (others) だと思っていますが，ちゃんとした解法で自力 AC できなかった唯一の問題が Z で，解説から学ぶことが多かったです．

ABC155-F  Perils in Parallel

10^5 で 2 sec なのですが，解の構築を 2 乗時間かけて 1.6 sec ぐらいで通しました（提出コード）．解の存在判定は 2 乗時間かけずに上手くできて，その解法に拘って二進も三進もいかなくなったので，犯罪 AC して解説を見てしまいました．なお，opt さんのこちらの記事が分かりやすくてオススメです．

ACLBC-F  Heights and Pairs

最近のコンテストの問題です．多項式の掛け算を NTT を用いてやるときに，常に次数が小さい 2 つを選んで併合すれば，全体の計算量が良い感じになります．コンテスト中はそれに気付かず，小さい方から掛けるなどを試して TLE していたのですが，なんと NTT などをせずに愚直に掛け算を繰り返すと，結果の次数が 10^5 の場合でも 1.7 sec ぐらいで通ってしまいました（提出コード）．時間中に試さなかったのが悔やまれます．

AGC037-D  Sorting a Grid

2 部グラフを完全マッチングに分解する問題（ネタバレ回避の気持ち）っぽいな～と思って色々やってみたけど，どうにもうまくいかなかったので，モンテカルロ法で違反度をひたすら下げる（同行の 2 要素を一様乱択し，入れ替えて違反度が上がらないなら入れ替える）というゴリ押しの乱択ヒューリスティクスで通してしまいました（提出コード）．解法の方向性は合っていただけに，正しく完遂できなかったのがとても悔しかったです．

AGC048-B  Bracket Score

2 種類の括弧からなる括弧列をうまく作る問題で，少し考えると 2 乗時間の素朴な DP が見えます．10^5 で 2 sec なので厳しいかと思いきや，上述のロボット同様頑張って軽めに書いてみたら 1.5 sec ぐらいで通りました（提出コード）．初の本番犯罪 AC でした．

*1:ある程度予想していたので，今まで手を出さなかったという節もあります．

*2:伝家の宝刀†平方分割†です．最近も非常にお世話になっています．

*3:正当性が証明できない，あるいは，制限時間内に終わる保証ができない解法で AC を得ること．

*4:178 で稲葉なので，狙っていました．

*5:されないやつ．と思っていたら 1 つ増えました (2020-10-06)．さらに 2 つ増えました (2020-10-20)．また増えました (2021-01-30)．

*6:ただ，初期解を次数の小さい方から上手く作るなどして工夫すれば，落とすのは至難の業な気もします．

*7:所謂半分全探索というやつです．

*8:意識がある中では．