ABC196 参加記＆解法メモ
97分5完でした。
A-Difference Max
2変数x,yの範囲が与えられるのでx-yの最大値を求めてね、という問題。
この手の変数の範囲が与えられて色々する問題はA,B問題などでよく出ますが、変数の境界を見ることで容易に解けることが多いです。
今回の場合は(xの最大値)-(yの最小値)、すなわちb-cが最大になりますね。とくに罠という罠もないです。
あれぇ！？
C#で出すべきところを間違えてPythonで提出していました……。
B - Round Down
やー、なぜか特定のWriterの顔が浮かんでくる問題だねー。
めっちゃ長い小数が与えられるから整数部を返してね、小数部の長さは0から100だよ、っていう問題。
入力を数値型として受け取るのは不可能（できる言語だとしても64bit浮動小数点数だと誤差が出る）ので、文字列として受け取る。
文字列内に'.'があればその手前まで出力し、なければ全部出力。
for文でチェックしながら出力するんでもよいし、'.'で文字列を分割して1つ目の文字列を出力するのでもよい。使ってる言語に応じてよしなに。C#ならX.TakeWhile(c=>c!='.')だけでいいですね。
ちなみに小数入力を文字列として受け取るテクニックは最近のコンテストでも何回か登場しているので、覚えておくのがいいと思います。decimalみたいな誤差の出ない数値型がある言語ならそれを使うのでもまあいいんですが。
C - Doubled
桁数が偶数であって前半と後半が同じ文字列でN以下であるような整数xの数を数えてね～、って問題。
N≤10^12なので全探索は不可能。必要条件から絞っていくのも筋が悪そう。
ここで、前半と後半が同じ文字列であるという条件に着目する。この整数文字列は10^6以下であるので、全探索が可能となる。1以上10^6以下の各整数について、2つ結合したものがNを超えないかどうか下から愚直にチェックしていけばよい。
D - Hanjo
これ難しいっすね……。最初問題斜め読みしてツルカメ算かと思った。
2×1の畳と1×1の畳を使ってH×Wの部屋を敷き詰める方法は何通りあるかな？っていう問題。
H×W≤16っていう制約の主張が強いので、bit全探索を初手思い浮かべるも、どう見ても面倒そうなので他の解法を考える。
これを思い出したけどどう見ても関係なさそうだったので記憶から飛ばす。
グラフとみなして探索もできそう。ただ、うまく状態を持ちながら探索する方法がパッと浮かばない。
他にもいろいろ考えたが、結局きれいに書けそうな方針が浮かばなかったので意を決してbit全探索で行くことに。
図のように、セルの境界となる辺に番号を割り振る。また、セル自体にも左上から数字を割り振る。
辺の数NはH*(W-1)+W*(H-1)となるので、最大でも24本。これをbitで管理する。
i桁目のbitが立っているとき、その辺を跨ぐように1×2の畳が敷かれているとする。
1×2の畳が重なるときを考えると、セルを構成する辺のうちbitが立っている辺が2本以上あることがわかる。
よって、立っているbitがA個であり、セルを構成する辺のうちbitが立っているものが2本以上であるようなセルが存在しない部分集合の数を数えればよい。
セルの番号と辺の番号の対応は図のようになる。ただし、該当する辺がセルとの境界でない（外枠である）場合は飛ばしてよい。
ここの対応を正しく導出する部分で手間取ってしまった。添え字ガチャは悪い文化。
計算量がよくわからなくて不安だった。
最悪ケースはおそらくH=W=4かつA=8の時。bit全探索パートで2^24≒1.6*10^7個の部分集合を列挙し、そのうち24C8個で最大16個のセルについて4方向の辺の判定処理を行うので、そこは4.7*10^7くらい？ただ実際には枝狩りが相当効くはずなので、まあ間に合わんことはないだろうということで実装。提出してみたところ、155msと十分短い実行速度でACした。
ちなみにこの問題、DFSやbitDP,trit全探索(O(HW*3^HW))など、けっこういろんな解法があって面白かったです。想定もDFSでしたね。制約が小さい問題を筋肉解法で通すのも一種の実力だと思います。（TLを見ている感じだと僕の解法もかなり筋肉よりでしたけども……）
E-Filters
途中で状態が変わらない珍しいタイプのクエリ処理問題。いかにも前処理してからO(1)で解きたくなります。
以下、t=1,2,3の関数をadd関数,chmax関数,chmin関数と呼ぶことにします。
add関数がない場合を考えてみると、入力xに関わらず、chmax関数の最小値より小さい結果とはならず、またchmin関数の最大値より大きい結果とはならないことがわかります。更新が行われなかった場合は、入力がそのまま答えとなります。
また、add関数とchmin,chmax関数の合成を観察してみると、max(x+α,a)=max(x,a-α)+αという式変形が成り立つことがわかります。入力に関わらず、add関数で加算されたaだけ上下の境界が”ズレる”ということです。
よって、add関数でどれだけ加算されたかを記録しておく変数sumを初期値0で用意しておき、add関数ではsumにaiを加算、chmin,chmax関数ではaiからsumを引いたものとの比較更新を行う、という処理を前から順番に行うことで、ズレを考慮しながらchmax,chmin関数を適用することができます。
事前計算では、infと-infを代入して実際に計算する、もしくはchmin関数の最小値とchmax関数の最大値を求めることで上下の境界値が求まります。境界の外にある場合は境界まで近づけた値にsumを足したもの、境界に挟まれているもしくは境界上にある場合は入力にそのままsumを足したものが答えとなります。
上下の境界を求める部分で、上の境界が下の境界より小さくなることがありえる実装をしていたのに気が付かず、コンテスト終了直前までWAが解消できませんでした。危なかった……。
解法とクエリの中身、サンプルからなんとなく関数の形を想像できたのが大きいですね。
そんなわけで
直近7回のコンテストで6回目の青パフォです。安定してきて嬉しいな。
