脳log[20240713]

2024年07月13日 (土) [AtCoder] 今日はトヨタ自動車プログラミングコンテスト2024#7（AtCoder Beginner Contest 362）があった。特に書くことはないけども参加記録として。自分のすべての提出。■A 問題「Buy a Pen」。３通りなのでどうとでも書きます。■B 問題「Right Triangle」。２乗のまま整数のまま三平方の定理で判定します。■C 問題「Sum = 0」。最初はすべて L に寄せて和の最低値を求めます。あとは和が負である限り、各組 R-L を上限として右に寄せていきます。■D 問題「Shortest Path 3」。辺だけでなく頂点にも重みがあって何かが変わるかなと考えたけど、普通に普通のダイクストラ法のままだった。■E 問題「Count Arithmetic Subsequences」。N の制約が 80 以下と非常に小さい。これだけ小さいと O(N) と O(logN) の差よりも定数倍の違いの方が大きくなりがち。80 の３乗が大した大きさでないことを確認して愚直３重ループを書いたら TLE が出てびっくりした。３重ループと書いたけど実は３つ目のループは再帰関数の中に隠れている。それって３重にとどまらないのでは？ やばいのは公差が０のケースなのでそれだけ別で数えて AC。■F 問題「Perfect Matching on a Tree」。マッチングとかフローとか辺被覆とか点被覆とかはわかりません。「最大重み最大マッチング」てなんだったんでしょうか。まんまと「知らないキーワード、怖い」と G 問題に流れていっちゃったけど、この問題は難しいことは考えずに、木の中心で頂点集合を２つに割って組み合わせたらどうかなと思った。WA だった。この問題の何が問題なのかがわかっていないか、うまくできなかったか、どちらなのかもわかりません。とはいえ、うまくできていなかったのは間違いない。中心に頂点があるとして、中心から３本以上の辺が出ている場合が考慮できていなかった。■G 問題「Count Substring Query」。ミシシッピの s が足りないのが気になってしょうがない。なんでコンテスト中に辞書を引いてるんだ……。F 問題より見込みがあるかと先に考えていたけど、数を数えようとするとどうしても２乗の時間がかかりそうになる。接尾辞配列を使うだけみたいなツイート(？)を読んだ。その使うだけもできないのだから惜しくも悔しくもないけども、接尾辞配列とか完備辞書とか Trie とか、見て見ぬ振りをして実装せずに来たツケなのは間違いない。「SA-IS 法のメモ - まめめも」８割くらい読んだ。しれっと挟まれた翻訳者自らの宣伝だけど、その本はもう持っている。悲しいかな理解が追いつかなくて積まれているけども。SA-IS 法に話を戻すと、２割が完遂できなくて写経することしかできない。たとえ写経でもするべきなのかなあ(やらないつもり)。やると書いて、やる、有言実行メソッドと、やらないと書いて、やる、天邪鬼メソッドの両方があります。自分のモチベーションをより高める方を選んでどうぞ。■■■精進。F 問題。提出 #55644781 (AC / 1365 Byte / 636 ms)。やりたいことのイメージは合ってたみたい。中心で２つかそれ以上の頂点集合に分けて、異なる集合から１つずつ選んでペアを作る。それをどうやってうまくやるか。葉から処理を始めて、親にどんどん頂点集合を集約していく。その集合の大きさが過半数になってはいけない。最終状態がいくつか考えられる。わかりやすいのが、集約された結果ある頂点とその２つの子が残り、そのサイズとつながりが (N/2)-(1)-(N/2) である場合。左右の子から１つずつ頂点を取り出してペアを作ればいい。総頂点数の偶奇により中央に頂点がない (N/2)-(N/2) のパターンも考えられるがやることは同じ。もうちょっとわかりにくいのは、ある頂点が３つ以上の子を持っていて、どの子に軸足を移そうとしてもその瞬間に他の子が過半数の大きさの頂点集合を作ってしまう場合。最も単純なケースは、２から N のすべての頂点が頂点１につながるスター型のグラフ。頂点１を中央に据えて、他のどの子の頂点集合もサイズはたったの１だけど、どの２頂点もマージできない。そんな感じで頂点集合をマージできるだけマージして残った頂点集合の集合からペアを作るのが次のステップ。同じ集合の中からペアを選びさえしなければいい。だからプライオリティキューを使ってサイズの大きい頂点集合から優先して２つ選んでペアを作ることを繰り返した。もっと洗練されたうまいやり方と考え方が絶対にありそうだけど、AC なんやしまあええやろ(向上心のない怠惰な態度)。あと、自分が中心と呼んでいるものに重心という名前がついているらしいのは何か所かで読んで把握している。■■■F 問題。某週記を読みまして DFS 順でペアが作れると知った。DFS の行きがけ順(に限らない？)に 27 個ないし 26 個の頂点を A-M$N-Z と並べたなら、(A,N),(B,O),(C,P),...,(M,Z) のペアを作る(のだと思う)。ローカリティに注目すればなんとなくそれでいいような気がするし、逆に両端からペアを作っていくのがダメなのもわかる気がするが、いつでも絶対それで OK とはわからない。■自分の解答の後半のステップはプライオリティキューを使わないで、単純に入れ子配列をフラットにして真ん中で切ってペアを作るので良さそう(C.flatten!; C[C.size/2..].zip(C))。どの解説もそういうペアの作り方をしてるので。どの頂点集合も過半数に届かないようにしているのだから、たしかにそれで同一集合からペアを作ることはないみたい。それと、DFS での頂点の並べ方は帰りがけ順でも OK と解説に書いてあった。