脳log[20250702]

2025年07月02日 (水) [AtCoder] 土曜日に日本最強プログラマー学生選手権～Advance～ -予選- （ABC412）があった。なかったことにしようと思ったけど火曜日に E が解けたので存在を認めてやらないではない。■A 問題 Task Failed Successfully。無加工で使用できる比較対象が同時に与えられる親切さはさすがの A 問題。だけど昔はループが必要なかったらしいです。■B 問題 Precondition。いつものごとく upcase とか uppercase とかガチャガチャやってみて当たりが引けなかったのでリファレンスを調べたら、どうやら大文字小文字を調べるメソッドはないみたいだった。びっくり。制約から特定の１ビットを調べるだけでわかるのは知ってるんだけど、どのビットかは覚えていないし、鼻につく感じもするので、大文字化して元の文字と比較するという馬鹿みたいなやり方でやった。■C 問題 Giant Domino。ドミノ１とドミノ N を抜き出してから他はソートする。貪欲法で必要な限り可能な限り最大のドミノにサイズアップしていく。■D 問題 Make 2-Regular Graph。順列が通る制約。やるだけではあるんだけど、短時間でやりきれなかった。やることは勘違いしていなかった。１個以上の輪っかでできたグラフを作る。輪っかの大きさは３頂点以上である必要がある(多重辺が許されていないので)。このときに輪っかの数が最大でも２個までだということに気がつけなかったのが敗因か。そうでもない。各順列に対してどこで輪っかを作るかというのを DFS で全探索する最初の方針で実装して AC だったのだから。N の階乗(頂点列の並べ替え)に２の N 乗(各頂点で伸ばす/輪になるの２択)を掛けてもまだ間に合う制約だというのも確認していた。D 問題に時間をかけすぎだと判断して途中で E 問題に行く原因になったのは何か。消す辺足す辺の数勘定ができなかった。すごく面倒くさかった。やりたくなかった。それならしかたないね。■E 問題 LCM Sequence。解けるまで２晩かかった。D 問題の AC が終了５分前だったので、当日は終了 30 秒前に未完成のものを提出するしかなかった (#67164359 TLE×19)。コメントにあるように素数判定に時間を使い過ぎている。翌日になって調和級数的な計算量で合成数をはじけば素数判定はいらないなと思って提出したものは WA×5 だった (#67182611)。制約で区間の幅が列挙可能な大きさ(10^7)に制限されている意味はわかっていたつもりだけど、区間の上限が (10^7)^2 だということとその意味に気がついていなかった。十分な大きさの素数までを列挙すれば、１つの素数のべき乗(2,4,8,16……など)とすべての合成数(4,6,8,10,……など)が列挙できて、消去法で区間内に高々１度しか現れない大きな素数も見つけられるんだけど、「十分な大きさ」を決めるのは区間の幅ではなかったのだった。提出 #67224096 (AC)。■F 問題 Socks 4。N すくみ的な状況。手持ちの靴下を C→D(→E)→C と入れ替えて戻すのは必ずどこかで判断ミスをしているので堂堂巡に陥る心配はしないけど、問題設定がすこしでも複雑になると自己ループの除去とかできなくなる。■火曜日……２晩……。６月30日は ABC412 の代わりに消えた？