脳log[20250419]

2025年04月19日 (土) [AtCoder] 今日は東京海上日動プログラミングコンテスト2025（ABC402）があった。E まで解けない問題ではなかったけど、D も E もうまくできなかった。実装が下手。やりたいことのコード化能力が低い。■A 問題 CBC。scan で大文字をピックアップしたけど、delete で小文字を消す方が短くなったみたい。■B 問題 Restaurant Queue。やります。実はクエリの種類を見る必要はなくて、クエリの第２項を何個出力するかという問題。■C 問題 Dislike Foods。ある食材を含む料理が何か、ある料理に苦手が何個残っているかを管理する。X で見かけた湯婆婆のセリフによると(「初日に克服されるのに食材名が６なのかい…？ ゼイタクな名だね。今からお前は１だ！」)、食材番号からその食材が苦手でなくなる日が引けるようにしておいて、料理ごとに苦手でなくなる日の最大値を求めて並べても解けるみたい。■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)。実装はそれなりにたいへんで、１時間ちかくかかった。■■■D 問題。平行線を管理するのに不変量がいろいろあったらしい。自分がやったのは平行線を円周上まで平行移動したときの頂点番号(２つ)のうち小さい方。他にはたとえば端点の片方を特定の頂点(１とか)に重ねたときに他方の頂点が何番になるか、とか？ X でちらっと見かけただけで細部はよくわかっていないけども。他方が円の外に飛び出ないようにどちらを１に重ねるかとか、他方の頂点は必ず番号の付いた頂点に重なるのかどうかとか、頂点１の場所で接線になってしまったときは他方の頂点も頂点１に重なったということになるんだなとか、いろいろ考えてしまってまとまらない感じ。もうひとつ見かけた天才解法は２つの頂点番号の和を N で割った余りで平行線を分類する方法。たとえば頂点 a と b を結ぶ直線があるとして、これを頂点１つぶん平行移動した直線は頂点 (a+1) と (b-1) もしくは頂点 (a-1) と (b+1) を結ぶ直線ということになり、頂点番号の和を N で割った余りが不変量として維持されていることがわかる。わかる？ 言われなきゃわかりませんよ。それにそれを飲み込んだとして、それで？ ってなるのが普通の反応ですよ。同じであってほしいものどうしが同じであることはわかったけど、異なっていてほしいものが必ず異なっているとどのようにして了解されるのか。なんもわからん。わからんってことはないか。一端を固定してもう一方を動かすことを考えると、その値はプラスマイナス合わせて N-2 通りの(引く２は元々の両端点を除外している)、最大で N-2 だけずれた値をとるわけだから、N で割った余りで十分に区別ができる。できるんだって。できるみたいですね。そんなん一人で自ずとわかるわけがないんだよなあ。脳みその配線が違う。だけども、天才でなくとも泥臭く分類して解ける間口の広い問題だったのが良いなと思います。