Open4
プ力貧弱マンのatcoder 勉強備忘録
Mo_ny0主旨
- 解いた問題、参考にしたページなどを記録
- 新しく知ったことなどをメモ
Mo_ny0C - Yamanote Line Game
メモ
- flushてなんぞ？
- https://hydrocul.github.io/wiki/programming_languages_diff/io/flush.html
- バッファリングしてる出力云々を無理やり出させる方法のこと？
- ランダムにリストから要素を選択
-
randomモジュールのchoice()で可能
-
- リストから一致する要素を削除
-
remove()を使う。ただしこいつは引数と一致する値のうちリストの中で最初のものを除く。
-
解答
import random
N = int(input())
arr = [x for x in range(1, 2 * N + 2)]
while len(arr) > 0:
tkhs = random.choice(arr)
arr.remove(tkhs)
print(tkhs, flush = True)
aok = int(input())
arr.remove(aok)
print(0)
解説
Mo_ny0C - Choose Elements
メモ
- 全探索でやったらとんでもない計算量になるじゃんと頭を抱える。結局自分で解けず。
- どうやら**動的計画法(Dynamic Programming)**なるもので解くのが一般的らしい。
- ビット演算子のことをちゃんと理解してなかった()
解答
N, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
dp_a = [False] * N
dp_b = [False] * N
dp_a[0], dp_b[0] = True, True
for i in range(N - 1):
if dp_a[i]:
dp_a[i + 1] |= abs(A[i] - A[i + 1]) <= K
dp_b[i + 1] |= abs(A[i] - B[i + 1]) <= K
if dp_b[i]:
dp_a[i + 1] |= abs(B[i] - A[i + 1]) <= K
dp_b[i + 1] |= abs(B[i] - B[i + 1]) <= K
if dp_a[N - 1] or dp_b[N - 1]:
print("Yes")
else:
print("No")
C - Collision 2
メモ
-
index()は引数と一致する要素の先頭のインデックスを持ってくる。- 指定した値と一致するすべての要素のインデックスを持ってくるにはリスト内方表記を使う
h_idx = [i for i, x in enumerate(y_pos) if x == h]
- 同じy座標にある人同士のインデックスを持ってきて、その人らが向き合っていれば衝突すると判定するようなプログラムを書いたら一部不正解したとともにTLEを起こした。計算時間にも気を配らなければならない。
- 結局解説を読んだ