はじめに
今週も無念の2完。
成績：AB2完(300)
A
xがA内にあればYes。
A
n = int(input())
A = list(map(int,input().split()))
x = int(input())
if x in A:
print('Yes')
else:
print('No')
珍しく簡単。
B
#の位置と数を数えて偶数だったら出力する。
B
s = input()
cnt = 0
ans = []
for i in range(len(s)):
if s[i] == '#':
cnt += 1
ans.append(i+1)
if ans and cnt % 2 == 0:
print(*ans, sep = ',')
ans = []
急にカンマ区切りと言い出したのは何なのか。
C
問題文が複雑！すべてを混ぜた状態から一つずつ取り除いていき、状態0にたどり着けばOKと考えた。各状態からの遷移先はビットの1を順番に1つずつ0に変更しておけばよいわけで、それを再帰で実装しようとした。
が、WAもTLEもいっぱいあるという結果に。
C_WA
t = int(input())
def dfs(cond,n,s):
if cond == '0' * n:
print('Yes')
return True
for i in range(n):
if cond[i] == '1':
#cond[i]を0に更新したものをnew_condとする。
num = int(cond,2) - (2**(n-i-1))
new_cond = bin(num)[2:].zfill(n)
if s[num - 1] == '0':
if dfs(new_cond,n,s):
return True
print('No')
return False
for _ in range(t):
n = int(input())
s = input()
dfs(bin(2**n - 1)[2:],n,s)
再帰でやった場合一つの状態が複数回登場することになるので、そこで効率が落ちていると思われる。
終了後Twitterで解法を見ていたところBFSでやったと言ってる人が多かったのでそれで実装すると通った。
C_AC
from collections import deque
t = int(input())
for _ in range(t):
n = int(input())
s = input()
s = '0' + s
G = [[] for _ in range(2**n)]
for num in range(2**n):
if s[num] == '1':
continue
bit = bin(num)[2:].zfill(n)
for i in range(n):
if bit[i] == '0' and s[num + 2**(n-i-1)] == '0':
G[num].append(num + 2**(n-i-1))
#で、このGで頂点2**n-1に到達できるかをBFS。
start = 0 #スタート地点となる頂点の番号
visited = [False]* (2**n) #既に訪れた頂点のリスト
todo = deque([start]) #今後探索予定である頂点のリスト。先頭から処理するのでdeque
while len(todo) > 0:
v = todo.popleft() #todoの末尾にある頂点をこれから探索するのでvに代入して消去する。先頭を消去するのでpopleft
if visited[v] == False:
visited[v] = True #もしこれまでにvを訪れていなければ訪れたことを記録。
for w in G[v]: #vに隣接している点のうち、
if visited[w] == False:
todo.append(w) #探索予定に入っていないものがあれば探索予定に入れる。
if visited[2**n - 1]:
print('Yes')
else:
print('No')
$2^n$通りの状態を頂点として定義し、ある状態から到達可能かつ安全な状態へ辺をつないだ隣接リストを作る。これをBFSするという形。
状態を枝分かれの構造で表せるからといってすぐ再帰を書こうとしたのが良くなかった。書けてないし……状態をグラフで解釈してBFSやDFSに落とし込むというのは選択肢として持っておかないといけない。
それにしても難しい問題。
D
Cの解法を見ている時にa-bの小さい方から貪欲という記述が目についたためそれで実装するとあっさり通った。
D
n,m = map(int,input().split())
action = []
for _ in range(m):
a,b = map(int,input().split())
action.append((a,b))
action = sorted(action, key=lambda x : abs(x[1] - x[0])) #aとbの差でソート
ans = 0
for a,b in action:
if n < a:
continue
times = (n-a) // (a-b) + 1
ans += times
n -= (a-b) * times
print(ans)
nがaを下回るまでa-bずつ減らしていく、という操作をするが、nが大きいので割り算の商を用いて高速化できる。
すぐ書けたような気がするがa-bでソートして貪欲という方針が分かっていたからでもあり、コンテスト中にこの方針を信じて突き進めるかは微妙な気がする。やっぱり難易度によらずまずCを通しに行く方がいいかもしれない。