脳log[20250412]

2025年04月12日 (土) [AtCoder] 今日は AtCoder Beginner Contest 401 があった。変な沼にもはまらず実装ミスもせず、かなりの上振れ回だったはずだけど、なんとか提出を間に合わせた F 問題が TLE×5 で無念。■A 問題 Status Code。一番あり得るミスは Success と Failure のスペルミスだと思った。コピペする手間は惜しんだけど提出前に一応凝視しておいた。■B 問題 Unauthorized。ロジックを実装してシミュレートする。素直な問題は好き。変数名について。たとえばよく出てくる 998244353 という数字に対して、最初こそ M (mod) という名前を与えていたけど今は P (prime number) とすることが多い(名前が競合する場合が例外)。この問題では e (error) という変数で答えるべき認証エラーをカウントした。他の人の提出を見ると ans という変数名をよく見かけた。answer の略だと思う。それも意味のある命名だけど、ではなぜ自分がその名前を選ばないかというと、それは役割に基づいた命名であって、対象そのものの性質に基づいてはいないと思うからだ。役割はコンテクストによって変わる。変わらないものに基づいて名前を与えたいと思っている。コンテクストに合わせてそのときその場で一番相応しい名前を与える(与え続ける)べきだという考えもあるかと思う。たとえば関数の中と外で同じ値に対して異なる名前がつけられることが普通にあると思う。どっちがいいかは知らないし、たぶん答えはひとつに決まらない。何よりこんなに小さな問題ではコンテクストはひとつしかなく違いは生じない。だけどひとつの考えに基づいて名前を付けているという話。■C 問題 K-bonacci。直近 K 項と K 項の和を持って N 項目までを計算する。■D 問題 Logical Filling。話を簡単にするために、o の隣は無条件に . に書き換えておいた。DP をするのかな復元するのかなどうやるのかなと最初は考えていたけど、出力が必然の o か . かそれ以外の ? かということで、２通りの可能性があるなら即座に ? が決定するのだった。最終的に見つかった条件は、「? を１つ以上 o に変えるかどうか」「? を最大限 o に変えなければいけないかどうか」「(最大限 ? を o に変えるとして)連続する ? の個数が偶数か奇数か」というものだった。これで T が決まる。方針を定める時間と考えながら実装する時間で 30 分かかった。■E 問題 Reachable Set。不可能なケースがあるのかなとまず考えた。ある。サンプル２がそうなんだけど、頂点５を経由しないと頂点１と２が連結にならないので、k=2,3,4 が -1 (不可) になる。じゃあ使える辺を使ったときに 1-k までが連結かどうかを UnionFind で管理したいね。同時に、使えない辺の先に繋がっている消したい頂点の集合を管理したいね。同時にできる？ できる。14 分かけたので D の半分。■F 問題 Add One Edge 3。直径の候補は木１の直径と、木２の直径と、i-j を結んで新しくできた i-j を通る直径の３種類だと思った。木の直径は DFS ２回で求まる。新しくできる直径は、各頂点について最も遠い頂点がどれだけ遠いかわかっていればわかる。それは全方位木 DP で求まる。２回の DFS を２つの木に対して合計４回やると、２秒を超えてしまって TLE だった。なにかへまをしていて５秒 10 秒かかるようなスクリプトになっているなら惜しくはないけど、制限時間が３秒だったら通っていたというならあまりにも残念。■コンテスト成績証。ぴったりギリギリで青パフォ。973 位だから「３桁順位に入りたいよー」と書いていた前回の雪辱は果たせたけど、最近落ち目なのだから今日くらいはもっと調子に乗らせてほしかった。■■■X で予告されていたけど、955 位 1607 パフォに上方修正されていた。でもなあ、F を通して 1800 パフォが欲しかったなあ。