AGC052
難し過ぎて0点で撤退するしかないかと涙目だったが、90分もかけてようやく1問解けた
他の問題も眺めたが、とっかかりが掴めなかったので諦めた
https://gyazo.com/c53876b197c7249dda9cf2a2b4b1418e
主観的にすごく難しかったのでレート上がるかと思ったら下がった。これくらいはできて当たり前だということらしい…。
https://gyazo.com/66c270de964038a555735b3454023271
A - Long Common Subsequence
https://gyazo.com/6cf081a57a9cdab37bc93950e9df8a50
一つ構築せよ問題なので、貪欲法とかで「作りやすい構築法」があるのではないか、と考えた
頭から順に3つの文字列それぞれの「次の0/1の場所」を持っておき、最大のものが小さい方の選択肢を選んでいく、というのを考えた
線形オーダー
証明は思いつかない
とりあえず提出して結果を見よう
結果WAとTLE
TLEが予想外だった
線形オーダーなので十分速いと思ってた
問題条件を見ると…線形オーダーでも10^10だな…
つまり全然違う文字列に対してループしたりしない構築方法を思いつく必要がある
わからないので他の問題を眺めたりする
ブルートフォースで解を列挙するコードを作ってみる
code:python
for 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のサンプルデータを作って解が正しくないものをピックアップし、ブルートフォース全列挙を観察する
code:python
def 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
code:python
def solve(N, SS):
flag = 1 * 4
for i in range(3):
j = (SSi0 - 48) + (SSi-1 - 48) * 2
flagj = 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 flagi:
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
公式解説
もっと場合わけが減らせる
今回の自分の思考の流れと公式解説のヒントを合わせて考えると一つ構築せよ→条件を緩めると自明な解があるというパターンかな