2025年05月10日 (土)[AtCoder] 今日は AtCoder Beginner Contest 405（Promotion of AtCoder Career Design DAY）があった。結果はまあまあ。ペナルティ２つがしょうもない。■A 問題 Is it rated?。こういうのは仕様をそのまま書きます。仕様はコードではなくデータで表現するのがおすすめ。コードはなんでもできすぎる。■B 問題 Not All。Array#tally で種類数を管理しながらシミュレートした。■C 問題 Sum of Product。すべての組み合わせの積の和。Ai に対して Aj (j=i+1,...,N) の和を掛ける。■D 問題 Escape Route。あまりにも実装が下手だった。全部で 25 分かけて TLE も１回出した。グリッド BFS を書くのが下手(そんなことある？ 驚きました)。この TLE だけど(#65661930)、31 行目を分解すると倍速くなった(#65666427)。グリッドの移動部分もアンローリングするとさらに倍速くなった(#65668293)。手を抜いたわけではないのです。早過ぎる最適化は悪なのです。■E 問題 Fruit Lineup。４つの果物を並べる３つのルール。きれいに整理できそうでできなくてでもやっぱりできた。バナナとブドウを混ぜて並べたあとで、最も左のブドウの位置に応じて、ブドウの左にあるバナナとリンゴのあいだにオレンジを並べる。■F 問題 Chord Crossing。ABC402-D Line Crossing で多く観察された誤読バージョンが期待に応えて登場。今回も誤読しました。時間をオーバーしながらとりあえず実装を終えたけどサンプル２が合わない。ノートをひっぱり出してきて図示して気がついたのだけど、線分どうしが共有点を持たないといって、そのありようにはバリエーションがある。２と４、６と８、10 と 12 を結ぶ３本の線分もたしかに共有点を持っていないが、こんなケースを全く想定していなかった。奇数の頂点を２つうまく選ぶことですべての線分を必ず貫くことができると想定していたのだけど、それは間違いだった。じゃあクエリの区間のあいだに出入りする線分をうまく数えてなんとかしたいね。最初はこの線で考えていたんだけど、すべての線分を平行に並べ直せるならより簡単に解けると思って、でも勘違いだったんだよなあ。■精進。F 問題。提出 #65700291 (AC)。クエリ区間のあいだに外から入って来る線分と外に出て行く線分を数えて、区間の内部で出入りが完結する線分を無視するために、何を管理すればうまくいくか。ABC402-D を誤読したときに誤読したまま解答までたどりついていれば今日は考える必要がなかった。残念ながらそうではなかったので、今日たっぷり考えさせられることになった。クエリ区間が始まるときに、すでに頂点を出発していてクエリ区間中に着地する予定の線分を BIT で数える。クエリ区間が終了するときには、頂点を出発していてまだ着地していない線分のうち、クエリ区間開始時にはまだ出発していなかったものを数える。これだけのことなんだけど、何をメモしてそれをどう足し引きするかということがものすごくややこしかった。■時間内に解いている hmmnrst さんの提出 #65685391。セグメント木を使ったあまりにもすっきりした解答。自分の頭の中のこんがらかり具合を反映して、ぐだぐだと順を追ってあれを数えこれをメモしてやっとのことで答えを出している解答との差よ。