ABC167
3完でした。
A問
t[0:-1] == s という簡単な条件式でOK。 2分ぐらいで提出。
s = input()
t = input()
if t[0:-1] == s:
print('Yes')
else:
print('No')
B問
1, 0, -1 の順番でK枚になるまで取ればいいです。 実装がダサい… と思ったけどとりあえず出しました。5分ぐらいで提出。
a, b, c, k = map(int, input().split())
total = 0
if a >= k:
print(k)
exit()
total = a
k = k - a
if b >= k:
print(total)
exit()
k = k - b
print(total - k)
C問
制約を読み間違えて時間を無限に溶かしました。つらい。
1≦N, M≦12 という制約を 1≦N と M≦12 という2つの制約だと勘違いし、「Nの範囲無限じゃん、どうすんだこれ…？」となっていました。BFS,DFSやDPを最近勉強したのもあり、そのへんでどうにかなるのか…？？？と無限に考え込んでしまいました。
最終的に「Nは標準入力の改行数だし、改行しまくる問題作るの大変だから高々100ぐらいだろ（？）」という謎の仮定を置いて、全探索を実装しました。
途中で1回WA出しながら（indexに+1するの忘れた）およそ70分かけて提出…。
from itertools import product
n, m, x = map(int, input().split())
books = [list(map(int, input().split())) for _ in range(n)]
minimum_cost = float('inf')
buy_selections = product([1, 0], repeat=n)
for selection in buy_selections:
bought_books = [books[i] for i in range(n) if selection[i]]
total_each = [0] * (m+1)
for book in bought_books:
for i in range(m+1):
total_each[i] += book[i]
if any([total < x for total in total_each[1:]]):
continue
if total_each[0] < minimum_cost:
minimum_cost = total_each[0]
if minimum_cost == float('inf'):
print('-1')
else:
print(minimum_cost)
D問
C問で時間を溶かしまくった結果、残り20分ぐらいで取り組むことに。
Kをループ部の長さで割った余りと、ループ前の部分を足せばOK、ってのは割とすぐ気づいて実装できました。
コンテスト終了直前に提出しましたが、TLE。計算量を削減できずにコンテスト終了。
TLEしたコードはこれ。
n, k = map(int, input().split())
a = list(map(int, input().split()))
history = []
index = 0
cnt = 0
loop_start_city_index = 0
while True:
if cnt == k:
print(index+1)
exit()
if index in history: # すでに訪れた街にきた
loop_start_city_index = index
break
history.append(index)
index = a[index] - 1
cnt += 1
from_start_to_loop_start = history.index(loop_start_city_index)
loop_length = len(history) - from_start_to_loop_start
print(history[from_start_to_loop_start + (k-from_start_to_loop_start)%loop_length] + 1)
ループの中の if index in history: が悪さしてました。ループごとに配列要素の全探索してたらそりゃ時間かかるわな。
訪れた街かどうかを保存しておく配列を作って、それを参照するコードに変えたらAC。
E問、F問
見てません。多分まだ見ても実力不足で解けない。
反省
- 制約をちゃんと読む カンマがある→複数の制約と思い込まない
inとかindex()はO(N)かかるから気をつける 組み込み関数だからサクッと動くとか思わない
