AtCoder Beginner Contest 179 A, B, C ( Python )

昨日(2020/09/19)に開催されたAtcoder Beginner Contests 179のA ,B ,C について紹介したいと思います。

コンテスト結果

自分のコンテストリザルトはこのような結果となりました。

ABC179の結果画像


コンテストを振り返って

久しぶりにA~Cまでノーペナで全完して、Dはさっぱりわからなかったので、Eに1時間以上かけましたがあと数分という所でコンテストが終了してしまいました。Eはコンテスト中では1度もACしたことがないのでしてみたいものですね(^_^)
また、昨日のコンテストで茶コーダーになることができました。色変の記事については現在書いている最中なので、もう少し時間をください(焦)




A - Plural Form(100点)

atcoder.jp
文字の末尾がsならesを足す、s以外ならsを足すだけ。問題文の通りに実装しましょう。

B - Go to Jail(200点)

atcoder.jp
N回分全探索すれば良いです。最初から順に調べていって、3連続以上連番になら "Yes"、そうでなければ "No" をprintしてあげましょう。
ただ、コンテスト中は焦ってしまったので提出コードはとても汚いです。()

C - A x B + C(300点)

atcoder.jp
最初見たときは「こういうの苦手だから時間かかりそう。」が第一印象でした。


迷ったときはまずは具体例を考える。
N = 2の時、(A, B, C) = (1, 1, 1)の1通り。
N = 3の時、(A, B, C) = (1, 1, 2),(1, 2, 1),(2, 1, 1)の3通り。(入力例1)
N = 4の時、(A, B, C) = (1, 1, 3),(1, 2, 2),(1, 3, 1),(2, 1, 2),(3, 1, 1)の5通り。
N = 5の時、(A, B, C) = (1, 1, 4),(1, 2, 3),(1, 3, 2),(1, 4, 1),(2, 1, 3), (2, 2, 1),(3, 1, 2),(4, 1, 1)の8通り。


これだけではいまいち分からなかったので数学的に考えてみます。
掛け算は範囲を絞りやすいので掛け算に注目すると、
 A*B + C = N
 ⇔A*B = N - C < N
 ⇔A*B < N
という結果が得られます。


ここでまた具体例
(例)N = 100の時
A =1の時、B = 1~99までで、その時のCは99~1で99通り。(Cは1ずつ減少)
A =2の時、B = 1~49までで、その時のCは98~2までの49通り。(Cは2ずつ減少)
A =3の時、B = 1~33までで、その時のCは97~1までの49通り。(Cは3ずつ減少)
A =4の時、B = 1~24までで、その時のCは96~4までの49通り。(Cは4ずつ減少)
A =5の時、B = 1~19までで、その時のCは95~5までの49通り。(Cは5ずつ減少)
...
...
A =98の時、B = 1~2までで、その時のCは1,2の2通り。(Cは1ずつ減少)
A =99の時、B = 1のみで、その時のCは1の1通り。


つまりこの結果からAを固定したらBは(N-1)//A通りの選び方があるということです!
したがって、数式だと

\displaystyle{
\sum_{i=1}^{N-1} (N-1)//i
}
のように表せます。

最後に

あまり記事を書いていないので、見づらいと思います…(字が多いよな)
徐々に書けるようにしていくのでこれからもよろしくお願いします。