ABC260D"Draw Your Cards"をRubyで解く
茶落ちは最近なくなってきたけど入水できる気がしねぇ……。
今回の問題はこちらです。
本番中に考えたこと
一年半もatcoderをやっていれば、D問題で出てくるアルゴリズムは大体想像がつきます。
「Xより大きい数字のうち最小の物を検索」というのは体感上90%が二分探索です。(9%がfenwick木。1%のセグ木はE問題ならともかくDで出たら何かの間違いなので出たら静かに涙する。)
二分探索 is 何
二等分して、答えが上にあるか下にあるか判定
→答えのある方を二等分して、答えが上にあるか下にあるか判定
→答えのある方を二等分して、答えが上にあるか下にあるか判定
これを最後の1個になるまで繰り返します。
めちゃめちゃ小さい数字をアウト、めちゃめちゃ大きい数字をセーフとして二等分していくと、「Xよりも大きい数字のうち最小の物」が残ります。
そして、実はrubyの配列にはこのメソッドが最初から組み込まれています。
逆に小さい方をセーフ、大きい方をアウトに設定してから二等分を繰り返すと、「Xより小さい数字のうち最大の物」が残ります。
上記のメソッドは「前半が全部false,後半が全部true」の場合にしか使えないので、sort.reverseするなどの工夫をするか、諦めてループでフルスクラッチする必要があります。
二分探索の弱点。順位が変動する配列
この二分探索そのものは軽いです。今回のカードは最大20万枚。これくらいなら余裕で間に合います。
が、それはあくまでお膳立てが整っていればの話。
詳しくはうさぎでもわかるさんに譲りますが、二部探索のためにはソートという重たい前処理が必要です。ハマれば強いのに上げ膳据え膳じゃないとハマらない奴です。ハンターハンターで言えばジャジャン拳、ガッシュで言えばバオウ・ザケルガ。雑に乱射して強いタイプではなく、撃てる状況に持っていくのがそもそも難しいタイプの必殺技です。
カードは最大20万枚、つまりソートも20万回。TLE不可避。
問題文を読むことの重要性
ここで盛大に沼りました。「カードを引くたびに場の山の順位が入れ替わり、それをソートする」など到底無理です。
10%の木構造問題かとも思いました。あれなら「カードを引くたびに場の山の順位が入れ替わり、それをソートする」必要がありません。しかしfenwick木やセグ木で「X以上かつ最小」の問題など解いたことがありません。じゃあどっちにしろ入水は無理だよ。
(解説はしませんしできませんが、今回の問題はfenwick木でも解けるそうです)
ヒープで行けないかとも考えましたが、あれは「配列の中の現状での最小(or最大)」を出すためのデータ構造です。「X以上」がクリアできません。
もう無理だ。5完どころかD問題すら解けない。「カードを引くたびに場の山の順位が入れ替わり、それをソートする」方法なんて見つからない。そうトイレで泣いていた時、ふと気が付きました。
「山の順位が入れ替わる事、なくね？」
問題文をもう一度読み返すと、新しいカードが置かれるのは「場に見えている表向きのカードであって書かれた整数がX以上であるもののうち、書かれた整数が最小のものの上」または「場にそのようなカードがなければ」「どれにも重ねず」のどちらかです。
つまり
既存の山の上に積み、山の数字がXになった場合:山の数字が小さくなり過ぎて他の山を追い抜いてしまう事はない(これより数字が小さい山はすべて数字がX未満のはず)し、山の数字が大きくなってしまう事もない(Xより小さい数の上にXのカードは積めない)。前にも後ろにもズレないので順位は入れ替わらない。
どれにも重ねない：X以上の数字の山が存在しない。つまりXが見える範囲で最大なのでやっぱり順位が入れ替わらない。
実例
入力例3で考えてみましょう。
3 14 15 9 2 6 5 13 1 7 10 11 8 12 4
ターン1;3を引いてどれにも重ねない。
[[3]]
# 上から見たときの場の状況は[3]
ターン2;14を引いてどれにも重ねない。
[[3], [14]]
# 上から見たときの場の状況は[3, 14]
ターン3;15を引いてどれにも重ねない。
[[3], [14], [15]]
# 上から見たときの場の状況は[3, 14, 15]
ターン4;9を引いて14に重ねる。
[[3], [14, 9], [15]]
# 上から見たときの場の状況は[3, 9, 15]
ターン5;2を引いて3に重ねる。
[[3, 2], [14, 9], [15]]
# 上から見たときの場の状況は[2, 9, 15]
ターン6;6を引いて9に重ねる。3枚組になったので場から除去。
# [[3, 2], [14, 9, 6], [15]]
[[3, 2], [15]]
# 上から見たときの場の状況は[2, 15]
ターン7;5を引いて15に重ねる。
[[3, 2], [15, 5]]
# 上から見たときの場の状況は[2, 5]
ターン8;13を引いてどれにも重ねない。
[[3, 2], [15, 5], [13]]
# 上から見たときの場の状況は[2, 5, 13]
ターン9;1を引いて2に重ねる。3枚組になったので場から除去。
# [[3, 2, 1], [15, 5], [13]]
[[15, 5], [13]]
# 上から見たときの場の状況は[5, 13]
ターン10;7を引いて13に重ねる。
[[15, 5], [13, 7]]
# 上から見たときの場の状況は[5, 7]
ターン11;10を引いてどれにも重ねない。
[[15, 5], [13, 7], [10]]
# 上から見たときの場の状況は[5, 7, 10]
ターン12;11を引いてどれにも重ねない。
[[15, 5], [13, 7], [10], [11]]
# 上から見たときの場の状況は[5, 7, 10, 11]
ターン13;8を引いて10に重ねる。
[[15, 5], [13, 7], [10, 8], [11]]
# 上から見たときの場の状況は[5, 7, 8, 11]
ターン14;12を引いてどれにも重ねない。
[[15, 5], [13, 7], [10, 8], [11], [12]]
# 上から見たときの場の状況は[5, 7, 8, 11, 12]
ターン15;4を引いて5に重ねる。3枚組になったので場から除去。
# [[15, 5, 4], [13, 7], [10, 8], [11], [12]]
[[13, 7], [10, 8], [11], [12]]
# 上から見たときの場の状況は[7, 8, 11, 12]
山の一番上の数字(小配列の最後の数字)に注目してください。一度も昇順ソート状態が崩れていないのがわかると思います。
ここの昇順が維持されっぱなしならしめたもの。いちいちソートを繰り返さなくても二分探索ループで殴り倒せます。
解答
7行目で-1で埋め尽くした配列を準備します。これにカードを食べたターンを記録していき、最後に表示します。
表示するターンは1-indexed,each_with_indexのindexは0-indexedなので、9行目で+1します。
10行目の二分探索で、「山の表示カード(配列末尾)が引いたカードよりも大きい山のうち、一番表示カードが小さい山のインデックス」を検索。
もしもそのような山が存在すれば(12行目)その山の一番上にカードを積みます(13行目)。
もしもそのような山が存在しない場合は(14行目)山そのものを新しく追加し(15行目)その山自体を食べるか判定に回します(16行目)。
18行目以降は山が食べるべき大きさに達しているかの判定です。食べた場合は7行目で用意した配列に現ターン数を記入し、山を削除します。
rubyの配列は0-indexedですが今回のカードは1から始まるため、最後に配列の先頭をshiftで削除し、putsに渡せば要素ごとに区切って表示されます。
ま、時間かけすぎたせいで結局4完の緑パフォだったんですがね。
Discussion