* を補って全体を N 行 M 列に揃える。次に配列を transpose して reverse する。この時点でほぼ出力ができあがってるんだけど、各行末尾の * を取り除いてから出力する。■C 問題「Balls and Bag Query」。Hash で個数を管理してサイズを答える。カウント 0 になった要素は取り除く。■D 問題「Cuboid Sum Query」。３次元の累積和。具体的にイメージができないので、機械的に操作をする。うまく１次元の操作を２次元３次元に拡張できるといいね。行列計算がそうだしこの問題もそうだったけど、自分は必ず演算対象の次元数を勘違いしてエラーを出す。数値に対して配列のメソッドを呼んだりする。包除も機械的にやる。３つの次元について L を使うか R を使うかの２通りがあるので全体では 2^3=8 通りの累積和を足し引きする必要があるが、３つとも R を選ぶのが全体であり、そこから引いたり引きすぎたものを足したりするのだから、３個の R を選んだ場合をまずプラスにして、つまり奇数個の R がプラスで偶数個の R がマイナスになる。これはコンテスト終了後に AC が出たからわかったようなことを書いている。コンテスト中は飛ばして E をやっていた。D と E がどちらもたいへんなら配点の高い方に時間を使う。■E 問題「Manhattan Multifocal Ellipse」。D (入力値) の最大値が 100 万だということで、平面上のエリアを具体的に特定できると思った。X 座標と Y 座標を分けて考えるけど、それぞれプラスマイナス D の範囲に限ることができる。D×D は通らないけど、１つの軸を１つずつ走査しながらもうひとつの軸が効率的に数えられたらいい。(WA×1/TLE×5/AC×23) までは行ったんだけど、log の２乗は「効率的」ではないんだよなあ。でも尺取りをするのもたいへん。(WA×1/TLE×11/AC×17) の構造を崩して改善した結果がさっきの TLE×5 なのであって、さらにぐちゃぐちゃ書き直したくない。それが済んでも WA×1 が残る。■F 問題「Maximum Composition」。制約が小さい。K は 10 以下だし、(A,B) の組み合わせも 2500 通りしかない。ということは最大 20 万個の (A,B) には重複がたくさんあるのだが、K 個以上は K 個と変わらない。という感じでなんとなく状態数が少ないような気がしたからといって、メモ化再帰をするだけでは TLE になるのだなあ。コンテスト終了後に取り組んだけど TLE だった。■なんと ABC の３完だ。自分のすべての提出。いまもって E も F も AC が出ないのだから、D の AC が時間内か終了後かはどうでもいいよ。どっちでもだめだよ。■E 問題。AC 出たよ。提出 #56580497 (AC / 942 Byte / 642 ms)。一方の軸を走査しながらもう一方の軸について数えるのではない。それぞれの軸について独立に、座標を、距離の総和に変換する。あとは距離の列と列をソートして尺取りっぽく和が D 以下になる組み合わせを数える。そうしたら TLE が解消しただけでなくなぜか WA も消えていた。コードはほぼすべて先の２つの提出のコピペであって、なんの修正もしてないのに、謎だ。これで A から E まで AC が出たけど、100 分で５完の目がある問題セットではなかったな、というのが感想。D も E も実装が重い。かといって４完ではなく３完なのは全くの想定外。これまで２回くらい脳みそにクモの巣が張ってるって日記に書いてるけど、それってブレインフォグっていうんじゃあありませんか？(何かのせいにしたいだけ。キミはもともとそんなのだ)■F 問題。どうするのかなあ。引数が大きくなればなるほど A が作用する比重が B のより大きくなっていくのを利用して状態数を減らしたい気がするんだけど、A 対 B の２次元の表に線を引いてトップ K を選ぶことってできない。■D 問題の提出一覧を見てると、自分のが特に遅い。３秒制限ぎりぎりだから当然なんだけど、どこが遅いのか。３次元累積和の作り方が下手っぽい。自分のは余分にループが回っている。なにか標準的な手順があるのだろうか。自分はまず３次元空間を用意して、３つの軸について順番に一方向に寄せるように累積和を作成していった。無駄があるのは、３つのパスで順番に、１次元累積和の作成、２次元累積和の作成(１次元累積和のマージ)、３次元累積和の作成(２次元累積和のマージ)を行っていて、たぶん３つともに３乗の時間と空間が使われているところだと思う。どうもね、すでに更新済みの累積和を参照しながら１パスで３次元累積和を構築してる提出が多いみたい。それってややこしすぎません？