脳log[20250208]

2025年02月08日 (土) [AtCoder] 今日は日本レジストリサービス（JPRS）プログラミングコンテスト2025#1（ABC392）があった。F 問題を６分半で解いても４桁順位だということがつらい。まあ、E 問題に１時間ちかくかけてペナルティも３つ出してはいるんだけど、それでも。■A 問題 Shuffled Equation。permutation でやったけど sort で十分だったらしい。１以上だからそうか。■B 問題 Who is Missing?。1000 以下なのでどうやっても愚直に２乗の計算量でやってもいい。Ruby の Array には集合演算が混じってるので、計算量にこだわらずお手軽にそれで。■C 問題 Bib。ビブってなんだゼッケン的なものかとイメージしていたらゼッケンの文字が目に入ってきた。そうらしい。あるいはよだれかけ(そちらが第一義)。問題文には人 i が存在しているけども、どのゼッケンがどのゼッケンを見ているかをゼッケン順に答えるだけでいいのは素直な設定。それを読み取ってさえ添字を取り違え配列を取り違え解答を４回も５回も書き直して問題を読み直してやっとサンプルが合う。最近タイプが下手だ(タイピングのせいにしています)。母音が転がるし濁点が抜けるしコンマがドットになるしで、P と Q が入れ替わらないはずがない(しかし直そうとして２回以上入れ替えていたのはおかしいよね)。６分かかった。■D 問題 Doubles。(1≦Ki という制約を見て)１面ダイスってどんなんだろう、メンコでも２面あるぞと考えていた(どうでもいい。どうでもいいけど……球かな)。最初の誤った方針。ある数字を出しやすいサイコロの上位２つを選んで確率を求める。最大の確率を出す２つのサイコロを選ぶ。実装を始めてすぐに気がついたけど、これは違う。選んだ２つのサイコロは複数の数字が共通している可能性があり、出目がそのどれであってもいいのだから、出目を決め打った確率を比較してはいけない。サイコロペアごとの数字を比較して最大を求める。演算の節約のために無駄に定数係数をループの外に括りだそうとしてバグらせた。一度素直に式を書いてから括りだしてやっとサンプルが合った。AC まで 10 分。■E 問題 Cables and Servers。グラフ、UnionFind、辺の数は木以上。自己辺なしとは書かれていない。多重辺なしとも書かれていない。できないケースの答え方が書かれていないことに戸惑ったけど、辺の数は足りているのでできないことはなかった。しかし極端なケースでかなり自由につなぎ替える必要があり、また、無駄につなぎ替えることは許されていないので、泥沼にはまりかねない危険を感じた。UnionFind をしながら同一連結成分をつなぐ余剰辺を見つける。余剰辺をつなぐ先が問題。余剰辺を持っていない連結成分につながないといけないのはもちろんだけど、余剰辺を持っている連結成分同士もつながないといけない。しかし A から生える辺で B-C をつなぐような無駄な操作はできないし、すでにつなぎ替えて連結になっている頂点同士をさらにつなぐような無駄をすると辺が足りなくなる可能性もある。秩序だって整然と無駄なくやるのは難しい。たとえば次数に注目した処理を一度は書いたのだけど、自己辺がある今回それは意味のある違いを生まない。余剰辺の有無を連結成分ごとに考えるのが正解。３ペナのうち１ペナはデバッグプリントのせいだったけど、２ペナは純粋に見落としと操作ミスによる。最近は E 問題が解けないのが当たり前なので F 問題に浮気したい気持ちを抑えてじっくり解答を読み直して見落としを見つけた。頭から読み直すことで思考の流れをなぞることになるのだけど、２度目は知識があるのと手を動かしてもいないので細部に注意を向ける余裕がある。１時間弱＋３ペナ。■F 問題 Insert。今回も腑抜けた F 問題だったが前回と違い今回は得点できたので許す。操作をするごとに Pi 番目だった数字がどんどん後ろになっていくことが問題になる。愚直に配列を操作すると TLE になる。しかし最後の操作で Pn 番目だった数字は Pn 番目で確定することにすぐに気付く。では P_{n-1} 番目についてはどうだろう。Pn 番目を無視したときの P_{n-1} 番目で確定する。順序付き集合があれば答えられるので BIT を使った。■G 問題 Fine Triplets。シンプルな問題で G 問題で 600 点で３秒制限だから無理な気配しか感じない。しかし順位表を見ると 600 人以上が解いていたので(最終的には 752 人)、見かけ倒しだったのかもしれない。調和級数的な計算量で探索できるかと思ったけど、実行してみると TLE が避けられない感じ。■日記を書いているうちに結果が出た。コンテスト成績証。1113 位で青にちかい水パフォが出てもいいんですかと疑問に思ったけど、過去の成績を見ると 900 から 1000 番台前半はだいたい水パフォなので不思議はなかった。それに順位は参加者の人数にだけ着目しても流動的な指標なので占いの役にしか立たないのだった。■明日は ARC の div.2 がある。配点が 4-6-6-6-8 なので解けても１問だし、今日の成績次第では Rated 参加もできない見込みで参加意欲が限りなくゼロだったけど、とりあえず Rated 参加はできる。600 点問題が３問あれば１つか２つは下振れてるやろの精神でやろうかな。