AtCoder Beginner Contest 182 C,D,E,F問題メモ

AtCoder Beginner Contest 182

C - To 3

• 各桁に0が含まれない正整数 $N$ が与えられる
• （10進法で）$N$ の桁をいくつか消して残りをそのままの順序で結合する操作を考える
• 操作によって3の倍数に出来るか判定し、出来る場合は消す桁の最小個数を求めよ
• $1 \le N \le 10^{18}$

$N$ が大きい場合は各桁の和が3の倍数となることを利用する方法が速いが、 今回はたかだか18桁しかないので、実際に全部試してもよい。

Pythonなら itertools.combinations(リスト的なもの, k) で、 リスト的なものから $k$ 個選ばれる全パターンのイテレータを得られる。
並び順も元のリスト的なものの状態が保たれている。

Python3

D - Wandering

累積和と累積MAXを同時に使う面白い問題。

$i$ 回目の「操作」を「$A_1$ 進み、$A_2$ 進み、…、$A_i$ 進む」行為とし、$j$ 回目の「移動」をその操作中での「$A_j$ 進む」行為のことを指すとする。

「$C_i$: $i$ 回目の操作の前と後でどれだけ（正の向きに）進むか」は、$A_1+A_2+...+A_i$ なので各 $i$ についての値を累積和で求められる。

また、$i$ 回目の操作の移動中に「$D_i$: 初期位置から最大いくつ進んだ座標まで訪れることがあるか」というのは、

• $\max(A_1,A_1+A_2,A_1+A_2+A_3,...,A_1+A_2+...+A_i)$

なので、“累積和の累積MAX”で求められる。

「今まで進んだことのある最大座標 $p$」「操作後の座標 $q$」を持ち、各操作毎に、

• 今回の操作中に訪れる最大座標が $p$ より大きければ更新
  • $p ← q+D_i$
• 操作後の座標を更新
  • $q=q+C_i$

として $p,q$ を更新していくと、$p$ が答えとなる。

Python3

E - Akari

• $H \times W$ のマス目
• $N$ 個の電球と $M$ 個のブロックが置かれている
  • $i$ 個目の電球はマス $(A_i,B_i)$
  • $i$ 個目のブロックはマス $(C_i,D_i)$
  • 1つのマスに置かれている電球とブロックはたかだか1個
• 電球は、ブロックに阻まれるまで、上下左右の 4 方向に光を放つ
• マス目上のブロックの置かれていないマスのうち、電球の光が届くものの数を求めよ
• $1 \le H,W \le 1500$
• $1 \le N \le 5 \times 10^5$
• $1 \le M \le 10^5$

Eにしては、素直に調べるだけ、という印象。
一応、上下左右に照らされるマスを調べる過程で、それ以上調べる必要の無い条件をはっきりさせて打ち切らないとTLEになる、という工夫は必要。

○:照明  ■:壁  ─:光線

──①───②───■

このような時、各照明（①）から上下左右に照らされるマスを1マスずつ調べるが、 たとえば右方向に調べて他の照明（②）にぶつかったら、それよりさらに右は②を調べる過程で調べられるので、①からはこれ以上調べる必要は無い。

そうすることで同じマスを何度も調べること無く、$H \times W$ の各マスを、同じ方向ではせいぜい1回だけ調べればよくなる（全体で4方向なのでせいぜい $4HW$）。

また、制約を見ると照明より壁の方が数が少ないので、壁から調べることもできる。

外周を含めた各壁から同様に上下左右に調べて、他の壁または照明にぶつかったら打ち切る。
ここで探索されたマスは、たとえば左方向への探索では、「右から照らされることは無いマス」と言える。

・・○・・■・・・■・・
      ↑↑  ↑↑↑
      右方向から照らされることは無いマス

上下左右どの方向からも照らされることは無いマスが最終的に照らされないマスとなるので、全体から引けばよい。

Python3

F - Valid payments

• $A_1$ 円玉、$A_2$ 円玉、…、$A_N$ 円玉の $N$ 種類のコインがある
  • $A_1=1$
  • 各 $i$ について $A_i \lt A_{i+1}$ かつ $A_{i+1}$ は $A_i$ の倍数
• $X$ 円の商品を購入する
• $y$ 円払うと $y-X$ 円のお釣りが返る
• 以下の条件を全て満たすような支払額 $y$ が何通りあるか求めよ
  • 支払いもお釣りも、その金額をちょうど払うのに必要な最小の枚数で受け渡しを行った
  • 支払ったコインと同じ種類のコインがお釣りに含まれてはいけない
• $1 \le N \le 50$
• $1 = A_1 \lt A_2 \lt ... \lt A_N \le 10^{15}$
• $1 \le X \le 10^{15}$

日常でも、なんかボケてると必要のない硬貨を渡して店員にそのまま返されることってたまにある。

ここでは、「お釣りに含まれない一番大きいコイン」で場合分けした。

入出力サンプルからいろいろ条件を探しての解法だが、公式解説にあるような解法2の方がスマート。

まず、サンプル3のように、$X$ が $A_i$（$2 \le i$）の倍数なら、$A_i$ 未満のコインは使われない。
$y \equiv y-X \mod{A_i}$ なので、もしこれが0でなかった場合、支払いとお釣りに同じ硬貨が含まれてしまう。

かならず最小の硬貨が使われるよう、全体を上記を満たす最大の $A_i$ で割り、それ未満のコインはなかったものとする。

N=5  X=44  A=(1, 2, 4, 20, 100)
↓
N=3  X=11  A=(      1,  5,  25)

これで、置き換え後の $A_1=1$ は、ぴったり払う上で必ず使われることが保証される。

この置き換えは後続の計算を上手くやると不必要かもだが、思考する上で条件の見落としが減ってわかりやすくなる。

サンプル2では、1,5,10,50,100のコインで198円を支払う。

       
       支払いに含まれる   お釣りに含まれるコイン
198    1,5,10,50,100      -
200              100      1
203    1,        100        5
208    1,5,      100          10
248    1,5,10,   100             50

203～248は、200円をベースとして、お釣りに含まれるコインを支払い側に順次含ませることで、お釣り側を繰り上げている感じ。

すると、細かな詰めの部分はあるとしても以下の方針がとれそう。

• 支払う最小のコインを $A_i$ とし、ギリギリ $X$ を超える支払額 $y_i$、その時のお釣り $z_i$ を求める
  • $y_i=ceil(\dfrac{X}{A_i}) \times A_i$
  • お釣りには、$A_1～A_{i-1}$ のコインのみが含まれる
• お釣り側のどのコインを支払い側に含ませて、お釣りを繰り上げるかの派生パターン数を求める
• ただし、お釣りには $A_i$（以上）が含まれないようにする
• これを各 $A_i$ について合計する

$A_{i-1}$ を繰り上げると $A_i$ がお釣りに含まれてしまうため、繰り上げ可能なのは $A_{i-2}$ まで。

これで求められる派生を含めた $y$ の範囲は、お釣りに $A_i$ 以上が含まれないことから「$y_i$ 以上 $X+A_i$ 未満」となる。

$y_{i} \lt y_{i+1}$ であれば、$X+A_i \le y_{i}+A_i \le y_{i+1}$ のため、$A_{i+1}$ について求める場合の範囲「$y_{i+1}$ 以上 $X+A_{i+1}$ 未満」とは被らない。

一方、$y_{i} = y_{i+1}$ の場合は範囲が丸かぶりするが、$y_{i+1}$ の方がカバー範囲が広いため、そちらでまとめて計算することとする。

場合分けの方針は良さそうなので、派生パターンを数える。

ざっくり考えると、$A_i$ の時には、$A_1～A_{i-2}$ をそれぞれ繰り上げるか否かの $2^{i-2}$ 通りくらいあるかな？と思う。
しかし、サンプル4は、コイン枚数の割には支払い方が21種類と意外と少ない。
数字の大きさにびびらず「何枚で次のコインに繰り上がるか」「最大コインだけで支払った場合のお釣り」を観察してみる。

X = 11837029798
                 1 942454037 2827362111 19791534777 257289952101 771869856303 3859349281515 30874794252120 216123559764840
繰り上げ
枚数     942454037         3          7          13            3            5             8              7

お釣り   414872683         2          2          12            2            4             7              6

すると、$A_4$ 以降は全て繰り上げ枚数がお釣りギリギリとなっている。

つまり、$A_3$ などを支払い側に含ませてお釣りを繰り上げようとすると、連鎖的に繰り上がって最大の $A_9$ が含まれることになる。
$A_9$ については、$A_8$ のみならず $A_3～A_7$ も全て繰り上げ不可となる。

$A_2$ もギリギリのため、結局、派生は以下の2通りしかないことになる。

• $A_1$ を支払いに含めて繰り上げる。お釣りでは $A_2$ も繰り上がるため $A_3$ が1枚増える
• $A_2$ を支払いに含めて繰り上げる。お釣りでは $A_3$ が1枚増える

また、お釣りが0枚のコインも、繰り上げられない。（繰り上げ枚数の分だけコインを追加することになり、それなら $A_{i+1}$ 1枚で払うことになる）
ただし、下の桁から繰り上がってきた1枚があれば、追加するのは(繰上げ枚数-1)枚となり、繰り上げられる。

このように、下の桁からの繰り上げの有無で遷移が変わるのは、桁DPを想起させる。

• $DP[i][j:0/1]=$ 小さい方から $A_i$ までで、$j=0/1$：上の桁への繰り上がり無し/ありの場合のパターン数

とすると、お釣りが「0枚」「繰り上げ枚数ギリギリ」「それ以外」で遷移が変化する。

お釣り
       0       繰り上げギリギリ    それ以外
     i   i+1      i   i+1          i   i+1
j=0  o → o       o → o           o → o
       ↗           ↘               ×
j=1  o → o       o → o           o → o

最終的に $A_i$ まで繰り上がってくるパターンが不可なので、繰り上がりのない $DP[i-1][0]$ が $A_i$ に対しての派生パターン数となる。

まとめると、

• 前処理する
• $A_i$ 以上のお釣りを含まない最小の金額 $y_i$ を求める
• お釣り $y_i-X$ の構成を求める
• $DP[0][0] = 1, DP[0][1]=0$ からはじめて派生パターン数を求める

これを合計すればよい。ただし、$y_i=y_{i+1}$ となる $i$ については合計しない。

Python3

要は、「$C_1A_1+C_2A_2+...+C_NA_N=X$ となる整数の組 $(C_1,C_2,...,C_N)$ は何通りですか」という問題で、 $C_i$ が正ならその枚数だけ支払い、負ならお釣りに用いると考えると問題のシチュエーションに当てはめられる。

ただし各 $C_i$ の絶対値には上限があり、 1段階大きいコインで表現できてしまう枚数（$\dfrac{A_{i+1}}{A_i}$）以上は使うことが出来ない。

この上限制約があるため、$A_1,A_2,...,A_{i-1}$ の全てを上限まで使っても $A_i$ 未満にしかならない。

また、以下のようにどちらからどちらの変換へも1通りに決まるので、$C_i$ の組と $y$ は1対1対応とわかる。

• $y$ を決めれば支払いとお釣りは1通りに決まる
• $(C_1,C_2,...,C_N)$ を決めれば当然、$y$ は1通りに決まる

以上を踏まえて $C_i$ を $i$ の大きい方から考えると、各コイン、支払う可能性のある枚数というのは、

• $X$ をちょうど払える場合、1通り
• $X$ をちょうど払えない場合、以下の2通り
  • $X$ にギリギリ足りない（あと+1すれば超える）
  • $X$ をギリギリ超える（あと-1すれば足りなくなる）
  • ただし（絶対値で）上限を超える枚数は不可

で、ちょうど払えない場合は端数を1段階小さいコインで表現する方法を考えれば、再帰的に解ける。

もしこれ以外の枚数だと、端数の絶対値が $A_i$ 以上ということになり、$A_1～A_{i-1}$ では表現できないため、不可能。

一見、2通りずつに分岐するので状態数が $2^N$ とかになってしまいそうだが、 実は以下のように多くの状態が同じになり、メモ化すれば $2N$ 程度にしかならない。

• $X=198$ を100円で
  • ギリギリ足りない: 1枚→$X=98$
  • ギリギリ超える: 2枚→$X=-2$
• $X=98$ を50円で
  • ギリギリ足りない: 1枚→$X=48$
  • ギリギリ超える: 2枚→支払いが上限を超えるため不可
• $X=-2$ を50円で
  • ギリギリ足りない: -1枚→$X=48$
  • ギリギリ超える: 0枚→$X=-2$

(100×1, 50×1 の支払い)と、(100×2 の支払い, 50×1のお釣り)とで、端数48が同じになる。

Python3