x y、y x を検索すればいいと思う。横着して単一の文字列を対象にして検索するようにしたら 10 や 20 を 1 や 2 と見間違えるバグを仕込んで頭を悩ませていた。あほ。■C 問題「Dash」。書いてある通りに実装するだけなんだけど最初の提出は WA×1 だった。問題文の最後がこうなんだけど、「高橋君が一度も倒れることなく N 回の移動を行えるか判定してください」、N 回目(最後)の移動の１ステップ目を終えた時点で体力が尽きた場合の判定がそれほど明らかではない。「
最後の移動で体力が-1になった場合答えはYesとなりますか？」という質問と答えが全体公開されているくらいなので。自分はコーナーケースをうまく回避したつもりで N 回目の処理を特別扱いして WA×1 になっていた。ところで、WA×4 になる提出をいくつか見かけたけど、これは「
移動した点に置かれたアイテムを消費し」というのを読み落としていたものと思う。この点はちゃんと疑問を持って確かめていたので間違えなかった。■D 問題「Shift vs. CapsLock」。D は DP の D！ CapsLock が ON/OFF の状態それぞれの最小タイムを記録していく。たぶんないとは思ったけど制約上は許されていたので、Shift+A と CapsLock+A+CapsLock みたいな、結果が決まってそうなケースも一応比較した。■E 問題「A Gift From the Stars」。難しくはないと思う。迷って手が止まってえらく時間がかかったけど。まず次数１の葉っぱを見つける。その相手は星の中心に決まっている。星の中心の相手は葉っぱに決まっている。すでに見た葉っぱは無視して新しい葉っぱの相手を見る。それが自分(星の中心)なら無視して、そうでないものがあるならそれは別の星の葉っぱに決まっている。という感じで次々に判定していくだけのことに 40 分ちょっとかけてしまった。最終形は、星の中心をキューに入れるようにして星のレベルを記録していくものになった。■こちらの提出 #41744985 を見ると次数だけで答えが出せるみたい。次数１は葉っぱに決まってる。次数３以上は星の中心に決まってる。次数２は星の中心でも葉っぱでもありうるけど、全体を見ると星の中心と次数２の葉っぱの数の比率は n 対 2*(n-1) に決まってるので、って感じだろうか。ヒントなしでは気がつけないよ。■面白いことを書いている人がいる。「ABC303-D この問題の正解者は実は間違っていた」。形式だけ見て気が付いたことを。「別のとらえ方」として書かれている４ステップの処理について。１ステップ目は dp[0][j] と dp[1][j] に基づいて dp[0][j+1] に一時的な値を保存している。２ステップ目は同じようにして dp[1][j+1] に一時的な値を保存している。３ステップ目は dp[0][j+1] と dp[1][j+1] に保存した一時的な値に基づいて dp[0][j+1] に本式の値を記録している。４ステップ目は dp[0][j+1] に記録した本式の値と dp[1][j+1] に保存した一時的な値に基づいて dp[1][j+1] に、おそらく誤った値を記録している。これは自分が提出 #41747349 で５行目と７行目がどれだけ長くても１行の多重代入によって値の更新をしている理由だし、ときどきは見た目を整理したい邪悪な欲求に負けて代入を複数行に分けてバグらせてしまうのと同じことである。たぶんね。