7完64:09 149位
Eで多少詰まったけどFGをまあまあの速度で通せてセーフ
A Attack
切り上げは (A + B - 1) / Bでできるやつ
Aでforが出るならlong long もでていいよね
(AC 2:54)
B Find snuke
250点はなんだと思ってみると重実装がおいてある
とはいっても、楽することはできて
dx = {-1, 0 , 1}
dy = {-1, 0, 1}
の全組み合わせを、すべてのマスを始点として試せばよいです
8方向書くときには↑のような定義おすすめです(dx = dy = 0は適切に省く)
(AC 8:12)
C Almost Equal
えー、地味にむずくない？と思ったら制約に答えが書いてありました
N ≦ 8なので順列全探索ができます
判定は1文字ずつみて素直にやるだけ
(AC 11:46)
D Impartial Gift
「2つ選びます」「3つ選びます」みたいな選ぶ個数が少ないタイプの問題は、とりあえず1つ選んでしまって、そこから最適なものを考えるとうまくいくことが多いです
今回も1つ決めてしまいましょう
Aiを1つ決めると、最適なのはBi ≦ Ai + D となるもののうち最大のBiです
(もしそのBiがAi-Dより小さいなら選べないことに注意)
これは二分探索で簡単に求めることができます
Biを1つ決めるものも試して最大値をとればよいです
(AC 19:33)
E Isolation
辺をくっつけて連結成分数 -> Union Findか？と思ったけどただの過学習でした
辺を頻繁につけたり外すのはUnionFindだとあまり得意ではないので、少し違うかなと思って普通に考察します
※1回だけ外すとかだと逆順にみるのが有効なことが多い？
2番目のクエリの辺を削除するというのが大変かな？と思うのですが、もともと辺がないし追加されるのもクエリにつき1辺なので、愚直に削除しても間に合いそうです
では、2番目のクエリの処理の仕方を詰めていきます
普通に隣接リスト(vector<vector<int>> G(N) のような形)で持つことを考えます
頂点iにつながっているものをすべて削除するクエリが与えられるとき、G[i]はすべて削除すればよいです
しかし、iとつながっている先の頂点でもiを削除しないといけません
これを普通にやるとvectorからiを探索して削除しないといけないので、最悪O(N)かかってしまいます
ここでsetを使うと「iを探索して削除」をO(logN)で行えるので、高速になります
よって、つながっている辺をsetで管理することでクエリの各処理がO(logN)で行えるので全体でO(QlogN)になり、十分間に合います
(AC 30:35)
F Merge Set
何で思いついたか説明しづらい...過去問演習の効果としか
同じ数字を含むものはつながっていてほしいという"おきもち"を抱くので、そうできるように考えます
左側に1~Nの番号、右側に1~Mの数字をあてはめた二部グラフを考えます
i番目の集合にjが含まれるなら、左側のi と 右側のj を結びます
(この時点では完全な解法は思いついていないですが、このようなグラフをつくって考察する価値があるだろうという読みでつくっています)
このグラフを使って考察すると、(当たり前ですが)右側の1から1回操作すると左側の「1を含む集合」にたどり着くことができます
同様にグラフを使って考察すると、「iとjを含むための回数」 = 「右側のiから右側のjまでの最短路 / 2 - 1」になることがわかります
(ここはサンプルをもとにいろいろ手を動かしてみるとわかりやすいと思います)
よって、このグラフで最短経路問題を解けばいいのでBFS, Dijkstraなどを使えばよいです
(AC 38:47)
G Sort from 1 to 4
めちゃめちゃ解かれていたのであせった...
まず広義単調増加となる列は一意に定まるので、それは求めておきます
そもそも、もとの列と広義単調増加の列で値が等しいものは動かすのが無駄なのでそのままにしておきます
そうでないものとして、以下の3パターンが考えられます
(i) 1 <-> 2 のように2点swapで解決する(=1回操作)
(ii) 1 -> 2 -> 3 -> 1のように3点をぐるっと回すと解決する(=2回操作)
(iii) 1 -> 2 -> 3 -> 4 -> 1のように4点をぐるっと回すと解決する(=3回操作)
まず、(i)はして損することがなさそうなので優先することにします
問題は(ii)と(iii)ですが、可能であれば(ii)が優先できたらいいですが、(ii)を優先した結果(iii)が増えるということがあると困ります
順位表をみるとよくわからない貪欲が落ちそうな割には、ペナが少なめです(嘘貪欲で落ちるならAC / Submit = 1 : 2~3になりそうですが、 160/200くらいでした)
こう考えると、適当な貪欲で通りそうなので(ii)を優先することにします
(ii)の中の優先順位もよくわからないんですが、普通に貪欲にしてみます
具体的な実装としては、3重ループで(1,2,3),(1,4,2)など組を列挙してそれがあれば処理するようにします
「組に該当するものがあるかどうか？」は
count[i][j] := 広義単調増加列だとiの位置に、jが存在する個数
をあらかじめ計算しておけばよいです
(i) -> (ii) -> (iii)の順に貪欲に処理していって提出すると通ります(証明AC)
(AC 64:09)
総括
Eの過学習よくないね
