あるたいるの競プロ手記

競プロについてちまちまと書いています

競プロ公式集（水〜青ver.）

こんにちは、あるたいるです。自分用に、コンテスト中の方針でまずは確認したいことをまとめた公式集を作ります。書いとかないと忘れちゃうので。例題は一応載せていますが、この解法の限りではなく、僕の感性によります。随時更新します。

 

考察全般に関するテクニック

　決め打ち二分探索は「解を決め打ちすると線形で判定できるとき」に使う

　結構忘れがちである。にぶたんしたのに元の問題の貪欲解を探ろうとしちゃうとかしょっちゅうやる（僕だけかも）。あくまで解を決め打ちしたときに何か嬉しいことがないと意味がない。

　例: ABC227-D など

　2変数の操作は座標系に落とし込む

　2つの対象に対して操作を施す時、それぞれをx,yに対応させて平面座標上で考えると嬉しい性質が見えてくることがある。

　例: ABC059-D, ABC205-E など

　区間+反転はbitが入れ替わる地点について考える

　ある区間についてbitを反転するタイプの問題は、s_i と s_{i+1} が異なる地点についてのみ考察すれば十分なことがある。特に、s_i のみ反転させたいとき、 [s_x,s_{i-1}] と [s_x,s_i ] （あるいはその反対）をセットで行えばよい。

　例: ABC083-D, JSC2019qual-C など

　xorに関する等式/不等式を利用して言い換える

　xorはうまく式変形することで別の式に言い換えられる場合がある（逆もまた然り）。 x + y = (x\:xor\:y) + 2(x\:and\:y) は有名。このことから、x\:xor\:y \leq x + y もいえる。また、xorで畳み込みを行うときには掛け算に書き換える必要があるので、x\:xor\:y = x\: \times \sim\! y \: + \sim\! x \times y なども使うことがある(bitwise)。

　例: ABC238-D, ABC098-D, ABC196-F など

　要素の寄与を考える（主客転倒）

　スコアの数え上げでよくやる。特に、経路・順列など、普通に数え上げるのは大変なものに対して適用することが多い。

　例: 

　とりあえずDPできないか考える

　よくわからない問題は大体DPである*1。

　明らかに実装量が多すぎるときはそのまま突破しようとしない

　特にAtCoderでは、基本的にめちゃくちゃな実装問題は出ない*2。実装量が多くなりすぎるときはそのまま実装せずもっとうまい別の方針を考え直した方が、結果的に早く解き切れることが多い。脳死のときはよくわからずに実装を始めてしまうことがあるので注意。

 

DPに関するテクニック

　いったん計算量の悪いDPを考えてみる

　制約的にO(N^2)しか通らないと分かっていても、いったんO(N^3)とかO(N\,2^N)とかのDPで考察する。しばしばそれを高速化することで通せる。

　DPの高速化まとめ
  1. 累積和・セグ木・BITなど
    　O(N^2) を O(N) や O(N\log{N}) に落とすことができる。特に遷移がO(N)のときよく現れる。言わずと知れた高速化。累積和で通るときは大体セグ木でも通る*3ので、セグ木の方が楽チンである。
    例: 
  2. 「実質同じ」要素を考え、いらない情報を削る
    　うまくやると、O(2^N)をO(N)に落とせたりする。例えば、「最後の要素より大きいものの個数」など、いらない情報を削ぎ落とせないか考える。逆に言うと、情報を削ると解けなくなる場合は方針が間違っている可能性が高い。
    　例: ABC232-E など
  3. 貪欲と組み合わせる
    　貪欲（ソート）と組み合わせて最適な遷移を限定することによって、計算量を大きく削減することができることもある。順列数え上げの場合は、小さい数から決めていくのが典型。何をしたらいいか全くわからないときは貪欲の性質が見えていないことがよくある。
    　例: ABC163-E など
  4. インラインDP
    　変更箇所が少なく、多くの要素がただ保存されるだけのとき、 O(N^2) を O(N) に落とすことができる。頭がバグりやすい。更新順序に注意。
    　例: 
  5. 行列累乗
    　操作回数が遷移に影響しないとき、行列累乗で高速化できることがある。
    　例: ABC204-F など
  6. 「最後にまとめて計算」を「逐一計算」にする
    　「dp[i][j] :=  i 番目まででちょうど j 個使って〜」「最終的な答えは\sum_{j} dp[N][j] \times f(j)」みたいな時、採用するたびfを作用させることでうまいこと計算量を落とせるパターンがある。
    　例: ABC169-F など
　「一番若い番号のものはかならず使う」ことにしてダブルカウントを防ぐ

　見出しの通り。

　例: ABC180-F, ABC226-F など

 

グラフに関するテクニック

　「最長路」は木なら直径、DAGならトポソしてDP、そうでないなら-1倍してベルマンフォード

　最長路を求めるのは難しい。ただし、特殊なパターンがある。グラフが木ならばBFSを2回で直径（辺素な最長路）が求められる（最終手段としては、全方位木DPによる脳死解法も検討すべき）。DAGならばトポロジカルソートをすることによってDPができる。どちらにも当てはまらないが、O(NM) が許されるとき、辺の重みを-1倍することでベルマンフォード法を用いた最短路問題に帰着できる。

　例: 

　移動に制限がある最短路問題は頂点倍加

　移動になんらかの制約があったり、愚直に辺を貼ると辺数が多くなり過ぎてしまう場合、頂点数を増やして移動に対応させたり、「移動中」に対応するグラフを考えて元のグラフと接続することで高々定数倍に落とせることがある。

　例: ABC132-E, ZONe2021-E など

　木の2頂点間パスに対する操作は根を使って分解

　木の2頂点 i-j を結ぶパスに対して何らかのクエリ（特に偶奇性に関係するもの・xorとか）を作用させるとき、root-i と root-j に対する操作として分けて考えても同値となることがある。ちなみに、これは区間に関するクエリにも同じことが言える（0-i と 0-jに分解できる）。

　例: ABC201-E, AGC014-B など

 

整数問題に関するテクニック

　Nを整数に分割すると、その値は O(√N) 種類 / 途中から主客転倒

　正の整数 N に対し、x = \lfloor N/i \rfloor の値はO(\sqrt N) 種類ほどしかなく、しかも \sqrt N \lt i \leq N でその値は1 \leq x \lt \sqrt N を連続的にとる。そのため、\sqrt Nの前後で主客転倒してまとめて計算をするとうまくいくことがある。

　例: ABC230-E, ABC132-F など

 

幾何問題に関するテクニック

　極端な場所だけ調べる

　実数座標系の平面には調べるべき場所が多すぎるので、極端なパターンだけ考えることで全探索が可能になることがある。

　例: ABC151-F, ABC157-F など

　点の集合は重心を追う

　点集合を回転させたり平行移動させたりする問題に対しては、重心の移動を追ってあげるのが有効な場合がある。

　例: ABC207-D など

 

ゲーム系問題に関するテクニック

　終状態を考える

　「終わるときは必ず〜になる」という性質があり、操作によって1段階ずつ終状態に近づくとき、始状態から一発で判定できる。

　例: ABC048-D など

　交互なら基本的に先手の方が強い

　それはそう。初手で全部決まる出オチみたいな問題も結構ある。逆に、不利な方が勝つための戦略を考えると正解に近づくことがある。

　例: ARC131-C, ARC105-D など

 

構築系問題に関するテクニック

　集め中…

*1:ほんとか？

*2:ほんとか？2

*3:ほんとか？3 少なくとも高速でない言語では偽かも

黄色になりたいんじゃあ

　こんにちは、あるたいるです。

　じつは、7/31のABC212で入青していました。えらい。

f:id:altairrr:20210802164055p:plain

うれしいね

　しかし、今回書きたいのは入青記事ではありません。

　この記事を書いているのは8月の下旬なのですが、8/22現在、なぜか水色になっています。まさに反復横跳び芸人となってしまいました。かなしい…

　さらに、ここのところ、競プロのモチベーションが急速に下がってきています。これはまずいということで、いったんしっかり決意を固める必要があるなあと思い、あくまで自分のためにこの記事（もとい日記）を書くことにしました。

何を目指すのか

　正直、今までは「たのしくやれればそれでいいな〜」と思っていました（入水記事にもそう書いたし）。しかし、最近競プロが前ほど楽しく感じられなくなりました。これがモチベ減衰の最たる原因なのですが、なぜかと考えてみると、成長が無くなってきているんですね。競プロを始めてすぐの頃は、初見のアルゴリズムがたくさんあるとか、地の数学力で問題が解けるとか、そこまで時間をかけずとも成長を感じることができました。最近はなかなかそうもいかなくなってきて、惰性では楽しくないゾーンに到達してしまいました。そろそろ、強くなりたい。強くならなければ楽しめない。そういうフェーズにたどり着いたのだと思います。

　強くなる上では、やっぱり入黄が目標になるでしょう。もし今後も続けるなら、100回目のコンテストまでに入黄（現在74回）したいところではあります（キリもいいし）。もちろん、また競プロを楽しめるようになれば続けない理由はありませんが、そのためにはそれなりに時間を割かなければならないということです。

 

やめたら？このゲーム

f:id:altairrr:20210823000611j:plain

　

　せやな〜〜〜〜〜〜〜〜〜。ほんとですわ。じゃあやめて何をするんだと言われると困りますが、なんか別の趣味を探しても良い頃かもしれないとは思います。ただ、知らないことも当然たくさんあるし、演習もたりてないしで、もしかしたらまだ強くなれるかもしれない、俺はまだ本気出してないだけ、と考えている自分がいるので、もうちょっとだけ頑張ってみたいと思っています。どこかで見切りをつけねばならない、それならば一旦ちゃんとした努力をしようじゃないかと。そして、このままなんとな〜くコンテストに出続けてもしょうがないので、どこかでけじめをつけようと思います。

 

じゃあ何をするのか

　ここが一番問題で、何をすれば良いのかあんまりわかっていません。有識者の方々、どうやって黄色になったのか教えてください。とりあえず、

・こどふぉの Edu/Div.2 いっぱいばちゃ走る

・ABC全部埋める

・ARC/AGC 600点以下埋める

・作問する

・蟻本読破する

くらいは思いついています。特に蟻本はそろそろ完璧に打倒しなければいけないな〜という気がしています。（そもそも知らないかも、という発想が考察を邪魔するので）

　ただ、こいつらって結構しんどいと思うので、9月いっぱいを一旦の目処としようと思います。伸びとモチベを見て、今後の進退を判断します。（レートも伸びると理想だけど、そううまくはいかなさそう）

　具体的な計画も立てる必要があると考えています。まあそれは後々ということにして、今日は寝ましょうかね（今日の朝10時の飛行機で東京に帰らねばならないのだ）。ここまで書いたんだから、競プロやめる覚悟をもって精進してください、頼むぞ俺。それじゃあ、次は入黄記事で会いましょ〜〜

ABC - D/E/F を埋めていく記事

こんにちは、あるたいるです。

現在ABCをひたすらに埋めているのですが、その中でも解説ACしてしまったものや、「これは大事だな〜」と思うやつを自分用に書き留めていきたいと思います。

ネタバレには注意！厳密さはないので注意！

 

 

 

ABC140 E - Second Sum

my submission

 

キーワード：「主客の転換」「setの上手な使い方」「大きい方から探索」

　第一印象としては、左側を固定して考える典型が見えたが、ちょっとうまくいかなそうなので、P_i が 答えになるような連続部分列を数え上げることにする。P_i より大きい値をP_i に近い方から左右それぞれ2つ探せばOKだが…　ここまではたどり着いたものの、実装が思いつかず断念。大きい方からsetに入れつつ探すのね、納得。setのイテレータはインクリメント・デクリメントができるので、そいつをうまく使えばかなりあっさり実装できる。0-index なら-2,-1,n,n+1 と番兵をおいてシンプルにできる。

 

ABC155 D - Pairs

my submission

 

キーワード：「K番目の言い換え」「解を決め打って二分探索」「気合の場合分け」

　典型。億マス計算の上位互換バージョン。「小さい方からK番目の数が Xである」を「X 以下の数がK個以上となる最小の X」と言い換えて、X を決め打ちして二分探索すればよい。ただし、正負が入り混じっているので、場合分けが必要で実装が重い。しんどい。

 

ABC172 E - NEQ

my submission

 

キーワード：「対称性」「包除原理」「撹乱順列」

　対称性から、 A = [1,2,3,4, \ldots, N]と決めてよく、この A に対して B の個数を数えればよい。ここで、「全ての i に対し、A_i \neq B_i」の余事象「A_i = B_i なる i が存在する」を考える。この数は包除原理で求めることができる。「少なくともk種類のi が存在し、A_i = B_i」であるものの個数を f_k とすれば、これは計算で出すことができ、k の偶奇によって足し引きすれば、求める数列の個数となる。

f:id:altairrr:20210611143226j:plain

N=3,M=4 のときのメモ書き

　ちなみに、N=M のときの  A = [1,2,3,4, \ldots, N] に対するBのことを撹乱順列と呼ぶらしく、この問題は撹乱順列の個数を求める問題の拡張バージョンということができる。

 

ABC162 E - Sum of gcd of Tuples (Hard)

my submission

 

キーワード：「主客の転換」「約数系包除」「大きい方から探索」「調和級数」

　数列自体を考えるのはあまりに多すぎて厳しいので、答えが X となるような数列を数え上げる。このとき、O(1) で求まるのは「答えが X の倍数となる数列の個数」であるので、これから「答えがちょうど 2X, 3X, \ldots\ となる数列の個数」を引けば、「答えがちょうど X となる数列の個数」となる（これを約数系包除というらしい）。大きい方から計算していけば、X について考えるときには、X + 1 以上の数に対する答えがすでに求まっている。それぞれの X に対し、引く数は O( \frac{N}{X}) 程度になるので、調和級数の和より O(N \log N) となる。

 

ABC146 E - Rem of Sum is Num

my submission

 

キーワード：「indexと和の関係」「累積和」「区間の左側を固定する」

　いつもこういう系の問題をなんとなくで解いてしまっている（手で書いて試して無理やり合わせている）ので、式変形でちゃんと導けるようにしたい。この問題の場合は、累積和を取った数列を S とすると、「(S_j - S_i) \% K = j - i」となるが、これを変形すると「 (S_j - j) \% K = (S_i - i) \% K かつ j - i \lt K」となって、各S_i に対し、mapを用いてO(\log N)で求められるようになる。ABC166-E はこの問題の下位互換だが、これとほとんど同じ式変形がEditorialに乗っていたので、覚えていなかったのは反省。 

 

ABC132 E - Hopscotch Addict

my submission

 

キーワード：「頂点倍加」「Dijkstra(BFS)に帰着」

　ぱっと見強連結成分分解かなと思い、SCCあんまりよく知らないんだよな〜と言いながら解答を見たら、全然違くてびっくりした。天才解法か？と思ったけれどどうやらかなり典型っぽい。頂点倍加というよりは、状態を持つDPなんかに近い感じがする。頂点数が3倍のBFSをするだけに帰着できる。

 

ABC128 E - Roadwork

my submission

 

キーワード：「イベントソート」「座圧してデータ構造パンチ」

　ある時間に出発する人がぶつかりうる道路工事とその時間区間を管理して、時刻D_i における最小の要素を取り出してやればいい。ここでよくわからなくなったが、こういう「区間とその値がいくつも与えられたうえで、ある地点の値に関する何かを求めるクエリを処理する」みたいなときはイベントソートというのが典型らしい。 [S_i,t_i) なる区間に対して X_i という値が与えられたとき、これを「追加イベント(S_i,1,X_i) 」と 「削除イベント (T_i,-1,X_i) 」に分解して記録し、ソートしてクエリごとに前からmapに追加・削除してから、mapの最小値を出力すれば良い。

　また、出てくる座標を全部座圧して遅延セグ木で殴ることもできると書いてあった。たしかに。実装でバグらせる気しかしないが…

 

ABC127 E - Cell Distance

my submission

 

キーワード：「要素の寄与を考える」「主客の転換」「マンハッタン距離はXY独立」

　「A全体に対するBの総和」に対しては、特定の要素を固定した上で、その要素が総和に与える寄与を考えるのが典型らしい。今回は特定の2点を考えて、これが全部で何回カウントされるかを考える。これは、NM-2 マスの中から K-2 マスを選ぶ通り数に等しく、\tbinom{NM-2}{K-2} となる。このことから、この問題を「全ての点対に対するマンハッタン距離の総和を求める」という問題に帰着できた。このままでは O((NM)^2) だが、マンハッタン距離はXYを独立に考えても良いことから、主客を逆転して、「X方向の距離がiで、Y方向の距離がjであるものの個数を数え上げる」と考えると、O(NM) に落とすことができる。

 

ABC205 E - White and Black Balls

my submission

 

キーワード：「数え上げを経路数に落とし込む」「カタラン数」「鏡像」

　コンテスト中は包除とかを頑張って考えていたが頭がパンクした。カタラン数の概念は知っていたものの、そもそも数え上げをグリッドの経路数に落とし込むという発想がなかった。グリッドに落とし込むと跨げない直線 l が現れるので、l を跨いでしまうものを引けば良い。l を跨ぐことは、l を+1だけ上側に平行移動した直線 l' を踏むことと同じ。ある経路が初めて l' を踏んだら、l' に対してその前の経路の鏡像をとると、l を跨ぐ全ての経路が点 (-K-1,K+1) を始点とすることがわかるので、そいつらを全体から引いてやれば良い。「カタラン数を知っていますか？」というよりは、「カタラン数の導出を知っていますか？」である。

 

ABC163 E - Active Infants

my submission

 

キーワード：「greedyからDPへ」

　むずかしい… 最初はフローかと思ったけれど明らかに制約が大きくて間に合わない。そこでまず Greedy な方針を考える。ぱっと見大きい方から振り分ければいいように思えるが、それだとうまくいかない。しかし、「頂点を2つの集合 S,T に振り分けて、その中で A_i が大きくなる順に両端から配置する」ようにすれば正しくなる。そうなったら、DPに落とし込むことができて、dp[i][j] := 「大きい方から i 個使って、そのうち j 個を左端に寄せた時の最大値」としてやればOK。このテーブルを思いつくのが結構しんどそうではある。

 

HHKB2020 D - Squares

my submission

 

キーワード：「余事象」「長方形の重なり判定」

　しんどい数え上げ。まず、重ならないやつを数えるより重なるやつを数えた方が良さそうなのは比較的すぐ見える。ここから、片方の正方形を固定して考えようとしたが、これはかなりの泥沼。長方形が重なっている条件は『「縦の辺が共通部分を持つ」かつ「横の辺が共通部分を持つ」』であるので、縦横分けて考えてOKだということに気付くのがポイント。こうすることで、1次元上で重なる2線分の数え上げに帰着できる。これはゴリゴリ場合わけをしても数えられそうだが、もう一度余事象に登場してもらって、重ならない2線分を数え上げるのが簡潔。

 

ABC197 F - Construct a Palindrome

my submission

 

キーワード：「回文は両側から見る」「操作に対応するグラフを考える」「Dijkstraに帰着」

　前と後ろの両方から辿るのが良さそうというのはすぐに思いついたが、ここで行き詰まった。典型テクとして、「操作に対応するグラフを再構築する」というものがある（頂点倍加の発展系）。今回は(前,後ろ)の状態を頂点として、遷移可能かどうかで辺を張れば良い。あとは頂点(1,N) からDijkstraして、(v,v) あるいは (u,w)（u-w間には辺が存在する）までの距離を調べればOK。

 

ABC206 F - Interval Game 2

my submission

 

キーワード：「盤面を分割する」「Grundy数」「区間DP」

　不偏ゲームなので、Grundy数が使えそう。Grundy数は盤面に振り分けられるので、順当に考えると盤面は 2^{100} 通りある。しかし、ある操作を行うと盤面が右と左に分かれるので、もとの盤面のGrundy数 =「右のGrundy数」xor「左のGrundy数」で表される。したがって、dp[left][right] :=「区間 [left,right) におけるGrundy数」とすれば、区間DPができる。

AGC047 A - Integer Product 解いてみた

こんにちは、あるたいるです。

AGC047 の日本語解説がまだ出ていないことと、自分とおなじ考え方をしている人が少なそうだったので、初めて解説記事を書いてみます。正直、エレガントではないですが（main関数が80行くらいある…）、非常に気持ちよく解けたので自慢させてください。かなり素直な発想が多いので、腑に落ちやすいと思います。

atcoder.jp

 

問題概要

N 個の実数A_1, \ldots ,A_nが与えられる。積が整数になる2数のペアの個数は？

制約

2\leq N\leq 200000

0\lt A_i \lt 10^4

A_iは小数部の桁数が9以下

考えたこと

まず、小数のままではいろいろとマズそうなので、文字列として受け取って何かするはず。10^9 倍すれば整数になるが、この数は最大で 10^{13} くらいになるから、2数の積を考えるとオーバーフローするのでなんだかやな感じ。そうすると、分母が 10^9 である分数で表すしかない。けれど、これなら「2数の積が整数」を簡単に表現できる。

分数は全て既約分数にする（ただし分母が1のときは残す）。分母と分子のGCDで割ってやれば良い。その上で、\frac{b}{a} \times \frac{d}{c} が整数になる必要十分条件を考えると、a と b、c と d が互いに素であることから、「 a が d の約数かつ c が b の約数」であることはすぐにわかる。

そうすると、分子の約数を列挙したいと思うのが自然な発想。しかし、分子は最大で 10^{13} である。普通に列挙すればA_i の1要素につき \sqrt{10^{13}} となり、到底間に合わない。どうしよう？

ここで、これらの分数の分母は、もともと 10^9 であったことに注目しよう。すると、分母の取りうる値はごく少ないことに気づく。すなわち、10^9 の約数である！ 10^9 の約数はたったの 100 個しかないので、 列挙すべき分子の約数もその 100 個の中にあるものだけでいいのである。

それでは、100 個の分母を全探索しよう。ある 10^9 の約数 d について考える。分母が d である分数 X について、X とペアになる可能性があるのはどの分数か？ 当然、列挙した分子の約数の中に d が存在する分数である。この分数は1つとは限らないが、その一つを Y とする。X と Y がペアになるためには、 X の分子の約数の中に、Y の分母が含まれていれば良い。同じ分母を持つ分数について事前に計算をしておけば、複数の X を同時に処理できる。Y は高々 N 個であるので、計算量は O(100 \times N) で抑えられる。

あとはダブルカウントに注意して（d = 1の場合など）処理すれば、答えを導くことができる！ 実際には map などを多用しているので計算量に log がついてしまうが、やろうと思えば map はいらないはず。というかもっと綺麗に書けるだろ…

 

自分の提出

atcoder.jp

 

列挙するのは 10^9 の約数だけでいいことに気づくところが山ですが、「同じものをまとめて考える」というのは二重ループを解消する時にしょっちゅう使われる手法なので、わりと思いつきやすいかなと思います。たのしかった〜！！

 

 

 

AtCoderで水色になりました！

はじめましてこんにちは、あるたいるです。

2021/1/10 の ABC188 でめでたく水色になることができたので、色変記事を書いてみることにしました！

「競技プログラミング始めたばっかりなんだけど、何すればいいの？」という灰Coderさん🐘から「はやく水色になりた〜〜い！！」という緑Coderさん🌿まで、お役に立てれば幸いです（あるいは「水色なんてとうの昔に過ぎ去ったぜ…」というガチプロさんも、暖かい目で読んでくれると嬉しいです）。

 

f:id:altairrr:20210111172543p:plain

入水！！

0. 自己紹介

　所属：東京大学前期教養学部理科二類1年

　競プロ歴：8ヶ月（入水時）

　Twitter：あるたいる（@altair_kyopro）

　AtCoder：altairrr

　Codeforces：altair_codf

 

　プログラミングは中高一切やったことがなく、5月にはじめて竸プロに出会いました。数学はそこまで得意ではありません（東大入試数学4割切り・JMO予選落ち等々…）。パソコンも詳しくありません。

　でもそんなのは関係なくて、楽しければなんでもOKです。ただし、やるからには強くなりたいので、いろいろ頑張ってみたところ、8ヶ月ほどで水色になることができました。うれしいね！！

　この記事が脱初心者の道標になったらいいなあと思い、記事を書いてみます。

 

1. 入水への経緯

  • 竸プロを始める（2020/5/8）
    　4月中頃から、Twitterのタイムラインでみんなやってたので「楽しそうだな〜、でもパソコンよくわかんないしなあ〜」と思って見ていました。しかしある日、ふとコンテストサイトを覗いてみると、環境構築しなくてもできることに気づき、APG4bから始めました。自分の書いたコードが実際に動いて問題を解けるのがめちゃくちゃたのしくて、のめり込んでしまいました。

  • 初めてのコンテストに出る（2020/5/10）
    　初めて出たコンテストは 2020/5/10 の ABC167 でした。「とりあえずおためしで出てみよ〜」と思い、レジりました。このときは "Yes" と "YES" を間違っていることにしばらく気づかず、2ペナ。B問題でも1ペナして、結果2完3ペナ、パフォは84でした。先は長い…

  • 入茶（2020/8/2)
    　2020/8/2 の ABC174 で入茶。個人的にはなかなかいいペースだったと思っています。（が、TLの人の中にはすでに水色とかがいたりして…）11回目のコンテストだったので、ちょうどレート補正が外れたころだったみたいです。

  • 環境構築をする（2020年8月ごろ）
    　夏休みに実家に帰省したときに、パソコンにやたら詳しい弟に環境構築をしてもらいました。（残念ながら自分にはよくわからず…）　しかし、これのおかげでコーディングがかなり速くなりました。

  • 入緑（2020/10/12）
    　2020/10/12 の ARC105 で入緑。夏休みの精進が効いたのか、9.10月で一気にレートを伸ばすことができました。ちょうど20回目のコンテスト！

  • Codeforcesを始める（2020/11/29）
    　AtCoder は週に1.2回しかコンテストがなく、しかも時々参加できないこともあるので、すこし物足りなく感じていました。そこで噂に聞くCodeforcesを初めてみることに。最初の方は面白いようにレートが伸びるので、気分が良かったです。（笑）
    　ちなみにCodeforces は 2020/12/17 に入青し、現在も青です。

  • 入水（2021/1/10）
    　2021/1/10 のABC188 でついに入水しました！年末のうちに入水したかったのですが叶わず、1/9のARC111は大荒れで冷えてしまい、すこし不安もありましたが、しっかり5完して入水することができました。合計で32回目のコンテストでした。

2. ここまで何をしたのか？

  • APG4b
    　個人的にはやはり竸プロするならC++だと思っているのですが、それはAPG4bの影響が大きいです。 竸プロを始めたばかりのころは、これを順番に埋めていきました。とりあえず3章まで頑張って読みましたが、途中途中でかなり難しい内容（参照や再帰関数、構造体など）があり、しんどくなっていました（実際のところほとんど理解できていなかった）。今考えてみると、1章がしっかり読めていたらあとは割と適当でもよかったのかなあと思っています。

  • AtCoder Beginners Selection
    　APG4bを終えた後はこれをやりました。竸プロたのしい！と感じるには最適なセットだと思います。ただし、「白昼夢」とかは相当難しいと思うので、解説をみるか、一旦飛ばしても全然良さそうです。（実際C問題は解説見ました）

  • 過去問埋め
    　結局はこれに尽きます。AtCoder Problemsを使うのがおすすめです。最初はABCのA~Dのうち茶diff以下のものを近い順に片っ端から埋めて行ったのですが、これ以上やるのは無駄だと踏んでABC126まで（ABCが6問になったところ）でやめました。
    　そのあとをAtCoder Problems の List を用いて茶diffと緑diffをdiffが低い順に全埋めしました。自分は変な完璧主義を発揮してUnratedもやりましたが、別にRatedだけでいいと思いますし、なんなら全埋めもしなくていいと思います。ただし、これをやったことにより確実に力がついたとは感じています。
    　その後、その流れのまま水diff埋めに移行し、現在その途中です。入水達成時のAC数は602でした。

    f:id:altairrr:20210111214452p:plain


    　「過去問を埋めるときには、しっかり時間をかけて粘り強く考えるのが大切」という話があります。しかし、茶色・緑色の場合、「そもそもアルゴリズムやデータ構造を知らないので解けようが無い」というパターンがかなり存在するので、個人的には、解説を見るハードルはかなり低くていいのではないかと思っています。
    　また、公式解説は上手くまとまってはいるのですが、「じゃあ実際にどうやって実装すればいいの？」まではフォローしてくれないことも多いです。そういうときはすぐにググりましょう。「ABC180 c」みたいな感じで調べればたくさんヒットします。特にけんちょんさんのブログや記事がとてもわかりやすいので、よくお世話になっております。ありがとうございます🙏　解説放送もおすすめです。

  • Educational DP Contest (A~J)
    　緑後半になってある程度典型がわかってきたところで、さらにDPに特化して詰めたくなったので。ただし、後ろの方は相当難しいという話だったのでとりあえず前半だけ。これも知らないと厳しい問題が多いので、パパッと解説を見ても良いと思います。サーバルさんたちに教えてもらいましょう。

  • Codeforces
    　上でも書きましたが、11月からロシアのコンテストサイト・Codeforcesにも手を出しています。といってもこちらはほぼコンテストに出て復習するだけで、個人的にはAtCoderの練習だと思ってやっています。コンテストの頻度がとても高いのが何より魅力的です。モチベーションのアップにつながりますし、コンテストという形でたくさん経験を積めるのは非常にありがたいです。レートもAtCoderより上がりやすいので、気分が良くなります（逆に言えば下がりやすいということでもありますが）。一つ欠点があるとすれば、コンテストが真夜中なことですかね…　深夜起きるのがつらくない人にはおすすめです。（英語はそこまで難しくないので心配ないと思います。翻訳サイトも使えるし）

  • 環境構築・テンプレート/ライブラリの整備・AtCoder Library の導入
    　最初はコードテストで頑張っていたのですが、ある程度のレベル（茶色以上）になると、やはり環境を整えることは偉大です。特にエディターを整備することは速解きに大きく貢献します。自分はVSCodeを使っているのですが、スニペット（事前に設定しておいた文字を打つと、登録しておいたコードを出してくれる）の存在が大きいです。速くなる上、typoも圧倒的に減ります。僕の場合、弟（高1）がパソコン・プログラミングに関して非常に（異常に？）詳しかったので、彼に任せましたが、この記事を参考にしたそうです。（弟くんは、競プロではなく開発系に興味があるみたいです。すごい）

    　環境構築をしたことで、毎回最初に書くテンプレートを作成することができるようになりました。自分のテンプレートはこんな感じです。

    f:id:altairrr:20210113024119p:plain

    謎の呪文、マクロ、なんでもござれい

    　また、自作のライブラリを作っておくのも大切です。ABCの後半ともなると、基本的な関数等は簡単に取り出せるようにしておくのが不可欠です。内容は、後述の「覚えたテクニック」を読めば大体わかると思います。

  • f:id:altairrr:20210112093356p:plain

    ここからコピペして使います

    　一方で、AtCoder Library (ACL) というものがAtCoder側で用意されています。（水Coder的には）非常に高速ですし、最近のABCではACLを使うことで簡単に解ける問題も出題されています（ABC185-Fなど）。使えるものは使った方がいいと思いますので、がんばって導入しましょう。やってみると意外と簡単で、パソコン音痴でもなんとかなると思います。ただし、ブラックボックスは怖いし応用が効かないので、どういう原理なのかはがんばって理解するようにします。後述しますが、入水にあたってはDSU(UnionFind)とSegtree（とFenwick Tree(BIT)も一応？）だけ把握していればおそらく大丈夫です。また、実用上はnaoya_tさんが作成してくださったクイックリファレンスが非常に便利です。

  • 竸プロの本を読む
    　そんなに熱心にはやってないのですが、いわゆるけんちょん本と蟻本を買いました。けんちょん本はがんばって最後まで読みましたが、蟻本はほとんど辞書のような使い方をしています。入水にあたっては特にけんちょん本がおすすめです。説明が丁寧ですし、初心者に必要なトピックが厳選されている感じがします。あと純粋に面白いです。

  • 精進ツリーを作る
    　月ごとに、解いた問題のコードをを日付・問題タイトル・感想や簡単な解法とともにツイートしてツリーに貼り付けています。

    自分が今月どれくらい精進したかが目に見えてわかるのでモチベーションアップにつながりますし、一言でいいから感想をまとめておくと、似たような問題を見たとき思い出しやすいし探し出しやすいです。ブログに解説記事を書くつもりはないので、これくらいが継続しやすいと思います。ただしTLの人にネタバレすることになるので、フォロワーが増えたら検討すべきかもしれません（杞憂か？）

  • 頼れる強い人・同レベルのライバルとつながる
    　Twitterや大学などのコミュニティを利用して、強い人と繋がりを持つことは重要です。わからないことをツイートしたり質問したりしたときに答えてくれる人がいると、非常にありがたいです。また、「こいつには負けたくないな〜」という相手がいると、精進も捗りますし、モチベーションも上がります。

3. 覚えたテクニック（アルゴリズム・データ構造）

  • 累積和・imos法
    　言わずもがな。かなり初期から必要になります。imos法は茶色レベルらしいですね。以下の記事が参考になります。三度登場けんちょんさん。ありがたい。

  • vector,deque,queue,priority_queue,map
    　この辺は知っているか知らないかがかなり大きい要素です。バケットソートで用いられるバケットの考え方とそれを用いた高速化も勉強しましょう。コンテナについては、APG4bのこのページを参照するといいと思います。

  • sortによる高速化、しゃくとり法による高速化
    　ABC-C/Dで出がちな高速化二大巨塔はこれだと思います。とりあえず一番最初に考えるべきです。

  • 二分探索（lower_bound,upper_bound）
    　いわゆるめぐる式というやつを使うのがいいと思います。lower_boundやupper_boundは便利ですが、普通に二分探索で書いても全く問題ないので、正直なところ、自分はあまり使ったことがありません。むしろ、内部構造を知らずになんとなく使う方が応用が効かず危険です。またもやけんちょんさんの記事を貼ります。

  • 素数判定・約数列挙・素因数分解・ユークリッドの互除法
    　整数系の問題では不可欠なアルゴリズムなので、これらも早いうちに勉強しておくべきだと思います。ここでもけんちょんさんの記事を貼らせて頂きます。

  • modの扱い・繰り返し二乗法・逆元
    　最初の方は「mod 10^9 + 7 で求めてください」にビビってしまうことがあるのですが、体系的に勉強すると、意外と恐れるものではないことがわかります。繰り返し二乗法も、二進数の考え方がわかれば難しくありません。一方で、逆元を理解するためには、Fermatの小定理や拡張ユークリッドの互除法を理解する必要があるので、なかなかレベルが高く骨が折れます。入水にあたってはとりあえずコピペでも問題ないかな、とは思います。もちろん理解するに越したことはないですが、優先度は高くないです。またまたですが、けんちょんさんの記事を貼ります。

  • 二項係数
    　逆元を学んだら、是非とも履修しておきたい内容です。300点問題程度ならパスカルの三角形を用いた実装でも問題ないのですが、問題のレベルが上がると、計算が間に合わなくなるので、逆元の前計算を用いた高速化が必須となります。一つ上に貼った記事内にも記述があります。

  • 座標圧縮
    　入水を目指すレベルだとたまに出てくる程度ですが、基本的な考え方や雛形は知っておいて損はありません。この概念を知らずに問題を解くことも可能だとは思いますが、速解きが重要なABCにおいては、やはりライブラリとして持っておくべきでしょう。

  • 再帰関数
    　とても大事です。下記のDPや探索系アルゴリズムで使用することになります。ただし、一筋縄ではいかないと思います。最初はなんだ簡単じゃないかと思うんですが、いざ問題の中で使おうとすると「？？？？？」となりがちです。APG4bの再帰関数の章を読んだ上で、たくさん問題を解くしかないと思います。

  • 動的計画法（DP）、メモ化再帰
    　入緑・入水で中心となるアルゴリズムの一つ、DPです。様々な形式があり、慣れが必要だと思います。出るたびにきっちりパターンとして覚えていきましょう。上記もしましたが、EDPCはおすすめ。解説記事も多いです。

  • グラフに関わるアルゴリズム（DFS,BFS,Warshall-Floyd,Dijkstra）
    　グラフ、理解するまでは大嫌いだったんですが、今では一番好きなタイプの問題です。「今俺アルゴリズムしてるな〜」ってモロに感じられるのがいいんですよね。迷路探索（グリッドグラフ）は別にライブラリとして持っています。個人的にはDijkstraよりもWarshall-Floydの方が、実装が楽なのも含め優先度が高いと思っています。Warshall-Floydは直感的に分かりにくいと思うので、以下のツイートを参考にどうぞ。

     　また、これはアルゴリズムではないのですが、入力などを全て行ってくれるmake_Graph, make_Tree, make_Cost_Graph という関数をライブラリとして持っています。いちいち書いてると頂点のデクリメントを忘れたりするので、コピペすると安心です。

  • DSU（UnionFind）
    　これは下手するとグラフ探索より先に出てくるかもしれません。ACLにもありますが、非常に重要なデータ構造なので、中身もしっかり履修することをおすすめします。中身はABC157-Dの解説放送が分かりやすいと思います。

  • Segtree
    　こちらも同じくACLですが、割とハイレベルだと思います。知らなくても入水はできそうです。

  • bitset、bit全探索、bit演算
    　bitsetを用いたbit全探索はいまや茶diffとなっています。APG4bにも説明がありますので、そちらを読むといいと思います。bit演算系の問題は、自分の場合慣れるまでは苦手意識が抜けませんでした。まずはxorとかにビビらないことが大切です。「桁ごとに計算する」という意味が徐々にわかり始めると、急に解けるようになったりします。

  • next_permutation、bitDP
    　順列を列挙したいときに用います。前者は非常に重要で、かなり基礎的なレベルとして問われます（入緑には必須）。後者はいわゆる巡回セールスマン問題で用いられます。こちらは少しハイレベルで、入水には必要ないかもしれません。この2つは制約を見た瞬間に思いつけるようにするといいと思います。N = 8 程度なら next_permutation のセンが濃厚です。

4. あるたいるの「おさえておきたい」お気に入り問題　15選

 　「入茶・入緑・入水を目指す上で欠かせない」と僕が思うAtCoderの問題を15問選んでみました。下に行くほど難しくなります（境界は曖昧ですが、一応、入茶・入緑・入水に5個ずつ対応しているつもりです）。個人的にネタバレされるのが嫌なのであえてポイントは書かないでおきますが、どの問題もしっかりと理解すべき問題ばかりです。「精進したいけど時間がないよ〜！」という方、ぜひご活用ください。（最近のコンテストがやたら多いですが、許してください）

5. 意識していること

ここからは、僕が競プロをするときに意識していることをいろいろ書いていきます。

 

　　問題を実際に解いているときに意識していること

  • 実際に手で書いて考える
    　サンプルケースを見つめるだけだとなかなか解法は浮かびません。サンプルケース1なんかは細かく説明されていることが多いので、実際に問題の操作を実行してみるのが大切です。また、自分で例を考えて書いてみるのも助けになることが多いです。自分はiPadを使って「竸プロ考察ノート」を作っています。

  • 一回で完璧に書こうとしない
    　これは個人で流派が分かれるところだと思うのですが、方針が浮かんだら、自分はとりあえず一回書いてみてからバグを消していくようにしています。コーナーケースなども、よほど自明なとき以外、最初は無視して書いていきます。

  • 制約でアルゴリズムを決め打ちしない
    　これは最近気を付けていることなのですが、制約を見た瞬間特定のアルゴリズムを思考から外すのは危険な感じがしています。もちろん制約をヒントにするのは大切ですが、考え方を整理するためにもまずは愚直に考えてみるのもよいと思います。（かといって無理筋に固執するのも良くないですけどね）

  • 全探索できるなら全探索
    　これは入水レベルの問題に対してのみ有効な策かもしれませんが、なによりもまずは全探索を検討すべきです。探索する範囲を絞ったり、うまく式変形をしたりすることでなんとか全探索できないか考えましょう。

　　コンテストに出ているときに意識していること

  • まずはテストケースも含めて問題を最後まで読む
    　A問題でも流さずちゃんと読むべきです。「何を答えれば良いのか」「どういう罠がありそうか」をしっかり捉えましょう。焦ってコーディングして、結果そもそも問われていることが違ったなんてパターンが最悪です（僕はしばしばやりがちです）。

  • 順位表は多少の参考に
    　順位表を見すぎるのは良くないですが、多少の参考にするのはいいと思います。特に注目すべきは現在の順位ではなくACの人数です。難易度の逆転なんかは参考にしても良いかな？という印象があります。もちろん速解きすべきときに見るのはご法度ですが…

  • 目標を立てておく
    　AtCoder Rating Simulatorなどを用いて目標を決めておくのは大切です。その上で大体何完すればよさそうか考えておきましょう。ABCであれば、入茶には3完、入緑には3完速解きか4完、入水には4完速解きか5完くらいが目安になるでしょうか。

　　その他普段意識していること、あるいはメンタル的なこと

  • コンテストは出れるならできるだけ出よう
    　とりあえずコンテストには出る、というのを一つの方針にしていました（20時まで新宿で麻雀して、そのまま近くのスタバでABCに出たりしました）。ただし、無理する必要はないと思っています。この辺りは後述。

  • 上を見過ぎない、つよいひとはつよい。過去の自分と戦おう
    　Twitterをやっていると、あるいは東大の競プロ勢を見ていると、初めて1年もしないうちに黄色になる人とか、当然のようにABC全完する人とか、中学生なのに自分よりずっと上にいる人とか、すごい人がたくさんいます。自己紹介でも書きましたが、僕はさほど数学が得意なわけではないので、どれだけ頑張ってもその域にはいけないかもしれません。だからこそ、いずれ追いつけたらいいな〜くらいに考えて、自分と比べることはあまりしないようにしています。
    　逆に、過去の自分ができなかったことができるようになったとき、知らなかったことを新たに知れたときに喜ぶようにした方がいいかなあと思います。精進も、AtCoder Problemsが緑色に埋まっていくことに達成感を感じられるようになると、しんどくなく続けられると思います。自己肯定感大事。

  • 楽しく競プロしよう
    　これが一番大切なのですが、競プロは楽しくやってなんぼだと思います。僕は幸い競プロつらいな〜と思ったことはまだないのですが、つらくなったらその時はすぐにやめるつもりでいます。（笑）また、「コンテストはできるだけ出よう」と言いましたが、友達との晩ご飯の予定を蹴ってまで出る必要はないかな〜と思いますし、他にもっと楽しいことがあるならそちらを優先すべきだなあと思っています。競プロと関わる方法はコンテストに出ることだけじゃないですし、なんならプログラミングと関わる方法も競プロだけじゃないです。ただし、僕は出るからには強くなった方がもっと楽しいと思うので、精進を続けています。

6. さいごに

　いかがでしたか？（定型文）

　長々と書いてしまいましたが、大概のことは他の方の色変記事にも書いてある気がします。ずいぶん偉そうなことを書いてしまった気もします。書いてて自分が楽しかったので関係ないですけどね。もし、この記事を読んで面白く思ってくれる方が一人でもいれば幸いです。

　次の目標は入青です。競プロはじめて1年で入青できれば上出来だなあと思っています。バチャとかも積極的にやっていきたいですし、他の競プロerさんとの交流もしたいですね。UTPCやICPCにも挑戦したいですし、しばらくは楽しく続けていけそうです。
　AtCoderの運営の方々や、けんちょんさんをはじめとするわかりやすい記事を書いてくださる方々、先生でもありライバルでもあるUTB1のみなさん、いつもアドバイスをくださるTwitterの競プロerのみなさん、環境構築してくれた我が弟、そしてこんな長い記事を読んでくださった方々、いろんな人に感謝しつつこの記事を締めたいと思います。ありがとうございました。