新人競プロerの山田です。
ABCDEの5完、2120位、perf1252、レーティング変動は963→999(+36)でした。
A問題 B問題
うん。（提出時刻はそれぞれ2分47秒、7分23秒 ノーペナ）
C問題
数列の合計をゼロにする問題。難なく考察完了して21時16分48秒にAC。（所要時間9分）
ただツイッターを見ているとここで苦戦した人が意外と多かった。山田は直感的に思いつくことができたけれど、調子の悪いときには思いつかないかもしれない。
直感的に思いつけなかった場合、「上界、下界を考える」というパターンを思い出すことが求められる。でもABCのC問題でそれは厳しい。山田は詰まりそう。脳みそのすぐ出てくる領域にその発想がない。
D問題
ただの重み付き有向グラフ最短距離問題に落とし込む問題。
即実装。Mへの入力を忘れたりして少しバグらせたが難なく直していって、サンプルケースもすべて合って提出した(21:31:54)。しかしなんとここでTLEして1ペナ。
TLEの理由は、ダイクストラ法の実装ミス（確定済み頂点をメモしていなかった）。このしょうもないミスが今回の一番の反省。
ただこのデバッグはすぐに終わって21:34:52 AC。（所要時間18分）
E問題
等比数列の部分列が何個ありますか問題。
考察に時間がかかった。dpなどいろんな解法を考えては捨てていた。
初項と公差をi,jとして全探索する方法を考えたが、制約を見て、実行時間的に不可能であることを知り断念。そこで無駄な探索を減らすためにはどうするか考えることで正攻法にたどり着いた。あるA[i]とA[j]を選んでそれぞれを第1項、第2項とすれば、初項と公差が確定するため、探索すべき初項と公差の組み合わせはA[i]とA[j]の組み合わせの数しかない(N<=80だからめっちゃ少ない)。
自明に間に合わないアホな全探索から正攻法を思いつくこともあるんだな。 初項と公差の全探索という発想を脳内で0秒とかで切り捨てていたら思いつくことができなかった。
固定した後は、dpでどうにかする。（本番中は、dpでどうにかなるか……？ なるよな……？ それ以外に解法思いつかないしって感じだった）
これで実装開始したのが22時ちょい前だったと思う。
第1項第2項を固定した上で、dpは「dp[i][j] = 数列Aのj項目まで考慮したときに、項数iの等比数列が何通りあるか」として実装。
サンプルケースも全部合ってたので22:15:01に提出したがWAとなった。
コードテストで入力をいろいろいじっていって、数列Aを「0 0 0 0 0」としたときに出力がおかしくなった。そこからバグの原因を究明。
バグの原因はただのdpの遷移ミスだった。22:23:44にAC。（所要時間49分）
二次元dpの遷移って頭の中でやるとしんどい。だからといって計算用紙に書くのも時間かかり、リスクリターンが合わない。（サンプルケースでおかしくなった場合は書くけど）