ABC309

6完。

A - Nine

考察にけっこう時間かかった。雑に言うと差が1。例外は、盤面をにらむと、Aが3の倍数のとき(A=9のときは差ではじかれてるけど別にいい)。

B - Rotate

考察にめちゃくちゃ時間かかった。盤面を時計回りに見ていく。そのために長さN-1のfor文を4つ書く。そのマスにある数を取って手元にホールドする。元々ホールドしていた数をそのマスに入れる。この操作は要するにswapだ。そうやって1周すれば大体OK。最初のマスに入るべきものをホールドしてから始めればよい。

C - Medicine

かなり難しい。aでソートするのはすぐわかるけど、そこから状況を把握するまでがまず難しい。単調減少なのもすぐわかるが、bの総和を求めて引いていけばシミュレーションできるのだった。出力すべき値は、1かa_i+1。K以下になったら出力すればいい。同じ日数の薬が複数あるとややこしいが、a_i日目はダメだしa_i+1日目はOKだからコード上は特にすることない。直前に引き算した薬の日数を持っておく。

D - Add One Edge

まあ遠いところ同士を結ぶだけだよね。不安なので確認する。BFSを2回するだけ。追加した辺をカウントするの忘れてサンプル合わなかった。

E - Family and Insurance

内容はシンプルだけど、問題文を読むのが大変だった。家系といっても親は1人しかいない。パッと見で明らかに木なんだけど、制約をしっかり見ないと連結であることが確認できない(いやこれで連結じゃなかったら閉路ができちゃうけど)。そこに時間を使ったあげく、1人が複数の保険に入るケースがあることを見落として1ペナ。

親の保険は範囲が上位互換になるので上からDFS、1を引きながら。制約上、子が対象にならない保険はないが、自分だけが入る保険をy=0として扱うと認識することで見通しが立つ。保険に入っていない状態は0ではなく-1だ。解説を見ると、トポロジカル順になってるからグラフを構築しなくてもいいんだね。そんなことにも気づかずどこに時間使ってた?

F - Box in Box

別に幾何というわけじゃなく、上位互換(上位互換と完全上位互換の違いis何)があるかという話。座標圧縮していい。長さ3のarrayに入れてそれをソート。全体も最初の要素でソート。2次元の図を描くと、要素0の順に追加して要素1をプロット。そうすると自分より小さい候補がある長方形の範囲が見えて、その中で要素2の最小値がわかればいいので、BIT(最小値を求めるバージョン)でできる。こんなに3次元詰め込めるんだねえ。

G - Ban Permutation

まあDPだろうなあと。箱根駅伝の名前とかも浮かんで、できるわけないけどなぞに挑戦する。ずっと端からやろうとしていたが、かなり経ってから三角形の狭い側からやると簡単だと気づいた。端のXずつは除いて、中央を左から考えると、上を選ぶ数とこれまでに上を選んだ数を持てばDPできそうな気がする。これを(正しいかわかんないけど)頑張ってコンテスト終了後も書いていたが、そこがわかっても端のXずつが当たり判定広すぎて不可能なことに今さら気づいた。