AtCoderBeginnerContest165復習＆まとめ（前半）

AtCoder ABC165

2020-05-02(土)に行われたAtCoderBeginnerContest165の問題をA問題から順に考察も踏まえてまとめたものとなります．
前半ではABCDまでの問題を扱います．
問題は引用して記載していますが，詳しくはコンテストページの方で確認してください．
コンテストページはこちら
公式解説PDF

A問題　We Love Golf

問題文
ジャンボ高橋君はゴルフの練習をすることにしました。
ジャンボ高橋君の目標は飛距離を$K$の倍数にすることですが、ジャンボ高橋君の出せる飛距離の範囲は$A$以上$B$以下です。
目標の達成が可能であれば"OK"と、不可能であれば"NG"と出力してください。

ぱっと問題を読んだときは，$K$の倍数以上飛ばす的な問題で，不等式使うのかなと思ったら，まさかの飛距離を$K$の倍数にできるかって問題でしたね．
とりあえず，制約も$1 \leq A \leq B \leq 1000$なのでfor文使って解く実装をしました．
以下が提出したコードです．

abc165a.py

k = int(input())
a, b = map(int, input().split())
flag = 0
for i in range(a, b + 1):
    if i % k == 0:
        flag = 1
        break
if flag == 1:
    print("OK")
else:
    print("NG")

ただ，制約の範囲が仮にとても広い場合，for文で探索してると間に合わないので，解説記事を参考に，

$B$以下の最大の$K$の倍数を求め，それが$A$以上かどうか確かめる方法

での解き方も，終わったあとに実装してみました．
以下が実装し直したコードです．

abc165a.py

k = int(input())
a, b = map(int, input().split())
x = b // k * k
if a <= x:
    print("OK")
else:
    print("NG")

正直，D問題を解くまでの速さを競っている段階なので，とりあえずA問題とかは，一番最初に思いついた方法でコンテスト中は解くようにしています．
pythonの演算子//は，割り算した結果の小数点以下切り捨てした整数を出すことができるため，x = b // k * kの計算により，xはb以下の最大のkの倍数になります．

B問題　1%

問題文
高橋くんはAtCoder銀行に$100$円を預けています。
AtCoder銀行では、毎年預金額の$1$%の利子がつきます(複利、小数点以下切り捨て)。
利子以外の要因で預金額が変化することはないと仮定したとき、高橋くんの預金額が初めて$X$円以上になるのは何年後でしょうか。

$X$の制約が$10^{18}$まであるのを見て，最初かなり焦り，工夫を考えようとしましたが，よくよく考えたら$10^{18}$でも$10000$年以内くらいには，到達する気がして実装して，確かめたら3760年でした．
余裕やんと思って，提出前に例を確かめてようとしたら，例2の入力が$10^{18}$でしたね．
最初に見ておけば，少し解くまでの時間を縮めることができたかもしれないです．
以下が実装したコードです．

abc165b.py

x = int(input())
y = 100
for i in range(1, 10000):
    y = int(y * 1.01)
    if y >= x:
        print(i)
        break

C問題　Many Requirements

問題文
正整数$N, M, Q$と、$4$つの整数の組$(a_i, b_i, c_i, d_i)Q$組が与えられます。
以下の条件を満たす数列$A$を考えます。
　・$A$は、長さ$N$の正整数列である。
　・$1 \leq A_1 \leq A_2 \leq ⋯ \leq A_N \leq M$
この数列の得点を、以下のように定めます。
　・$A_{b_i}−A_{a_i}=c_i$を満たすようなiについての、$d_i$の総和 (そのような$i$が存在しないときは$0$)
$A$の得点の最大値を求めてください。

$O(?)$をしっかり計算できる余裕がコンテストのときはありませんでした．
もう少し問題量解いて，全探索できるかどうかの感覚身に着けたいところです．
解くための方法を考えていたら，時間なくなってきたので，"TLE"覚悟で全探索に切り替えて実装したら通りました．
とりあえず，実装し提出したコードです．

abc165c.py

n, m, q = map(int, input().split())
dict_list = {}
key_list = []
for i in range(0, q):
    a, b, c, d =  map(int, input().split())
    key = tuple([a, b, c])
    key_list.append(key)
    dict_list[key] = d 
def func(i, k, a_list):
    if k == 0:
        temp_score = 0 
        for key in key_list:
            if key[2] == a_list[key[1]-1] - a_list[key[0]-1]:
                temp_score += dict_list[key]
        return temp_score
    k = k - 1
    max_score = 0
    for j in range(i, m + 1):
        max_score = max(func(j, k, a_list + [j]), max_score)
    return max_score
score = 0
for i in range(1, m + 1):
    score = max(func(i, n - 1, [i]), score)
print(score)

昇順となるような数列$A$は，再帰関数を使って，全パターン作成し，最大スコアを返すようにしました．
今回は実装よりも，条件を満たす数列が${}_{N+M−1} C _N$通り存在する部分を少し書いておけたらと思います．
この系統の問題は高校の数学も問題集に必ず載っている問題で高１が苦戦し始める問題ですよね．
数字を一列に並べる問題に見えるので$P$を使いたくなりますが，$C$を使って通り数を求めることができる問題です（模試とかにもよく出てた気がする）．

公式の解説と少し，考え方が違いますが，自分の解釈としては，$N$個のボールと$M-1$の仕切りで考えて，それらを一列に並べることをまず考えます．
これは，ボールと仕切りの数を合計し，$(N + M - 1)!$通りに並べることがまずできますが，重複が存在するため$N!$と$(M-1)!$で割る必要があります（よくある重複文字を含む順列の問題）．
したがって，

\frac{(N + M - 1)!}{N!(M - 1)!} = {}_{N+M−1} C _N

となるため，$C$を使って通り数を求めることができます．
なぜ，$N$個のボールと$M-1$の仕切りを一列に並べる通り数と，昇順となるような数列$A$の数を求められるのか，具体的に$N=6, M=8$のときを例に説明していきます．

例１ ○|○|○|○||○||○

左の○から順に，$A_1, A_2,...,A_N$を示していると思ってもらえれば大丈夫なので，例１は
$A_1|A_2|A_3|A_4|　|A_5|　|A_6$
と考えることができます．
そして仕切りによって，仕切りは左から順に，1と2の境，2と3の境，...，7と8の境ととらえることができます．
仕切りに着目して考えると，
1の部屋|2の部屋|3の部屋|4の部屋|5の部屋|6の部屋|7の部屋|8の部屋
と捉えることができます．
したがって，例１によって数列$A$は，5の部屋と7の部屋が空っぽなので，
$A=[1,2,3,4,6,8]$
の数列を表していることになります．

例２ |○||○○|○|○○||

例１と同様に考えると，1, 3, 7, 8の部屋が空っぽで，4, 6の部屋に2つ入っているので，数列$A$は，
$A=[2,4,4,5,6,6]$
の数列を表していることになります．
このように，考えられる昇順の数列は，○と|を一列に並べる通り数と等しいことがわかります．

塾講師やってると高１からよくこの問題を質問されるので，けっこう躓きやすいところですよね．

D問題　Floor Function

問題文
整数$A, B, N$が与えられます。
$N$以下の非負整数$x$に対する$floor(Ax/B)−A×floor(x/B)$の最大値を求めてください。
ただし、$floor(t)$とは、実数$t$以下の最大の整数のことを表します。

とりあえず，全列挙できないとは思いつつ，全探索のプログラム提出して"TLE"でした（D問題でこんな実装が簡単な全探索出るはずないよな汗）．
そのあとに数式見て，わかったことから場合分けしたら，問題なく解けました．
コードのif文の順番は，コンテスト本番のときに場合分けした順番通りに書かれています．
$floor(Ax/B)$が広義単調増加であることはすぐにわかったので，まず$N < B$で場合分けしました．
これは，$floor(x/B)=0$となり，考えやすいので，思いつきやすいかなと思います．
広義単調増加であることから，$X=N$が最大となることがわかります．
次に$N = B$は，$floor(Ax/B)−A×floor(x/B)=0$になることが，代入することで明らかだったので，$X=N-1$が最大となることがわかります．
その後も，具体的に$X=B-1$などを代入して考えることで，$A$と$B$の大小で場合分けをすることで，以下のコードを書いて提出し，"AC"を出すことができました．

abc165d.py

a, b, n = map(int, input().split())
max_score = 0
if n < b:
    max_score = int(a * n / b) - a * (n // b)
elif n == b:
    max_score = int(a * (n-1) / b) - a * ((n-1) // b)
elif a <= b:
    max_score = a - 1
elif a >= b:
    max_score = int(a * (b-1) / b) - a * ((b-1) // b)
print(max_score)

解説みるとすごくシンプルな結論になってて，自分の実力不足を感じました．
解説の結論を実装すると以下のようなコードで書けました（圧倒的に短い）．

abc165d.py

a, b, n = map(int, input().split())
x = min(b - 1, n)
print(int(a * x / b) - a * (x // b))

前半はここまでとなります．

今回のコンテストはABD問題まで解いた後，C問題が全探索の問題と気づかず，どうやってとけばいいかに時間を費やし過ぎてしまい，EやF問題に使える時間がなかったので，まずはD問題までを40分くらいで解けるようになりたいですね．
とりあえず前半の最後まで読んでいただきありがとうございました．

後半はEF問題の解説となります．
後半に続く予定．