AtCoder Beginner Contest 179をPythonで解く

こんにちは, Shinoryoです.

今回はAtCoder Beginner Contest 179を, Pythonで解いてみた結果を書き連ねていこうと思います.

AtCoder Beginner Contest 179 - AtCoder

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

A - Plural Form

文字列に対して, リストのように[1]や[2], [-1]等をつけることによって, ○文字目の文字を抽出することができます.

B - Go to Jail

問題文にあるゾロ目の条件を順に確かめればよいです. ループの条件に注意しましょう.

C - A x B + C

$A \times B < N$を満たす自然数の組$(A, B)$に対して, ある自然数$C$を適当に選ぶことで$A \times B + C = N$となります. ゆえに, 自然数の組$(A, B)$に関してだけ気にすればよいです.

$A$を固定した場合, $A \times B < N$を満たす$B$は$\left\lfloor \frac{N-1}{A} \right\rfloor$個だけあります(ただし, $\lfloor \ \rfloor$はGauss記号で, $\lfloor x \rfloor$は$x$を超えない最大の整数です). それを$A = 1$から$A= N - 1$まで足し上げればよいでしょう.

D - Leaping Tak

動的計画法(dynamic programming)による簡単な解決方法として, 以下のようなものが考えられます.

1. $[L_i , R_i]$の和集合として$S$を作る.
2. 配列dpを, 「dp[i]：$(i + 1)$番目のマス目に到達する場合の数」として定義する.
3. dp[0]に関して, $1$番目のマス目に到達する場合の数は「高橋君は現在マス$1$にいる」という意味で$1$通りとする.
4. $1$番目のマス目から$(N - 1)$番目のマスに関して, 集合$S$で定められた$d (\in S)$マス分の移動移動を試す. その際, $i$番目のマス目に到達する場合の数を$(i + d)$番目のマス目に到達する場合の数に加えていく.

最終的に, 配列dpに「dp[i]：$(i + 1)$番目のマス目に到達する場合の数」が入るようになります. しかし, これでは計算量が$O(N^2)$(集合$S$の要素数も高々$N$個存在する)になってしまうので, TLE.

これを解決する方法については, まだ私の理解が追い付いていないので記載しません. 理解できたときに記載します.

E以降

E以降は私の能力不足故に省略いたします.

参考にしたサイト等

• 「解説 - AtCoder Beginner Contest 179」
  Editorial - AtCoder Beginner Contest 179

  AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

• Tomotaka Ito様の「Python文字列操作マスター」
  Python文字列操作マスター - Qiita

  Pythonにおける基本的な文字列操作をまとめました. 経験豊富な人には物足りない内容かもしれませんが... (追記2018.12.23: print の文法をPython3対応にしました. Python2でコピペしたコードが動かない場...

• マスオ(難波博之; 高校数学の美しい物語)様の「ガウス記号の定義と３つの性質」
  ガウス記号の定義と３つの性質

  ガウス記号の定義. および覚えておくと役に立つガウス記号の性質を３つ紹介. その証明も解説します.