AtCoder Beginner Contest 166 [ D - I hate Factorization ]をPythonで解く（400点、🟫茶diff）
問題
解説
A5 - B5 = X
で、Xの制約条件が
1 <= X <= 109
ゆえに、Aは大体1000くらいまでだろ？
という当たりをつける。
Bは負の値もありえるので、-1000から1000までの範囲で総当たりをかける。
実装
素直に計算したのが、実行時間70ms。
はまやん氏のコードを元にしたdictでキャッシュする実装が72ms。
意外に素直に計算のほうが速い。
はまやん氏バージョン
AtCoder Beginner Contest 167 [ D - Teleporter ]をPythonで解く（400点、🟫茶diff）
問題
解答
周期性を利用したコードでAC。
なかなか難しかった。
感想
dpを使ったダブリングが想定解答。
こっちもやってみたいが、一回力尽きたので後ほど。
実装
参考
AtCoder Beginner Contest 168 [ D - .. (Double Dots) ]をPythonで解く（400点、🟩緑diff）
問題
解答
BFS(幅優先探索)で、あっさり解ける。
BFSの探索をかけて、ans[i]に部屋iの一個前の部屋番号を記録。
ansが一通り揃っているなら、"Yes"の後にまとめて表示。
感想
問題読んで、dfsかbfsだろうな？とは思うが、どっちだろう感ある。
競プロの考察方針の一つとして、典型問題に似ていないかという糸口がある。
今回は、今いる部屋から最短距離で部屋1にたどり着くという条件があるが、最短距離はどのくらいになるだろう。
全ての部屋から部屋1にたどりつくための最短距離を考えたいが、移動が双方向に可能なことから、
部屋1から各部屋にたどりつくための最短距離を考えるのと実質同じであることが言える。
このある始点から移動コスト1で移動したときの最短距離を求めるのは、典型問題であり、
BFSで解けることが知られている。
とあるので、移動コスト指定がとくに無い最短距離問題はBFSと考えて良いのだろうか？
実装
AtCoder Beginner Contest 211 [ C - chokudai ]をPythonで解く（300点、🟫茶diff）
AtCoder Beginner Contest 165 [ D - Floor Function ]をPythonで解く（400点、🟫茶diff）
問題
解法
計算式を関数に実装し、試しに数値を入れてみて答えに規則性があるかどうかを見てみる。
すると、mod Bでループしていることがわかる。
よって、最大値の候補はx = Nかx = B-1。
それぞれの値の答えを求めて比較。
答えとする。
B-1 <=Nかどうかは、チェックする。
実装
参考
xを[0,N]に動かして何か発見が無いか探してみる。
すると、計算式の値はmod Bで周期性があるみたいだ。
AtCoder Beginner Contest 165 [ D - Floor Function ]をPythonで解く（400点、🟫茶diff）
問題
解法
計算式を関数に実装し、試しに数値を入れてみて答えに規則性があるかどうかを見てみる。
すると、mod Bでループしていることがわかる。
よって、最大値の候補はx = Nかx = B-1。
それぞれの値の答えを求めて比較。
答えとする。
B-1 <=Nかどうかは、チェックする。
実装
参考
xを[0,N]に動かして何か発見が無いか探してみる。
すると、計算式の値はmod Bで周期性があるみたいだ。
