Atcoder 灰diff埋め ABC083C~100C 振り返り
灰diff埋めは簡単な問題が多いためテンポ良く大量に解いていこうと思っていましたが初期の問題は意外に難しい問題が多く……
ABC086 C - Traveling【AC】
迷路の問題を解くように幅優先探索で解こうとすると,t=10^5もあるため間に合いません.この移動は同じ場所に留まる事が出来ない事を利用して,各時刻に対してO(1)で求めることが出来ます.
時刻0で(0, 0)におり,時刻が1増えるごとにxかyのどちらかに-1か+1移動します.つまり,時刻1では(1, 0), (-1, 0), (0, 1), (0, -1)のどれかにいることになります.このことから,時刻の偶奇とx+yの偶奇が一致することが分かります.時刻1ではどう頑張ってもx=2の所に移動出来ませんし,時刻2ではどう頑張っても(1, 0)に移動出来ません(同じ場所に留まる事が出来ないため)
そのため,まず時刻の偶奇とx+yの偶奇をチェックすれば良いです.しかし,例えば時刻2で(100, 100)という場合このチェックでは正しくありません.偶奇は合っていても距離が届かない場合をチェックする必要があります.これは現在の時刻とx, yの地点の差を求めれば良いです.x, y地点の方が現在の時刻より多ければ,最短で移動しても届かないのでNoとなります.
pre_t = 0 pre_x = 0 pre_y = 0 for _ in range(int(input())): t, x, y = map(int, input().split()) if t % 2 != (x+y) % 2 or t - pre_t < abs(x - pre_x) + abs(y - pre_y) : print("No") break pre_t = t pre_x = x pre_y = y else: print("Yes")
ABC100 C - *3 or /2【AC】
最大で何回できるか求める必要があります.3倍すると言う操作は無限にする事が出来るので考える必要がありません.必ずどこかの数字は2で割る必要があり,数字は整数である必要があるため,なるべく2で割る操作を少なくすることが最大回数を求めることになります.なるべく少なくするので,1回の操作で2で割る数字は一つのみで他は3倍する操作をした方が良いです.結果,各数字で何回2で割る事が出来るかを数えればよいことが分かります.もし3倍で無く偶数倍だったら,無限に操作ができてしまいます.
N = int(input()) A = [int(i) for i in input().split()] ans = 0 for a in A: while a % 2 == 0: a /= 2 ans += 1 print(ans)