blog.bouzuya.net

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 を超える場合は左右に往復することで回数を消費できる。ただし NX + 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


今日のコミット。