2022-02-28 アルゴリズムと数学 演習問題集 058, 059, 060, 061 を解いた
アルゴリズムと数学 演習問題集 057 は難しそうなのでスキップ (今日は気力がない) 。
アルゴリズムと数学 演習問題集 058 - Move on Squares 1 を解いた。
問題: https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_ax
例題。まず負の数の場合も (0,0) からの距離は変わらないので X, Y をそれぞれの絶対値で考える。
(X,Y) まで移動するためには X + Y はないと届かない。 X + Y を超える場合は左右に往復することで回数を消費できる。ただし N と X + Y の偶奇が一致しないと (X,Y) に N 回ちょうどで止まることはできない。
提出: https://atcoder.jp/contests/math-and-algorithm/submissions/29774053
アルゴリズムと数学 演習問題集 059 - Power of Two を解いた。
問題: https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_ay
例題。書き出してみると 1 の位は 1, 2, 4, 8, 6, 2, 4, 8, 6, ... と変化することに気づく。 0 はないので 2, 4, 8, 6 だけを繰り返す。あとは [2, 4, 8, 6][(N - 1) % 4] でおしまい。
2^1 % 10 = 2
2^2 % 10 = 4
2^3 % 10 = 8
2^4 % 10 = 6
2^5 % 10 = 2
2^6 % 10 = 4
2^7 % 10 = 8
2^8 % 10 = 6
提出: https://atcoder.jp/contests/math-and-algorithm/submissions/29774397
アルゴリズムと数学 演習問題集 060 - Stones Game 1 を解いた。
問題: https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_az
例題。残り 1 個のときの先手番のときどちらが勝つか、残り 2 個のとき……と書き出して規則性を調べる。
1 : First
2 : First
3 : First
4 : Second
5 : First
6 : First
7 : First
8 : Second
3 個までなら調整して相手に負ける手番を押し付けられる。 3 個勝ちが続いて 1 個負けを挟む 4 個周期になる。
提出: https://atcoder.jp/contests/math-and-algorithm/submissions/29775495
アルゴリズムと数学 演習問題集 061 - Stones Game 2 を解いた。
問題: https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_ba
060 と同様に書き出してみる。残り 1 個のときの手番側は最大 0 個しか取れないので負け。残り 2 個のときは最大 1 個取れるので相手に残り 1 個 (負け) を押し付けて勝ち。この調子で数える。取れる個数の最大値までに 1 回でも負けになるものがあれば押し付けて勝てる。
1: false 0
2: true 1
3: false 1
4: true 2
5: true 2
6: true 3
7: false 3
8: true 4
9: true 4
10: true 5
11: true 5
12: true 6
13: true 6
14: true 7
15: false 7
16: true 8
17: true 8
18: true 9
19: true 9
20: true 10
21: true 10
22: true 11
23: true 11
24: true 12
25: true 12
26: true 13
27: true 13
28: true 14
29: true 14
30: true 15
31: false 15
1, 3, 7, 15, 31
+2 +4 +8 +16
規則性を見ると false (負け) になる位置は 1, 3, 7, 15, 31, ... となる。これは 2 の累乗ずつ増えていることが分かる。倍々になっていくので 10^18 でも大した回数にはならないので前から順に負けになる位置を調べていけば良い。
提出: https://atcoder.jp/contests/math-and-algorithm/submissions/29775495
今日のコミット。