なかけんの競プロノート
🕒 2021/03/21 🔄 2021/06/14

ABC196感想戦

🦋

AtCoder Beginner Contest 196 に参加しました。結果は、Eまで解けたものの、DでWAを結構出しました。画像はコンテスト中に書いたメモです。

Aは、a以上b以下の整数xとc以上d以下の整数yを選んでx-yを考えるとき、この値の最大値を求める、という問題。xは一番大きいb、yは一番小さいcを選べばいいだけ。1分。

Bは、Xが与えられるので、小数点以下を切り捨てた値を答える問題。これ、はじめ、「小数点以下を四捨五入する」と誤読していて、「めっちゃめんどくさいな」と思ってしまった。途中まで書いてて、「これ、Bの難易度じゃないだろ」と思って読み返してようやく誤読に気づく。時間をロスし過ぎた。ここまでで5分。

Cは、N以下の数で、偶数桁であり、前半と後半が等しいものがいくつあるかを数える問題。Nは$10^{12}$未満なので直接調べるのは無理だけど、繰り返される部分を全部見るなら多くても$10^6$個チェックするだけなので、ぜんぶ見ても間に合う。

数$i$の桁数を$d$としたとき、$i+10^d\\times i$が$N$以下かどうかをチェックする、というコードをまじめに書いた（提出 #21076341）。数字を文字に、文字を数字に変換するコードがわからなかったんだけど、これ知ってたらめっちゃ短く書けるなぁ（C - Doubled 解説）。実装力のなさよ。ここまでで13分。

Dは、縦H、横Wの長方形の領域に、2x1の長方形をA個、1x1の正方形をB個並べる方法の総数を答える問題。HWは16以下と小さい。

まったくどうするかわからなくて、DPっぽいけど書き方がわからず、DFSっぽいけど書き方がわからず。どうやって2x1を選んだときの突き出たほうのマスを管理すればいいのか、わからなかった。

で、思いついたのが、壁を壊すやり方。

HxWのマスのうち、2つのマスに共有されている辺を考えます。このうち、A個をぶち壊して、2x1をA個作れるか考える、という方法。各マスについて、4辺のうち壊された辺が1個以下になっていればOKで、2個以上壊されているセルが一つでもあるとダメ。これを全部調べればいいんじゃないかと。

辺の数は全部で24個あって、Aは最大で8であり、 ${}_{24}\\mathrm{C}_8$は70万くらいらしいので間に合いそう。ということで書いた（提出 #21094560）。壊す壁がないときの処理でミスって、WAを連発してしまった。ここまでで63分。

あと40分を切っているのでもうダメそうな気がするし、Eがあまり解かれてないので難しそうだったけど、Eを一応考え出す。

関数がN個あって、初期値がQ個ある。この関数N個を合成した関数によって、各初期値はどのような値になるかを答える問題。関数の数も初期値の個数も $2\\times 10^5$ある。また、関数は、$a_i$ との和、 $a_i$ とのmax、 $a_i$ とのminの3種類のどれかしかない。

個人的にはこれはDよりも解きやすくて、見た瞬間に方針が浮かんだ。各初期値の最小値をLow、最大をHighで表すとすると、$a_i$ を足すのは区間全体をスライドさせるだけ。$a_i$とのmaxをとるのは、区間の下の方を縮める処理。$a_i$ とのminをとるのは、区間の上の方を縮める処理に対応。なので、当初のLowとHighがどこへいくかだけを追いかければいい。

もし、Lowが最終的にLow1に行ったとする。maxとminを考慮しなかったらLow2に行ってたとすると、LowからLow+(Low1-Low2)までの初期値は全部Low1に行ってしまう。High側も同様に考えられる。で、maxとminでひっかからなかったところは、 $+a_i$ されるものが全部適用されるので、合計を足せばいいだけ。これで提出（提出 #21101186）。87分。Dよりもぜんぜん早く解けた。

Fは見たけどできる気がしなかったので、早く終わってくれ、って願いながら終了。