Cまで三完だが、Aは嘘だった。DもEも思いつきにくい部分は思いついていたのだが。
コンテスト後のツイート
C 右端のエレベーターを使わない場合と使う場合とで場合分け。使う場合、その行を突っ切らない場合の最短コストを求めて大きい順にソート。二つまとめてW-1にできる。
— titia (@titia_til) May 10, 2026
D 実験したが分からず。
E 外周から順に構築していったが失敗。（WA6個）
A - Similarity
文字列Xの01を反転させたものをX'とすると、S中にX'が含まれないなら、Xを答えとして良い。
ACした提出は、Sの文字を全探索してそれを調べたが、Sの要素が全て対になっているとき、これではダメ。乱択などしなくてはいけなかった。WAが出たら気付いてACはできていたと思う。
D - Grid Game
解法ツイートを見てAC。
コンテスト中、（一次元での）実験により、
・(i+j)%2==1の箇所しか影響しない
ことには気付いていた。
また、（K+1）での余りを考えて良いことも分かっていた。
しかし、判定条件が分からず、交代和などを考えて迷走。分からなくなってEへ行った。
実際は、NIMと同じなのでxorを取ると良かった。
NIMに近いのでは？ と考えたことはあったはずなのに、なぜ試してみなかったのか。悔やまれる。
E - Equal Distribution
解法ツイートを見てAC。
★「oが偶数個とxが偶数個で作られた配列があったとき、その連続部分区間でoとxをちょうど半分ずつ含むものが存在する」
を使うことはコンテスト中に気付いていたのに、全体のハミルトン閉路を取ることを思いつかなかったという。
外周から距離０、1、２の順に、oがちょうど半分か、一個少ないか、みたいなものを取って構成しようとしていた。
この方法でもできなくはない気がするけど、外周ではAが右半分に、次ではAが左半分に……みたいなときに連結性が保たれない。連結性を保つような取り方はあるはずだけど、若干実装の手間が増えるし、コンテスト中はそもそも反例に気付いていなかった。
★が本質だと思うのに、★に気付いても違う方針へ行ってしまったのは痛い。
一番の鍵となる部分は思いついて実装していたため反省点も見出しにくく、冷静にならないと……くらいしか言えないのも辛いところ。
0 件のコメント:
コメントを投稿