ARC154に出た。
A: 頑張って考察すると、とにかく片一方をでかくして片一方を小さくすると最小になることが分かる。あとはAとBのmod 998244353を計算して掛け合わせるだけ。
B: 逆の操作を考えると「任意の場所から抜き取って先頭に入れる」になる。Tをこの逆操作でSに変換できるかを考える。
Tにこの操作をk回やると、抜き取った文字を並べたk文字の文字列+残ったN-k文字の文字列になる。k=Nとすれば任意に並べ替えることが出来るので、SとTがソートして一致するなら必ず変換可能であると言える。あとはkを最小化することを考える。
Sの後ろのN-k文字がTの部分列であるならばk回で変換可能であると言える。この判定は$O(N)$だが、単調性があるので二分探索で最小のkを探索できる。全体$O(N\log N)$。
C: Aに操作を行うと必ずその操作をした位置に2つ同じ値が並んだ状態になる。ということは、最初から一致している(A=B)場合でない限りBには最低でも一か所2つ同じ値が並んでいる箇所が必要になる。なのでこれをまず判定する。$A_{N+1}=A_1$であることに注意。
Aに操作を行ってどういうことが出来るかを考える。まず、ぐるぐる回すことが出来る。ただし2つ同じ値が並ぶ箇所を最低1か所作るという条件付き。2つ同じ値が並ぶ箇所は任意に移動できるので最低1か所ありさえすればよい。それから同じ値を広げることが出来る。1,2,3,4,5…という部分があったら1,3,3,3,1…にできる。前にも後ろにも広げることが出来るのは回転できることから導かれる。そして重要な点として、境目を増やすことはできない。1,1,2,2から1,2,1,2を錬成することはできない。
以上を踏まえると、Bをランレングス圧縮して文字だけを取り出した文字列($B’$とする)がAの部分列であれば良さそうだということが分かる。ただし、任意に回転できるのでAを回転させたいずれかの文字列の部分列であれば良い。ここが難しく、厳密な証明が出来なかった。
とりあえず回転を許す場合の処理のセオリーとしてAの長さを2倍にしておく($A’$とする)。$B’$がこれの部分列であるかどうかをまず判定する。ここで部分列でなければ即アウトだが、部分列であってもOKとは断定できない。$A=(1,1,2,2), B’=(1,2,1,2)$といったケースを考えると、$B’$は$A$をどう回転させてもその部分列にはならないが、$A’=(1,1,2,2,1,1,2,2)$の部分列にはなってしまう。これをはじくために、$A’$の部分列として$B’$を取り出したときに$A’$上で長さが$N$を超えないことをチェックする。
前からマッチして$A’_k$で終わった場合、$B’$が$A’: [k-N+1, k]$の部分列であるかどうかを確認する。これで部分列だったらセーフ、部分列でなかったらアウト。Nの範囲内に収まるかどうかを確かめてやるという気持ちでこういう感じの実装をしたが、正当性の証明は出来なかった。とにかくACしたのでヨシ！(よくない)
D: 1の位置さえ特定できれば20000回程度でマージソート出来そうということは分かったが、1を特定する方法が思いつかなかった。後でupsolveしたい。
筋トレをした。今日は背筋。
一日中ロックマンXをプレイしまくっていた。一気にラスボスシグマまで突き進んだ。
ライフ最大値アップを回収したほか、ダメージ軽減と頭突きのパワーアップを回収した結果、あんなにムリムリ言ってたボスたちがおよそ雑兵と化した。サブタンクも3つまでに増えた。
あと説明書をちゃんと読んだ結果、ダッシュ壁ジャンプを会得した。昔のゲームというのは説明書を読むものだね。
最初は無理ゲーにしか思えなかったが、なんだかんだ説明書以外何も見ずにちゃんと進めることが出来てしっかり作られたゲームに感じている。やり応えもしっかり感じた。パワーアップが初代シリーズに輪をかけて重要なファクターになっているので最初のとっかかりが難しい感じになっているかも。そこはもうちょっと調整できたんじゃないかという風に思うが、ロックマンシリーズといえばステージ選択画面なのでそこを変えるのもなあという感じがする。
Categories: 未分類