AtCoder Beginner Contest 199 反省
実は先週の最強コン、それに続くARCについての記事を書いていない。忙しかったので仕方がない。軽く先週のおさらいをしておくと、「最強コンで黄パフォ黄色昇格→ARCで水パフォで-50くらいして青入り」
結果を鑑みて
1500(1) 66:52
298位となった。普段のABCでこの順位だと冷えかねないが、どうやら今日は参加人数が多かったようだ。今回のセットは典型力と実装力を問う問題が多かった。実生活の心配事を引きずって考察が鈍る傾向があるが、今回はウォームアップと睡眠（昼寝もあわせて13時間寝てる......）の甲斐あって冷えずには済んだ。
A - Square Inequality
どこかで見たような問題文だが、整数値の判定なのでふつうにやればよい。サンプル一通り試しても1分かからなかった。
B - Intersection
これも見てすぐ解法はわかった。
軽実装なので解いてすぐ順位表を見たが、特に危ない順位にはなっていなかった。
C - IPFL
問題文を読んで、これもすぐにわかったがflipが奇数回行われたときと偶数回行われたときで場合わけする必要があることが予期されて、少し実装したくなさがあった。そういうわけで少し実装が楽になる気付きポイントがないか少し考えたが、何も思いつかないので実装し始めた。実装していくと、flip奇数回のときにA, Bの値を書き換えることにしておけばそれ以降の処理は共通なので実装は案外重くならなかった。
最近はシンプルな実装ができるようになっている一方で、泥臭い実装を要することが予期されるとすぐにやる気がなくなることが増えた。よくないなあと思うが、競技との向き合い方自体に問題がある気がしている。
D - RGB Coloring 2
制約を見て、計算量の評価がすぐにできた。雑にやれば状態数が3^Nあるが、連結成分ごとに一頂点決め打てば2^Nに落ちる。
ところが、これを実装に落とすのに難儀してしまった。最初は色を配分した表を持ちながらDFSしていく方針だったが、これは探索中の頂点が連結成分の末端に達した時にうまく他に遷移できないこと、木ではないのでボトムアップな集計ができないこと（木は二点間のパスが1個だけなので二点間の情報伝播に矛盾が生じないが、閉路があると簡単ではない）から正しく実装できずに時間だけが過ぎ去ってしまった。
順位表を見て、DとEが50人ほど解けている状態だったので仕切り直す意味を込めてEを見に行った。このときにDが200人くらいに解かれていたら冷静な判断ができなくなっていたかもしれない。
Eを解いて戻ってくると、すでに150人程度に解かれていた。最初の方針で1回組み切って出して1ペナした。その後、やや実装は重いが連結成分ごとに頂点の色を決め打ちして正しく塗れているかをチェックする方針にシフトした。最初に取った方針と似てはいるが、DFSの集計に関する弱点がこちらの方針にはないので何とかこれを解くことができた。
最近のD問題にしてはかなり実装が難しい問題だったと思う。
E - Permutation
制約を見て、こんなものはbitDPしかないなと思った。実際、数列を端から順に構築していく場合に保持すべき状態数は2^Nずつで抑えることができる。あとは素直に組めばいいのだが、全状態でM個の制約全部を見ているとO(N^2M2^N)などという計算量（この計算量回文じゃん！）になってしまい、破滅の予感がした。そういうわけで枝刈りをして祈りながら提出をした。この枝刈りに少し時間を取られたが、最悪O((Mcomb(N,N/2)+2^N)N^2)くらいにはなっていたため通すことができた。一応、最悪ケースでコードテストもしておいた。
これを解いた後に気分新たにDを見に行った。
F - Graph Smoothing
難しい。これは本番中に解けなかった。なぜこんなに解かれているのか。
最初はDFSで考えていた。パスをうまく管理できればあとは組み合わせ計算でなんとかなるように見えたため。これは難航したので、別のアイデアがないか少し考えた。
次に出たアイデアが隣接行列のようなものを持っての行列累乗で、思いつきだったが問題の条件にフィットしており、大いに興味をそそられた。そこから先、行列の初期値をあわせるためにガチャガチャと値を変えていたのだが、ついにACできなかった。
行列累乗で考える場合は、「どの部分が何を表しているか」「次状態に遷移する際に、どこから寄与が生じていてどのような遷移式になるか」を意識して特に遷移部分を明確にしなくてはならない。今回は雰囲気で値をガチャガチャやっていてこの二点を疎かにしていたのが敗因となったように思う。
ところで、さっきまでこの問題Graph Somethingだと思っていた。
総括
Dで詰まってEに行った時のムーブは良かったが、もう少し早くDを後回しにしても良かった。また、最近は（といっても今回のと直近のcodeforcesだが）解法の正しい道筋が見えずに嘘解法を出してペナると途端に解法と問題の全体像が見えることが多くなってきた。できればWAとかになる前に気付きを得たいのだが、コンテスト中の冷静さが足りていないのだろうか。
AtCoder Beginner Contest 198 反省
一応、黄色昇格に王手をかける形となった。とはいえ、次は8問制ABCなのでうまく立ち回らないと破滅し再び黄色が遠のいてしまう。
結果を鑑みて
1500(2) 44:33
149位となった。速解き力、数学力、実装力、そして注意力が必要とされる実にやりづらいセットだった。苦手回ではなかったが、どの問題でも嵌って破滅があり得たセットだった。
A - Div
最初、N≦15という制約を見て少し動揺したが、サンプルからN-1をエスパーしてこれに証明を与えてACできた。
B - Palindrome with leading zeros
なぜかわからないが末尾の0を消す方針で回文判定を行なった。しかも回文判定も１文字ずつ。（S==S[: : -1]でいいのに)
結局4分かかって順位表も見てしまって精神が乱れる要因となった。ここらへんのムーブはかなり変だった気がする。
C - Compass Walking
まず、貪欲に近付いてシミュレーションするのは得策ではなさそうに見えた。そうなると数学することになるが、これもよくわからない。第三の選択肢として二分探索を考えたが、これが実にシンプルな解法だったのでこれが答えだと確信した。
WAが返ってきた。順位表を見ると大勢ペナを出していたのでそこまで焦燥を感じずには済んだ。そのため冷静にWAケースの数からコーナーの発見につなげることができた。
この問題はいつぞやのBishopのような雰囲気を感じた。ここで1ペナつけて12分くらいで200位くらいだったと思う。少し安心した。
D - Send More Money
まず、問題を読んで面倒臭そうに思った。leading zeroを許しているのかどうかもわかりづらい。問題の理解におそらく2~5分かかり、理解すると解法はすぐに生えた。permutationsを使うやや面倒な実装問題であることがわかり、順位表を見るとわずかにEのACがDより多く、Eの方が簡単らしいことが意図せずわかってしまったが敢えてそのままDを解きにかかった。
結局、14分程度かけてこれをACした。このとき、実行時間制限が5secであることにACを取ってから気付いた。ジャッジ中はTLEしないか気が気でなかった。4.4secでギリギリ通って安堵したもののもう少し高速な処理が書けたのではないかと少し思った。
この時点で体感時間的には21:50ほどであったが、実際は21:30ほどで、なかなかよく集中できていたと思う。
E - Unique Color
案の定、この問題は見て少し考えたら解法が生える程度の簡単な問題だった。サンプルを眺めていたときに「出力は昇順か、気をつけないと」と思ったのも束の間、実装に入ると全部忘れて出力をソートせずに出して1ペナつけた。これでパフォーマンスが30~40落ちていると思われる。
最初にミスしそうな点に気付いたらコードにコメントしておくことにしよう。この時点ではpredictorの算出では黄色タッチだった。順位もそこまで悪くなく、安心して次の問題を見ることができた。（とはいえ、Fが異常そうなのはAC数から既に察していた。）
F - Cube
これは解けなかった。難問。
ボリアの数え上げ定理に思いを馳せたが、三次元の回転にどう持って来ればいいのかわからなかった。これに関連して、mod 6でうまいこと順列表現してサイコロの同型判定ができないか考えたりもした。
また、サイコロのパターン列挙は6!で進み、これの同型判定ができればあとは組み合わせ論の計算に落ちることを見出したが、最初の同型判定をどうすればうまく進められるのかわからなかった。対称性のある無向グラフについての判定と見て、隣接行列をうまく照らし合わせられないかと思ったが......。また、それができたとしてもその後の計算も特に方法が思いつかなかった。
そんなこんなで、22時くらいには恐らく解けないし、解かなくても大丈夫な問題だなと判断してそこから10分ほどまた考えた後にお風呂に入って完全に撤退した。（とはいえお風呂でもついつい考察してしまうのだけれど）
総括
出だしのムーブが変だったような気がするが、C~Dあたりのムーブはまあ良かったと思う。Eのようなミスは今後しないようにしたい。
AtCoder Regular Contest 116 反省
4完、遅解き...... とはいえ微減少なのでARCとしてうまく立ち回れたほう。
結果を鑑みて
1700(1) 80:27
全体491位、レート-6となった。Dで時間かけ過ぎたとは思うが、その割に減少は優しかった。
A - Odd vs Even
最初は何もわからなかったが、偶奇性はあるなと思って、{2, 2以外の偶数, 奇数}で場合分けした。この時点でサンプルは通るが、さすがに4や6で試してみると答えが異なっており、そこからなんとか解法を思いつくことができた。
4分半かかって、まあそこそこだろうと思ったら600位くらいだった。びっくりした......
B - Products of Min-Max
最初は主客転倒オーラがすごいのでその方針で少し考えた。さすがにminとmaxではうまくいかないから、とりあえずソートすると、区間についてごにょごにょする問題に見えてきた。
あとはいい感じに値を累積しながらmaxかminの値を固定して計算すればいいことに気付いたが、添字ガチャでごちゃごちゃになってしまい、結局11分かかった。
順位表を見て、まあARCだしそうだよねという気持ちになった。ここまでのムーブのせいで焦りが生まれてしまったかどうかはあまり覚えていないが、そこまで精神は乱れていなかったと思う。
ちなみに、ここでmodの取り忘れでペナをつけた。
C - Multiple Sequences
読んですぐ、Mまでの全探索となんかの約数列挙が思い浮かんだ。sieveは整備済みなのでこれを引っ張り出して取りかかった。
解き進めていくと、1~Mの整数の素因数をN個の箱に突っ込んでいってその際の場合の数を数える問題になった。 ここの数式ガチャで手こずり、とんでもないコードを書いてしまった。
16分かかった。
思えば、この時点で何だか脳死コードを書いているし集中力が破滅しかけていた。部屋が少し暑かったせいだと思う。春の訪れだろうか。
D - I Wanna Win The Game
序盤〜中盤はなんだか意識が朦朧としていて、何を考えていたのかまるで覚えていない。20~30分ほどを何だかよくわからない解法に費やして破滅しかけていた。ここで順位表は見ないぞと（精神安定のために）決め込んだのは悪くなかったと思う。
考え方を変え、解法ガチャに再度戻ってくると実に素朴なO(M^2logM)のdpが生えた。いやいや、pypyでこんなの通るわけないだろと思いつつコードテストに放り込むと存外高速で、なんとか通すことができた。
解法ガチャを最初にやるときは紙に解法を書き出しておいていつでも参照できるようにしておくべきかもしれない。
E - Spread of Information
パッと見では木の中心からのdpと二分探索に見えた。これのおかげで意識がはっきりし、以後の考察はいい感じに進めることができた。解けてないけど。
木の中心に情報伝達すると、まず最初のサンプルで落ちる。代わりに、葉からなるべく直接情報伝達する点が少なくなるように配置する方法を思いついた。葉から見るとそれが最適な配置になる上に無駄がないように見えたが、このdpの結果直接伝達する点が0個になってしまう場合や多すぎる場合などに対処する方法が思いつかず、そのままタイムアップとなった。
総括
だんだん気温もあったかくなってきたので、体温調節をしっかりするように気をつけよう。解法ガチャは時間かかりそうな問題(ARCやAGCなら400点~)ならば紙に書くなどしよう。
なんだか終わってみるとどっと疲れた回だった。今これを書くのも結構しんどい。Dで自分が今書いているコードの意味がわかっていないような状態が中盤続いてひどかった。体温の問題なのだとしたら、次回以降対策できると思うのでしっかりやっていきたい。
AtCoder Beginner Contest 197 反省
あたたまれてよかった。UTPCを５時間もやって脳みそ破滅していたかと思いきや、良いウォーミングアップになっていたようだ。
結果を鑑みて
2100(1) 80:38
基本的に考察はすんなりと進む問題セットだった。得意回ということになるわけだが、得意回なら60分以内に全完したかったところ。pythonの定数倍関連での知見が増えたのでよしとする。
A - Rotate
１文字目と末尾を交換する問題だと思っていて少し時間かかった。rotateって書いてあるだろうが。
B - Visibility
こういうグリッド上の上下左右探索がABCで出るのは3回目くらい？B問題としては難しいと思った。読んですぐに解法はわかったが、実装には少し手間取った。5分かけてfor文を4個書いてAC。
C - ORXOR
題意が少し取りづらかったけれど（読解力さん？）制約をみるとbit全探索で、解法はすぐに生えた。仕切りの位置の組み合わせを全探索してAC。5分ほどで終わった。
この時点で順位表を見て、そこまで悪くはなかったので特に焦ることはなかった。
D - Opposite
第一感として、正多角形ならば外心を使うことができることに気付いた。最初は外接円半径を出そうとしたが、よく考えると外心を中心としてp0を回転させるだけなのでwikipediaの回転行列公式をググってなんとかACした。そこまで悩んだ印象はなかったが7分かかった。
ABCで300点以上のO(1)数学が出たのは久しぶりな気がする。これで誤差ゲーだったらブチ切れてAtCoder引退をしていたかもしれない。
この時点では順位もいい感じだったのでいい気分で先に進むことができた。
E - Traveler
パッと見た感じ、色ごとにまとめて色の昇順に見るのが良さそうで、右端行ってから左端行くのと左端行ってから右端行くのでは移動距離が変わる場合があって、これが貪慾性をもたらすように思えたが、よく考えるとこれが次の色に取り掛かる時にも影響を及ぼしているので単純な貪慾ではなさそうだった。無限場合分けかなと思ったが、その色の右端で終わるか左端で終わるのが流石に移動距離的には正しそうなのでこれを持ってdpすることにした。ほぼお気持ち証明だったが、なんと正しかった。
13分ほどでACでき、順位も上々だった。精神的には安定していて、橙パフォあるかも〜とか思っていた。
F - Construct a Palindrome
第一感として、回文なら両側から同時に歩を進めれば良いだろうというアイデアになった。最初、N≦10^5だと思っていたので解法は特に思いつかなかったが、制約のN≦1000を見ると直積グラフを作ってDFSするだけの計算量的余裕があることに気付いた。すぐさまDFSを組み、サンプルをチェックすると正しい答えが得られた。
ここで提出する前に一呼吸おいてN=1000の一直線なグラフについてテストするとなんといつまで経っても処理が終わらず、PyPyでさえN=200で5secかかるなどえらいことになっていた。ここから20分ほどかけて定数倍高速化をして、PyPyでN=200で3secまで縮めたがあまりにも遅くてびっくりした。
最後の希望としてDFSにつかっていたスタックをlistからqueue.Queueに変えた。これをするとなんとN=1000でも0.6secほどのスピードで進んだ。驚きすぎてうっかりテスト用の入力を残したまま提出して1WA、その後ACできた。
listよりqueueモジュールの方が速いという話は聞いていたが、これで橙パフォがおしゃかになったと思うと全完後は辛い気分になった。
ところで、コンテスト終了後に外を走っていた時にふと気付いたことだが、queue.Queueは"FIFOキュー"である。つまるところ、気付かないうちにDFSではなくBFSになっていたことになる。この問題の本質は直積グラフの最短経路問題なので、DFSは不適でBFSを使うべきシーンであった。
なんと、考察の大詰めでしくじっていておまけに運でACしていたということである。この事実に気付いた時、あまりの不甲斐なさに私は膝から崩れ落ちて目の前が真っ暗になってしまった。
総括
queueモジュールについて理解を深める必要があること、直積グラフは想像しづらいので最短経路問題であることにすら気付けなかったことなど色々と課題が見つかった。
コンテストのムーブとしてはA~Eまでは大変良かったと思う。Fは知らない！
AtCoder Beginner Contest 196 反省
つらいね ぐにゃぐにゃになります
結果を鑑みて
1000 15:25
やらかした......という気持ち。青下位パフォ、全体785位、レート-29となった。最近やらかしたABC級4完はCaddiコンで、まあもう4完なんてしないだろ と思ってたらこんなことになってしまった。その時も今回もE: 数学, F: ライブラリ+高度典型といったラインナップだったので、こういうのが苦手なんだなーとはっきりした。
余談だが、CaddiコンのWriterと今回のWriterを見比べてみると......
A - Difference Max
見てすぐ解法はわかったのでその通りにやった。
B - Round Down
Xの上限が10^100とか書いてあってぎょっとしたが、これはよく考えると文字列で受け取って小数点で分割すればいいことにすぐ気付くことができた。いつぞやのABCで出た誤差ゲーでも浮動少数点数をまず文字列で受けるというテクが出たことがあって、そこで破滅したので記憶に残っていた。
C - Doubled
問題文が簡潔なので問題読む前に制約が目に入った。問題文を読むと制約の意味がすぐに理解できた。てきとうに全探索するだけなのですぐに書いて出した。
ところでサンプル2の1333ってなんだろう。
この時点で初めて順位表を見た。そこそこだったので焦らず進むことができた。
D - Hanjo
少し悩まされた。まず、問題文と制約から盤面の全列挙が可能なことに気付いた。これをbitDPで組もうとするのは少し大変で、精神のリソースを消耗することが予想された。そんなわけで少し逡巡して、dfs木の深さが高々8程度に抑えられることから、盤面と１畳の畳を引数に持った再帰的な解法を試みた。
サンプル2で答えが大きくなりすぎて少しびっくりした。重複をうまく除去できていないからこの方法じゃダメなんだ、と思ってコードを消そうとしたが、どういうわけか踏みとどまって順列で割ることを思いつくことができた。ふと思い出した蟻本のボリアの数え上げ定理の記憶が助けてくれた。ありがとう蟻本。
この時点で順位表をみるとかなりいい感じだったのでエンドルフィンの分泌を感じながら次の問題へ進むことができたのだが......
E - Filters
問題を読むと、操作についての前計算を行い、クエリに対して小さい計算量で解答する問題のように見えた。
次のように解法の予想を立てた。
1. maxやminをif文に置き換えて数直線上のイベントソートのようにやる
2. なんかがんばると遅延セグ木に載る
3. 実はmaxもminもまとまっていい感じになる
コンテスト中は特にパッと思いついた2. が光明のように感じられて、大半の時間をmaxの合成写像を考えることに費やした。
1. もそれなりだが、加算操作のせいで前計算が二乗計算量になってしまい、うまくいかなかった。
1. も2. もうまくいかず、すっかり焦ってFを見に行ってあれこれ考えたりした。こういう時、どうやって思考をクリアに戻すのが正しいのだろうか。
最後10分ほどで3. をやけくそになって考えた。実はこれが最も答えに近かったのだが、結局コンテスト中に提出することすらできなかった。
できあがる関数の形に注目する問題はABCでも度々出題されているが、だいたいの場合はそれが単調性と結びついて二分探索やら三分探索につながる問題だが、自分は今までそのような問題に対して「単調性がありそうか」を調べ、その結果として関数の形に気付くことが多かった。maxやminの合成関数の概形が正しく想像できなかったのも無理もなかったかもしれない。ただ、サンプルは明らかに単調だったので嘘でもにぶたんとかしておきたかった......
F - Substring 2
この問題を見たのはEに詰まっていたときで、パッと見てdpや前処理、差分などに思いを馳せた。感覚的には解けなくもなさそうだった。solve probability 30~50%程度の感覚だった。
Binary Trieとの相性が良さそうに見え、それを使った考察に時間を使い、ダメだと思ってEに帰る、といったことを繰り返した。
大局的に見たような定式化ができればこれは解けたかもしれないが、流石にEが通っていないとその余裕はなかったろうと思う。
解説を見て悔しい思いをした。配列同士のなんやかんやを多項式乗算に帰着する問題はyukicoderで一回解いていたのだ。とはいえEが通っていたとしても組み切れていたかはわからないが。
総括
Dまでのムーブは大体よかった。バランスよくいろいろな方面に思考とエスパーを巡らすことができ、それが功を奏した。
Eで1時間強も椅子を温めることになったのはかなり厳しい気持ちになるが、時間配分やレートロスの最小化を考えた際に適切な判断ができていなかったのは問題だと思う。Fはやらずに順位表の動向だけ適宜見てEに取り組むべきだったかもしれない。
一方で、思考に詰まったときにこれを回復する術の習得が必要なことがわかった。試しに、ビハインドな上に思考の詰まった状況になってしまったら外を走ってこようと思う。
また、数学寄りの問題への習熟度の低さが露呈したので（というよりも考察のボトルネックが数学になっている）これもこどふぉなどで頑張って研鑽していきたい。
ちなみに最近すまーとうぉっちを買ったので、コンテスト中身につけていた。
ストレス値はコンテスト中ずっと低い状態で、心拍数がコンテスト開始時102 bpm、徐々に下がって22:00には76 bpm、最後10分は追い込みで103 bpmとなっていた。
80~90 bpm付近の頃は（問題が簡単なのもあるだろうが）エスパーが冴えていた。サンプル数が少ないのでよくわからないが、心拍数はある程度高い方が思考には向いているのだろうか。100 bpmあると流石に思考と脈のリズムが噛み合っていないような感じがした。
ちなみに、平静時は60 bpm程度なので、心拍数の爆上がりする競プロを毎日10時間やる生活などをしているといずれはしぬとおもう。
AtCoder Regular Contest 114 反省
A, Bが明らかにABCのものより難しいのはさておいて、Cを通せなかったのでただの速解き2完になった。
結果を鑑みて
700 25:31
全体547位、レート-16となった。ARCで２完などをやるとだいたい-30くらいは覚悟しなければならないことが多いが、今回はちょっと優しめの減少だった。
A - Not coprime
パッと見でGCD、LCM系の問題に見えたのでLCMをとってみたが普通にサンプルが合わないのでよく見ると昨日見た問題に酷似していた。
恐る恐る提出するとAC 7分弱かかった。
この時点では200位ちょっとくらいだったと思うので、そこまで焦らずに済んだ。
B - Special Subsets
パッと見で特に思いつくものはなかった。
少し考えると、f(a)=b, f(b)=c, f(c)=aみたいに有向閉路になる部分はひとつにまとまることに気付くので、SCCを持ってきた。
そこから、強連結成分分解した有向グラフ上のパスを数える問題だ と解釈したわけだが、これは正しくなかった。入次数をうまく管理しなければならなかったりして複雑な実装になる予感がした。
そんなこんなでここで時間を使ってしまったが、有向閉路の考察に立ち返って、有向閉路の集合になることがTの必要十分条件であることを疑った。この考えは正しかった。正当性を厳密に考えることはできなかったが、辺の本数がN本であることがうまく効いてくれていることを信じて提出するとACした。この問題にはなんと20分近くかけている。たまげた......
順位は微妙になったがCが解けそうな見た目をしていたので取り掛かることにした。
C - Sequence Scores
パッと見で最適な操作はわかった。この段階では種類数がそのまま答えになると思っていた。その線で実装すると値が合わないので、ノートで実際に実験して次の性質を洗い出した。
・種類数がそのままコストにプラスされる
・A[i + 1] > A[i]であるとき、コストに+1
1番目の性質は良いのだが、小さなサンプルばかり考えていたせいで2番目の性質を俯瞰して検証することができなかった。主客転倒でdpを組むと最後のサンプル以外はすべて合っており、ここから1時間ほど考えていたがついに2番目の性質を拡大することはできなかった。
毎回そうだが最後の1,2分は正常に考えるのが難しい。時間がなくなるほど俯瞰してみるのが困難になる。
値・要素数の比較的大きなケースを考えること。愚直実験コードを作ること。などが反省として得られた。
総括
愚直実験コードや大ケースでの実験は問題の考察を進めるうちの早い段階で作っておかないと精神力が足りなくなり、また、「今更作っている余裕があるのか」という逡巡が入ってしまうためミスに繋がりやすいかもしれない。
ただ、問題にどのくらいの時間を割くことになるのか推定するのは難しいので（Cはパッと見た感じうまくいけば30分以内に終わるだろうと踏んでいた）比較的難しい問題に対しての時間感覚を身につけることが必要になってきそう。
パナソニックプログラミングコンテスト(ABC195) 反省
よかったんじゃないかな。うまくキリ番を踏めれば賞金もありうるというところ。
結果を鑑みて
2400 46:58
橙パフォ、全体33位、レート+60とかなり良い成績だった。B問題の凶悪さにもペースを乱されることなく進むことができた。周りもBで詰まっていたので遅れを感じずに済んだのが大きい。
実装の軽い問題が多く、いずれの提出コードも700byteを超えない程度のものであったことも速解きにつながった。
A - Health M Death
パッと見た感じ、ただの倍数判定なのでやるだけだった。46秒で通した。
B - Many Oranges
パッと見た感じ、除算についての問題でO(1)で解けるものだろうと踏んだ。同時に細かな処理（切り捨てとか切り上げとか） が面倒臭く、実装によってはコーナーケースが無限に生じうることを予感した。あとMがキログラム単位でびっくりした。サンプル見て首を傾げていたのだけれど、これに気付くとちょっとだけむっとした。
制約を見ると、全探索が可能そうに見えた。つまり、O(1)を頑張るか全探索するか選べる問題だと理解した。こういうときは経験的に全探索を選ぶのが速さ・正確さ共に安定することを知っていた。そういうわけで全探索路線に切り替えた。
全探索できる項目は少ないので、すぐにオレンジの個数についての全探索が思い浮かんだ。そしてこのときの最適な１個当たりの重さは個数nに対してW/nであることもさっと証明できた。（２つのオレンジの重さをW/nからずらそうとするとW/nであった時より得をすることは絶対にない。）
そういうわけで何とか通せた。解法の逡巡などがあり8分かかった。CかD問題相当に見えた。周りも同じくらい手こずっていたので焦りは感じずに済んだ。
これが初参加のコンテストの人とかってこの問題でどういう気持ちになるんだろう。
C - Comma
パッと見た感じ、O(logN)の解法がぼんやりと浮かんだ。10^3, 10^6, ...といったカンマを打つタイミングの数に注目した。
この第一感は正しく、特に証明はしなかったが適当に式を合わせるとサンプルも合ったので提出した。2分ほどでACできた。Bの方が難しかったなと感じた。この時点ではそこそこ良い順位だったとおもうので（スピードが出ている時は順位表を見る癖がある。精神安定に繋がる。逆の時は逆の作用を持つ。）良いテンポで進んでいたと思う。
D - Shipping Center
パッと見た感じ、制約や入力などからナップザック問題の前計算によってクエリO(1)、あるいは半分全列挙のbitDPなどの解法を連想した。（実態に即してはいない。あくまで「そういう解法があてはまるかもな〜」という予想。）
内容がごちゃごちゃしているように感じて、すべきことや本質などを探るのに時間がかかった。全体感を掴み取るのに5分近く使っていたのではないかと思う。これは、ちゃんと考えればすぐに掴めた本質をエスパーで適当にさらって掴もうとしたために起きたロスだと思う。それでもエスパーをやめてちゃんと考える方にシフトできたのはよかった。
ちゃんと見ると制約や入力はナップザック然としているが問題は全くナップザックではないことに気付いた。それと同時に雑な貪慾法が生えた。O((NM+MlogM)Q)程度の計算量だが、パッと考えたところ計算量には十分な余裕があるように見えた。ソートと貪慾の正当性は感覚で理解していたが最後までナップザックオーラを放つ問題文が怖くて祈りながら提出した。何とかACをとれたのでよかった。
この問題は焦ると解法ガチャをミスったりそれに固執したりして取りこぼしやすいような問題に見えた。パッと見た感じはE問題相当、解くとD問題として妥当な難易度に思えた。
この時点でかなり精神に余裕が生まれた。
E - Lucky 7 Battle
パッと見て、ゲームdpかな という感じだった。
大正解、というかこの形式だともうそれくらいしか疑う方法がないのだが。問題文についてサンプルなどを見て理解しながらコードを組んだ。
ゲームdpは最終局面から遡るのが定番である。S, Xは予めreverseしておいてdpを書いた。ループ中では7*Nの状態を追うことになるが、ゲームdpを書いたのが久しぶりなのがあって、逆再生するような配るdp(つまるところ貰うdp)として組む時に少し遷移を書くのに手間取った。最適戦略の基本に立ち返ることで何とか遷移を決めることができた。
あと、ゲームの始状態は0 mod 7の状態になるわけだが、 これがなんだか自信がなくてこれも祈りながら提出した。間違っていても取り返せるくらいには先行しているし という気持ちがあって思い切って出せた。なんとかACを取れた。この問題には12分近く使った。コードの構築に一番時間がかかった。
F - Coprime Present
パッと見た感じではB-Aについての奇妙な制約が目に止まり、区間篩を連想した。また、なんかすごい方法によるbitDPもどきとか。あとは独立集合の数え上げについてググった。
3~5分のうちにとんでもないひらめきがあった。73以上の倍数が72個の連続する整数に2度以上現れることはないのではないか というものである。このアイデア自体は恐らく何度か目にしたことのあるものである。
この気付きの後は上記の解法を並行して考えつつおはなつみに向かった。リフレッシュは大切で、精神的な余裕は解法を落ち着いて精査する余地をもたらしてくれた。ここで大方の方針は決まり、戻ってくると72以下の素数の個数をググった。
あとはいい感じに進み、ただpypy特有のTLEが怖かったのでインラインにしたりなど適度な定数倍改善を含みつつ提出し、ACを得た。
Bで2ペナくらいしてたら焦りでこの問題は解けなくなっていたと思う。
総括
制約をがっつりと見てそれに即した解法をエスパーしたり、それとは関係ない方向にも考えたり、今回のムーブはバランスが取れていて理想的だった。実生活における心配事は減ってきていて（というか際限なく後回しにしているだけなのだけれど）、それが安定したプレイングの土台になったのかなと思う。
ちなみに、INHOPではないがこの週は乾燥させたホップの株から出したハーブティーを毎日のように飲んでいた。香りは香ばしく精神安定作用があるように感じた。味は......
因果関係はないのかもしれないけれど、ひとつひとつの小さな調整が実を結んでいってくれるといいな。次はどうなるのかな。
