2025年03月01日 (土)[AtCoder] 今日は AtCoder Beginner Contest 395 があった。自分のすべての提出。コンテスト成績証。F まで典型度が高く簡単でした。G はとりあえずワーシャルフロイド法で全点間距離を求めてから再帰関数で木を作って最小コストを求めてみた。サンプルの１は合う。サンプルの２は答えが合うものも、答えが大きすぎるものもある。わからない。PC の時計が１分近く遅れていてコンテストに遅刻しました。それから、自分はいつも G 問題を開いて提出言語を Ruby に変更してから他の A から F の問題を開いている。そうすると A から F の提出言語が最初から Ruby になっているし、タブの並びが A から G まで順番になるので具合がいいのだけど、今日は G 問題の問題ページに提出欄がなかった。新しい PC だからブラウザの設定が違うだろうからと外部スクリプトを順番に許可してみたりしていたのだけど、なんと今日の G 問題にはもとから提出欄がなかったのだった(提出タブから提出することはできます)。「質問 - ABC395」。さらに無駄な時間を使ってしまったけど、逆に肩の力が抜けた面もある。■A 問題 Strictly Increasing? Enumerable#each_cons で素直に判定した。何をもって「素直」とするかは判断が分かれるところ。適切な初期値を補って N 回判定を行うことを自分は素直ではないと考えたけど、N=1 の場合に each_cons(2) が何を返すか一瞬の判断を要するところが素直ではないという考えもあるだろう。■B 問題 Make Target。B 問題なりの配慮だったのだろうか、冒頭からこれ「以下のような N×N の模様を作成してください 」。ABC375-C Spiral Rotation は難しすぎて解けなかったもんね。今日は出力例を見て見たまんま実装した。■C 問題 Shortest Duplicate Subarray。同じ値の最小間隔が答え。ペナルティが出ていてびっくりしたんだけど、見たら全部 WA だった。この場合のデバッグはむしろ簡単で、スクリプトを２回貼り付けていたのが原因だった。さらに言えば原因は Firefox と MS-IME にある。(バージョンアップした) Firefox は思うようにスクロールができないし、MS-IME は全角/半角の切り替えが狂っている。ATOK2009 を使い続けたかったが Windows 11 においては入力できるコントロールと入力できないコントロールが混在していて支障がある。そのうち必ずなんとかする。■D 問題 Pigeon Swap。E 問題でもよくないですか？ ABC279 では F 問題が BOX でしたよ。どちらの問題も３種類のマッピングを管理して答える。■E 問題 Flip Edge。01BFS かなと思って実装を始めたけど、それだと手戻りというか上書き更新というか、何度もグラフ全体をなめさせられる気がしたのでダイクストラ法に落ち着いた。頂点を倍加した１つのグラフでやるか２つのグラフを並べてやるかで迷ったけど、慣れた方でやった。■F 問題 Smooth Occlusion。歯は伸ばすことができないので大きすぎる H は答えにならない。逆に全部削ればいいのでゼロは必ず答えになる。コストと H は比例している。二分探索で H を決め打ってから、取りうる上の歯の長さの範囲を前から順に求めていった。空でない範囲が得られる最大の H がコストを最小化する。他の人の提出を見るに、実は二分探索はいらなかったらしい。■G 問題 Minimum Steiner Tree 2。1 から K と s, t 以外の頂点が交差点になるケースに対応できていないことが寝る前に分かった。ではどうするか、わからない。