AtCoder Beginner Contest 178
2020-09-13
コンテスト中に挑戦した問題についての感想とか.
A - Not
(logxor 0 1) ; => 1
(logxor 1 1) ; => 0
のことを忘れていたので, 入力が0かどうかを判定した.
B - Product Max
最大値は端点のどこかであるので, 4通り試せば良い.
C - Ubiquity
- すべての数字を使った数列の数は, 10のn乗個 (A)
- 9以外の数字を使った数列の個数は, 9のn乗個 (B)
- 0以外の数字を使った数列の個数は, 9のn乗個 (B)
- 0と9以外の数字を使った数列の個数は, 8のn乗個 (C)
AからBを2回引くとCのぶんだけ引きすぎるので, Cを足すと答えが出る.
大きな数が出てくるので, 剰余の処理はうまく書いておく. (特に累乗について.)
D - Redistribution
数列の全ての項が3以上なので, n項ある場合, (- s (* 3 n))が負になるnについては,
そのような数列は存在しない.
以上のことから, 数列が存在する範囲のnは上限が決まるのでそれらについて考える.
全ての項から3を引くと, 全ての項は0以上の数となり, それらの総和は(- s (* 3 n))である.
なので, (- s (* 3 n))個のものの間に(- n 1)個の仕切りをどのように配置するかという問題になる.
仕切りは隣接していても良いことを考えると,
(- s (* 2 n) 1)個のものから(- n 1)個のものを選ぶ組み合わせの数になる.
この際に階乗を計算するが, これは事前に計算しておくと良い.
E - Dist Max
WIP
F - Contract
WIP