脳log[20240106]

2024年01月06日 (土) [AtCoder] 今日は ABC335（Sponsored by Mynavi）があった。コンテスト成績証。自分のすべての提出。ABCDE の５完で青パフォ。F 問題に 50 分残していて解けなかったのが残念。DP の状態をうまくまとめられなかった。ではふりかえり。■A 問題「202<s>3</s>」。文字列操作。■B 問題「Tetrahedral Number」。辞書順に総当たり。■C 問題「Loong Tracking」。最大で N+Q 要素の配列があれば十分。末尾へのポインタを管理して最大で N 要素振り返って見る。■D 問題「Loong and Takahashi」。実装問題枠か。ぐるぐる。■E 問題「Non-Decreasing Colorful Path」。連結なので最低得点 0 は確定している。1 以上の得点を得るパスのみを考える。なので辺については A[u]<=A[v] となる u->v のみを使う。狭義単調増加が得点の条件であれば、A[i] の値が小さい頂点から順番に移動をシミュレートするだけ。自分のこの WA (#49092053) はある頂点に未達の場合を考慮していなかったせい。使う辺を限定して正の得点を得る場合のみを考えているので未達もある。実際の問題は広義単調増加が条件なので、A 数列がすべて同じ値の場合にうまく順序づけができないとぐるぐると値の更新が反復して TLE になりそう。A[i] の値が同じ頂点についてはこれまで通ってきたパスの得点が高いものから順に処理することで TLE を避ける。自分のこの WA (#49096697) は同じ A[i] を持つ頂点間の移動によって未達だった頂点に新しく到達した場合に、その頂点を処理対象に追加するのを忘れたのが原因。２つ３つの罠があったようであり、自分が単に間抜けだったようでもあるが、２つの WA を経てやっと AC (#49100939)。３つの提出にそれぞれ９分７分７分かけてペナルティ合計が 10 分なので、E 問題には 33 分かけた計算になる。案外いいのでは？ しかし十分に時間をかけても F 問題は解けず。