先週のABC411は、ABCの3完でした。
A・B問題は特に問題なく、合わせて10分以内にAC。
C問題は少し手間取りましたが、それでも開始から44分でACでき、ここまでは順調に進みました。
D問題でのつまずき
D問題はクエリ処理の問題で、以下のような操作を行います。
-
p番目の箱の内容をサーバにコピー -
p番目の箱に文字列を追加 -
サーバの内容を
p番目の箱にコピー
一見、箱の内容を実際にコピーするのではなく、箱のポインタを移すような実装にすれば良いと思いました。
サンプルケースはこれで通ったのですが、本番ではWA（Wrong Answer）。なぜ間違っているのか分からず、非常に悩みました。
解説を通して学んだこと
後日、公式解説や上位勢のYouTube解説を見て勉強し直しました。
その中で有益だったのは、「クエリを後ろから見て、最終的にサーバに残る箱を追跡し、そこに後ろから文字列を追加する」というアイディアです。
この発想を踏まえて実装を組み直したのですが、以下のようなポインタの制御条件を忘れており、なかなか正解にたどり着けませんでした：
//１の場合
if (p[i] == point_s) { // ポインタがクエリの箱と一致している場合のみ
point_s = 0; // サーバを指すように変更
}
//３の場合
if (point_s == 0) { // サーバを指している場合のみ
point_s = p[i]; // 指す先を指定された箱へ変更
}
おそらく、WAとなったのは、この条件が足らなかった点だと思いますが、後ろから見るというやり方ができていなければ、TLEとなったような気がします。
レート変動と次への意気込み
今回の結果、レートは**522 → 521（-1）**と、ほぼ横ばい。
本日はこのあと、21時からのABC412に挑戦予定です。
次こそD問題までたどり着き、しっかりACしたいと思います！