AGC052
難し過ぎて0点で撤退するしかないかと涙目だったが、90分もかけてようやく1問解けた
他の問題も眺めたが、とっかかりが掴めなかったので諦めた
主観的にすごく難しかったのでレート上がるかと思ったら下がった。これくらいはできて当たり前だということらしい…。
一つ構築せよ問題なので、貪欲法とかで「作りやすい構築法」があるのではないか、と考えた
頭から順に3つの文字列それぞれの「次の0/1の場所」を持っておき、最大のものが小さい方の選択肢を選んでいく、というのを考えた
線形オーダー
証明は思いつかない
とりあえず提出して結果を見よう
結果WAとTLE
TLEが予想外だった
線形オーダーなので十分速いと思ってた
問題条件を見ると…線形オーダーでも10^10だな…
つまり全然違う文字列に対してループしたりしない構築方法を思いつく必要がある
わからないので他の問題を眺めたりする
ブルートフォースで解を列挙するコードを作ってみる
pythonfor t in itertools.product("01", repeat=N * 2 + 1):
if all(isSubStr(s, t) for s in SS):
print("".join(t))N=2のケースで高々32個の候補をテストするだけなので速い、観察に使える
全ての解を観察してみたが、大体いつも2個か3個に分かれただけの列がある。
2Nの長さなら自明な解があることに気づいた
例えば
"0" * N + "1" * N 各列の最初と最後の組み合わせは4通りある。
文字列は3つなので1つ以上の「使われない組み合わせ」がある
たとえば0, 0が使われないなら中央に0に挟まれた1が必ず存在するので
"0" * N + "1" + "0" * N は解になる伏線A
1,1の時も同様
1,0や0,1の時にはどちらでもいいのかな？と思ったがWA
N=2のサンプルデータを作って解が正しくないものをピックアップし、ブルートフォース全列挙を観察する
pythondef randomtest():
import itertools
xs = [bytes(x) for x in set(itertools.permutations([48, 48, 49, 49], 4))]
from random import seed, choice
N = 2
for s in range(1000):
seed(s)
args = [choice(xs), choice(xs), choice(xs)]
answer = solve(N, args[:])
if not isOK(N, args[:], bytes(answer, "ascii")):
ss = [bytes(s).decode("ascii") for s in args]
print(ss, flag, answer)
blute(N, args)
print()これでどういう時に正しくない答えを返すかがわかったのでワークアラウンドした
AC
pythondef solve(N, SS):
flag = [1] * 4
for i in range(3):
j = (SS[i][0] - 48) + (SS[i][-1] - 48) * 2
flag[j] = 0
if flag == [0, 1, 0, 0]:
return "0" * N + "1" * N + "0"
if flag == [0, 1, 1, 0]:
return "0" * N + "1" * N + "0"
if flag == [0, 0, 1, 0]:
return "1" * N + "0" * N + "1"
for i in [0, 3, 1, 2]:
if flag[i]:
if i == 0:
return "0" * N + "1" + "0" * N
if i == 1:
return "0" * N + "1" + "1" * N
if i == 2:
return "1" * N + "1" + "0" * N
if i == 3:
return "1" * N + "0" + "1" * N公式解説
もっと場合わけが減らせる
今回の自分の思考の流れと公式解説のヒントを合わせて考えると一つ構築せよ→条件を緩めると自明な解があるというパターンかな
"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from [Scrapbox] at [Edit]