ABC411-D を Python で解いた

ABC411 D - Conflict 2
https://atcoder.jp/contests/abc411/tasks/abc411_d

惜しいところまで行っていたのに解けませんでした。敗因を探っていきたいと思います。

コンテスト中の動き

C 問題の解法がすぐには思いつかず、D 問題を先にやっておくことにしました。ところが結局 D もわからずまた C に戻り、するとすぐに C の解法を思いつきました。それはいいのですが結局 D は解けず「C 問題を遅く解いた 3 完」という最悪の結果になりました。今年始まってから最低のパフォーマンス、2 回目の茶色を記録しました。4週続けてレートが大きく落ち、1000 切りが現実的になってきました。4週続けて3桁のパフォーマンスしか取れていないので当然です。ABC392-400 と ABC402-406 で 14 回連続 D 問題正解！なんて調子の良い時期もあったのですが、ここ4回で D 問題を解けたのは 1 回のみ、しかも遅い……。difficulty を見てみると緑 diff が解けなくなったようです。僕がサボっている間に周りのレベルも問題のレベルも一気に上がったのか、たまたま不調が続いているのか……。引退の2文字がちらつくぐらい激しく落ち込みましたがしっかり復習してまた頑張りたいと思います。

コンテスト中に考えたこと

全ての PC の文字列を記録しておいて毎回コピーするのは明らかに計算量オーバーになるので、これを回避することを考えます。最初に考えたのは、操作2で追加される文字列 s に 0, 1, 2, ... と番号をつけておき、どの PC がどの文字列を持っているのか数字の配列を用いて管理する方法です。しかし、これは結局配列のコピーが必要になるので TLE です。じゃあ PC ではなく文字列の方に着目し、どの文字列がどの PC に保持されているのかという情報を持たせるようにすればうまく行くのでは……？ということも考えましたが、「じゃあ PC1 に入ってる文字列を全部サーバーのものに変えるから、PC1 に含まれている文字列の一覧を出してくれ」となると TLE は避けられません。では「どの PC に何番の文字列が入っているか」と「何番の文字列がどの PC に含まれているのか」両方を管理しておけば……なんてことも考えましたが、なんとなくうまく行く気がしない上に書くのがとても複雑そうです。文字列 s は重複することもあるので辞書型も使えません。

ここまで考えた頃にもう少し楽な方法が他にないのか考えました。過去問の知識からいうと、全ての操作が終わった後の結果だけを要求されているときはクエリ先読みが使えます。

考察

この問題でそれを学びました。
https://atcoder.jp/contests/abc314/tasks/abc314_d
また、この問題では特定のクエリについては最後のもの以外は結果に影響を与えないという特徴がありました。そのアイデアを持ったまま今回の問題を見てみました。

入力例 1 を見ていきます。クエリを後ろから見ていきます。先読みに加え、「後ろから見る」も典型の 1 つですね。

• 3 2
  最後に PC2 の文字列をサーバーにコピーしているので PC2 さえチェックしておけば答えは求まります。
• 2 2 corder
  その前に PC2 に文字列が追加されています。これは最終的な結果に影響を与えるので記録しておきます。
• 1 2
  PC2 の文字列をサーバーにコピーしているので今度はサーバーを見るようにします。
• 2 2 on
  PC2 の文字列が変化しますが今はサーバーを見ているので影響はありません。
• 3 1
  今度は PC1 の文字列をサーバーにコピーしているので PC1 を見るようにします。
• 2 1 at
  今見ている PC1 に文字列が追加されたので記録しておきます。

最終的に文字列 "corder", "at" が記録されているのでこの順序を逆転させ、答え "atcoder" を得ます。

考えてみれば、サーバーの文字列が変化するのは他の PC からコピーされてきたときだけです。また、操作 2 以外で PC の文字列が変化する手段はサーバーを介したコピー以外にありません。となると、サーバーの中身と答えに影響する PC 1 つの中身だけを監視しておけばいけそうです。全ての PC の中身を管理しなくても監視対象となる PC の中身だけを管理しておけばいいのであれば計算量は少なく済みます。

提出と WA

ところが……書いて提出したコードは 18 個の WA を出して帰ってきました。僕が提出したコードの概要はこれです。上記の監視対象となる PC を変数 see に入れておくようにし、サーバーを PC0 としておきます。

• クエリ1 のとき、p の中身がサーバーにコピーされるので、この p が監視対象 see であれば see を 0 に切り替える。
• クエリ2 のとき、PC see に文字列が追加された場合は答えの元になる配列 ans に文字列 s を追加する。
• クエリ3 のとき、サーバーの中身が p にコピーされるので、監視対象 see を p に切り替える。

どこがおかしいのかわかりません。もしかしたら監視対象以外の PC の文字列が変化したときも記録しておかないといけないのか？と考えて焦ります。入力例 3 の中身も詳しく見てみますが、これも大して複雑な処理にはなっておらずデバッグに使うには不十分そうです。結局原因がわからないまま残り 30 分を切り、そこでギブアップしました。

結論からいえばクエリ 3 の処理が間違っていました。「監視対象 see を必ず p に切り替える」のではなく、「監視対象 see が 0 のときにのみ p に切り替える」ようにしないといけませんでした。つまり if 文を 1 つ追加するだけで AC となりました。たかが 1 行ですが、内容の理解が不十分だったことが原因なのでこれは大きな大きな 1 行です。

実装

実装自体は簡単ですね。

N, Q = map(int, input().split())
querys = []
for _ in range(Q):
  query = input().split()
  querys.append(query)
# クエリを後ろから見る
ans = []
see = 0 # 監視対象にする PC
for i in range(Q-1, -1, -1):
  query = querys[i]
  if query[0] == "1":
    p = int(query[1])
    if p == see:
      see = 0
  elif query[0] == "2":
    p, s = int(query[1]), query[2]
    if see == p:
      ans.append(s)
  elif query[0] == "3":
    p = int(query[1])
    ####### この条件がよくわかっていなかった。これがあれば AC だった。
    if see == 0: 
      see = p
ans = ans[::-1]
for an in ans:
  print(an, end="")
print("")

敗因の分析

要するにクエリ 3 で「どんな p が来たとしても必ず監視対象を p に切り替える」としたのが悪かったわけです。「サーバーと、監視対象になる PC の 2 台だけを監視しておけばいいのでは？」と考えていたのが敗因でした。処理の手順をもう少し突き詰めて考えれば、サーバーも PC も対等な存在として同等に扱えることに気づいて「監視対象となる（サーバーも含めた）1 台だけを監視すればよい」とわかったはずです。そうなればクエリ 3 がクエリ 1 と対になることから、こちらにも if 文が必要になることにも気づけたかもしれません。

「なんとなくできそう」というひらめきだけで問題を解こうとせず、もっと細かいところまで考えるようにしないといけません。しかし、これは正解を知った後だから冷静にそう言えるだけです。コンテスト中には今考えている方針で本当に解けるかどうか確信もありませんし、僕の頭ではこれ以上深堀りするのは難しかったと思います。

頭が悪くて細かいことまで考えられないのであればもう少し機械的な解決法を探る必要があります。一般的なことをいうならデバッグ用のテストケースを自分で用意することでしょうか。やるべきなのはわかっているけど面倒なのでサボっていました……。いろんな場合分けを盛り込むのって難しいですからね。頭もめちゃくちゃ使います。ただ今回の問題は愚直解が簡単に求まるので、テストケースをランダムに適当に作っても正解と見比べるのは容易でしたから、やるべきでした。ここが僕の甘えですね。