脳log[20250419]

2025年04月19日 (土) [AtCoder] 今日は東京海上日動プログラミングコンテスト2025（ABC402）があった。E まで解けない問題ではなかったけど、D も E もうまくできなかった。実装が下手。やりたいことのコード化能力が低い。■A 問題 CBC。scan で大文字をピックアップしたけど、delete で小文字を消す方が短くなったみたい。■B 問題 Restaurant Queue。やります。実はクエリの種類を見る必要はない。クエリの２項目を何個出力するかという問題。■C 問題 Dislike Foods。ある食材を含む料理が何か、ある料理に苦手が何個残っているかを管理する。■D 問題 Line Crossing。最初しばらく違う問題を解こうとしていた。円内と円周上で交点を持つ直線の組を数えようとしていた。そういう設定なら直線ではなく線分っていう用語を使うんですよね。問題文中の直線という用語とサンプルを見て勘違いに気がつくまでひととおり考えたあとだった。直線の交わりだというなら平行線の組を数えて除外すれば良い。平行な直線をどのようにまとめるか。代表点を決めることにした。２頂点の中間に頂点が１つないし反対側にもう１点あるならそれらの数字の小さい方。１つもなければ 0.5 で刻んだ仮想の中間頂点を２点想定してそれらの小さい方。これを実装するのに WA を３回出した。実装が下手。■E 問題 Payment Required。とりあえず実装したメモ化再帰でサンプルが通ったので終了 30 秒前に提出したものが TLE×7 だった。D 問題に１時間以上かけたせいで実装を詰める時間が残っていなかった。その後ぼちぼち試行錯誤して 30 分後に AC (#65043290)。２重の Hash をやめてメモ配列とメモ配列を埋める関数のペアとし、配列も２重にするのでなくフラット化した。これは頭を使うようなことではなく、技術的機械的な操作でしかない。だったら E まではさささっと解いて F に頭を使いたいんだよなあ。■精進。F 問題 Path to Integer。X で半分全列挙って読んじゃったからなあ。自分で気がつける可能性は 10 % くらいと限りなく低い。つまり、これまで１度だけしか気がついたことがない。この問題について言えば、コンビネーションで計算量を見積もる発想がまず出てこない。ネタが割れてしまえば実装するだけ。提出 #65046061 (AC)。実装はそれなりにたいへんで、１時間ちかくかかった。