ABC213

6完。6回提出して実行時間が単調増加だった。Gは読んだだけ。Hは読んでない。Eがあんまり好きじゃない。解説を読んでみると、教育的なセットを意図されていたことに気づく。黄色復帰。ABCは、失敗も多いけど、けっこうな頻度でパフォ2200以上が取れるので黄色に戻るチャンスは多いという感覚(まあこれもひとたび調子が落ちたらどうやっても戻れなくなるだろうからあんまり意味のない感覚だとは思う)。

A - Bitwise Exclusive Or

まあそういうことだけど、知らないとかなり難しそうなの出してきたな(AC人数B問題のが多い!)。開発環境をAHCモードから戻すの忘れていて、慌ててコード消してテスターのAHC用defineを1行コメントアウトしてという作業をやっていた。それ込みでも1分以内でACできたので不幸中の幸い。

B - Booby Prize

ソートできるstructにA_iとiを入れてソートしてN-2番目を出力。N=2があり得る制約なので、1位はブービー賞なのだろうかと少し不安になった。わりと軽いBで、2分でACできた。

C - Reorder Cards

Cにしては難しいというか重い問題。座標圧縮みたいなことをしているので、座標圧縮をする。最初うっかりしたが、ぶち込む先のvectorは2つ用意する必要がある。sortしてunique。uniqueはこの前スニペットを作ったのが役に立った。あとはそれぞれ二分探索で何番目か求めて出力していく。

D - Takahashi Tour

一見して木上のDFSだが、番号が小さい順に訪れる必要がある。いつものグラフ用ライブラリを、単にvectorvectorへ突っ込むやつに書き換える。ソートしながらDFSする。サンプルが合わず、戻ったときも出力する必要がある問題だった。DFSの関数に入ったときだけでなく、再帰でDFSを呼んだ直後にもpush_backしておく。またサンプル合わず、出力の長さがNだと最初思っててそのままだった。

E - Stronger Takahashi

難しそう。FGを覗いて読みやすそうなGをやろうとするがやはり難しそうなのでわりとすぐ戻ってきた。順位表を見ても、時間が経つとそこそこ解かれていて焦る。これは本当に難しいのですよ。DPしようにも右下へ動くとは限らないし、あるマスへ移動するにもどの2*2を破壊するか複数通りあったりする(1*1を壊すだけのは最初に考えてまあできそう(コストをどうかけるか難しいけど塀に入るとき1払えばいい))。同じマスを複数回通ることはないとしてよさそう。

かなり経って、もう仕方ないので(破壊範囲の重複が怖いけど)1回の破壊で移動できる周囲2マスくらいへコスト1の辺を張るのを実装し始める。周囲20マス(最初24マスと思っていたが斜めへは動けない)へコスト1で移動できると考えるとわりと明快だと気づいた(確信までは行かない(それを明快とは言わない))。移動先が空きマスなら壁の中からでもコスト0で移動できることに、サンプルが合わなくて気づく。一発ACはけっこう運が良かったと思う。考察も実装もかなり重い。無思考での書きやすさを優先したが、メモリが100MB食っててけっこう危ない(一応気づいてはいたけどAtCoderはこの甘えが許される)。時間を消費してしまい、嫌な気持ちに。

F - Common Prefixes

順位表を見てFに専念。まずSuffix Arrayが浮かぶ。辞書順に並べて隣同士の先頭の一致数を見るのと、それを元に答えを求めるの、どちらも難しそう。ただ、ありそうな概念ではあるので色々ググっていると、そもそもACLにlcp_arrayというそのものずばりがあったことに気づく。灯台下暗しすぎるだろ。開いてたACLのページのすぐ下にあるし読んだこともあった。じゃあもう一つの問題を頑張って解こう。まずセグ木を貼ったが、どうも隣との演算ができない。その考える過程で直接計算できそうだと気づいたのでその方針にする。同じことを左右からやればいいので左からやるやつを書く(考察時は右からだった)。一致数が単調増加ならよくて、減ったときの差分計算が問題。自分以下のところまで戻って、そこの答えに足すことの「自分の一致数*幅」(その区間は長方形になる)。遅延セグ木も考えたが、それは実装に時間がかかりそうなこともあり、ここはしっかり考える。こういう状況で遅延セグ木が要ることは少ない。スタックだ。一致数と位置を持ち、自分より大きいものを全部popしてback()を見れば長方形の端の位置がわかる。時間がないのできれいに書いて祈る。サンプルを使って範囲外アクセスとかは直せた。あとは順番がバラバラっぽいので辞書順にソートしてしまってあることに今さら気づく。自身との一致数とかもちゃんと直してサンプルが合い提出。終了5分前でAC。ACLとサンプルにおんぶにだっこだった。

G - Connectivity 2

(追記)自分で考えていたときは、頂点集合Sが連結成分になるのが何通りかわからなかったが、解説を見たらSとS以外に分けて掛け算していた。じゃあSが連結になる場合の数はどうやって求めるか。Sに含まれる頂点を一つ固定して、それを含むS全体ではない部分集合を全列挙し引いていけば全体でO(3^N)(部分集合に対しては計算済みであることを使う)(特に、この問題の場合はSに頂点1が含まれるとしてよいので定数倍の改善になる)。頂点集合を2つに分けて、その2つの間を結ぶ辺は使わないようにするのが上手い。思いつかない。

H - Stroll

(追記)辺が有向辺1本ではなく無向辺10本でややこしいこと、見慣れないタイプの再帰で処理内容がイメージできないことなどから、解説が何日も理解できなかった(こうなると、解説を前にボケーっとしているだけになり無駄な時間を過ごしてしまう)。さて、解説にあるDPで、あるmに対してm未満からm以上への遷移だけを畳み込みで求めていく。多数の辺があるが、こうすることでどんな順番でやってもバッティングしない。歩いた距離[km]は0からTまでT+1通り、それを各頂点に持つ。隣同士は全部O(M)ずつかけて計算することになる。分割統治は、左半分で再帰を呼び、左半分から右半分へ遷移させ、右半分で再帰を呼ぶ、という流れ。この真ん中の遷移だけで全ての遷移をカバーできている。