Cまで。
No.1425 Yet Another Cyclic Shifts Sorting
自力AC。
二種類あれば隣接要素SWAPができそうなので、答えは高々2。0回の判定は簡単なので、1回でできるかどうかを調べれば良い。
一回でできるかどうかは、ソートした配列と比較し、最大値が一致していれば消していく。
残った配列について、ソートしたものを巡回したものになっていれば良いので、ローリングハッシュを使って判定した。
が、解説を見たらもっと簡単にできたらしい。なるほど。
ところで、なぜタグが「動的計画法」なのだろう？ 解けたと思った後タグを見たらそう書いてあって、何か間違っているのでは？ と疑心暗鬼になりながら実装した。
（タグに頼るのはいけないかもしれないけど、yukicoderのタグはいつも出したまま問題を考えています）
No.1426 Got a Covered OR
解説AC。
A_iが全て正、という条件の扱い方が難しい問題。
包除原理で扱うのかな？ とは思ったものの、DPで包除原理でやるのかと考えてしまってダメだった。
・範囲を分割できること
・それぞれの範囲について、二項係数を使って計算していける
ことに気付ければ解ける。
bitの中で条件を満たさないものの個数で包除すれば良い。
方針が分かれば難しくない。何で包除すれば良いかを考えるのが大切だった。
No.1427 Simplified Tetris
解法は自力で分かったが、ACするのは苦戦した。
盤面が与えられたとき、ちゃんと置けるかどうかは、この問題と同じ。
なので、元の盤面の候補を全探索したい。
ブロックが入っているマスの前後に何マスあるか？ をDFSで調べれば良さそうだが、何列必要かが分からない。高々2列で十分だろう、と思ったらWAで、3列必要な場合があった。
そして、それで全探索するとTLEしてしまったため、ずるいけれど時間で打ち切る処理を入れてAC。
解説を見ると、もっと上手にやる方法が書いてあった。気付かなかった。
0 件のコメント:
コメントを投稿