脳log[20240302]

2024年03月02日 (土) [AtCoder] 今日は ABC343 があった。では ABCDE のふりかえりを。■A 問題「Wrong Answer」。言われた通りにやる。だから答えを 0..9 の範囲で探したけど、２つの数字を選んだら必ずそのうちの１つ以上が答えになることには気がつかなかった。■B 問題「Adjacency Matrix」。B 問題からグラフかとびびったけど、グラフ問題を解くために隣接行列形式のグラフ表現に慣れておきましょうね、という問題だった。■C 問題「343」。N が 10**18 以下の制約。列挙はできないなと思ったけど、平方数なら列挙できるかな、いやできないなと思って、もう一度問題を読んだら立方数だった。立方数なら列挙できる。脊髄反射をやめて問題を読もう。読んで頭に入れよう。■D 問題「Diversity of Scores」。ハッシュ表で数えます。■E 問題「7x7x7」。制約の元になる数字は７と小さいけど、これが何乗にもなるので制約の厳しさが見積もりにくい。結果的にはがちがちに厳しくはないけどゆるゆるでもないという制約だった模様。自分の AC 提出はちょっとだけ工夫した脳死愚直解で 1892 ms だったけど、同じ Ruby で 81 ms の提出がある。AC が早い順に 81 ms、319 ms、1555 ms、1892 ms となっている。おかしくない？ 時間をかけたほど出来が悪いっておかしくない？ 自分の工夫は総当たりする範囲を限ったこと。１つめの立方体は C(0,0,0) で決まり。２つめの立方体の１つめの軸は 0..7 の範囲で網羅できる。２つめの軸は１つめの軸以下の範囲に限って良い。３つめの軸は同様に２つめの軸以下に限る。３つめの立方体の置き方をどうするか。最適な置き方がわかるなら全探索などしていない。V3 がゼロか正かで場合分けをして、ゼロなら１つめの立方体と重なったり重ならなかったりする範囲を列挙したが、２つめと重ならない範囲とアンドを取っても良かったか。V3 が正の場合は１つめと２つめの立方体の両方と重なる範囲を列挙した。あとは空間に１、２、３とマーキングしていってそれらの個数が V1、V2、V3 と一致しているかを確かめた。AtCoder Problems によるとこの E 問題が青 diff の一方、より配点が高い F 問題が水 diff だったらしい。報われないなあ。■F 問題「Second Largest Query」。AC がまだなので不確かだけど、セグメント木で２番目に大きい数が求められるのではないか。目当ての数がわかったら、範囲内にある個数を BIT もしくはセグメント木で数えられるなら数えたいけど、数の種類数×範囲の幅≦20万の２乗になるので工夫が必要。内部データを Hash で持つ BIT でクリアできるならお手軽だけど、ある程度運任せになるうえ定数倍も重い。SortedSet があればそれが最適だけどない。A,B-木でも良さそう？ だけど以前の実装をこの問題に適合させるのが難しかった。もう内部構造を覚えていない。効率良く insert できるソート列を２本用意したら、delete 操作は実装しないで済ませられる。■F 問題。他の人の提出を覗いてみた。セグメント木だけで個数も数えられるっぽい。そうか、全部の数を数える必要はないのだ。トップ２の値と数だけ覚えておけばいいのだ。セグメント木の使いこなし術が足りていない。■F 問題。サンプル以外 TLE になった。提出 #50851673 (TLE)。完敗です。完全に何かがおかしい。■E 問題。立方体の共通部分を計算で求めると速いらしかった。３次元の重なりをイメージするのは難しいけど、やってみたら区間の共通部分を３回求めるだけだった。提出 #50880639 (AC / 948 Byte / 417 ms)。IX 関数で直方体の共通部分を求めて、V 関数で直方体の体積を求める。どちらもワンライナーで書ける程度の簡単な式。あとはテキトーに６重ループで列挙して簡単な３者の包除。だけどこれでもまだ 417 ms かかっている。81 ms は異次元じゃない？ Yes になり得る入出力を全ケース埋め込んだと思しきこちらの提出 #50846546 が 108 ms……はジャッジ起動後の第一ケースの特異例だとして次点が 57 ms なんだけど、ほとんど遜色がないよ。■F 問題。トップ２の合成をするのに Hash を使った集計をやめてネストした if 式で３分岐×３分岐=９分岐の結果をベタ書きしたら間に合った。提出 #50881793 (AC / 1063 Byte / 1670 ms)。そんなにかわるんだ。他の人の TLE/AC 提出の差分を見ていると、セグメント木の初期化を 2N でやるか NlogN でやるかでも結果が分かれるみたい。シビアだ。