0.はじめに
2週連続のARC。1問解けないとレート駄々下がりという緊張感の中
1問も解けずにレート急落・・・。
1.A - Swap Digit
正直問題文を読んだだけでは、解法が皆目見当もつかなかった。
ただ、直感的に同じ桁の数字のうち、小さい方を一方に集めれば
なんとなく行けるのではないかと思い実装
9問ACで9問TLEに。
その後試行錯誤するもあえなく時間切れ。
解説読んでも、直感があっていることが裏付けられただけでした。
翌日ふと、pypy3ではなく、python3で提出したらTLEにならずにAC・・・・
桁の大きい計算があるときはpypyを使うなという昔刻んだ鉄則を
忘れてました・・・。無念。。
https://atcoder.jp/contests/arc154/submissions/38273958
2.B - New Place
2023/1/23 修正
解説を読んでも今一でしたが、解説動画を見て解法が分かりました。
本番時は、使用されている文字が一致すれば回数はともかく
一致する文字列が作れることはわかりつつ放置してましたが
やはり最初にそのチェックをした方が良いことが分かり
SとTをソートして比較。
一致しなかったら-1を出力して終了。
を、してからの以下の考え方。
【考え方】
操作は先頭から行う形式のため、途中のある文字だけ動かす等はできない
→Sの最後の文字から動かさなくてもいい順序になっている文字をカウントし
それ以外の文字は動かすと考える
例題１）で考えると
S:abab
T:abba
→1)S4：b以外を動かす場合・・・abbaにできる
→2)S3：a、S4：b以外を動かす場合・・・abbaにできる
→3)S2：b、S3：a、S4：b以外を動かす場合・・・babに対して、aをどうやっても、abbaにできない
→2個残しの状態までがTに一致させられる＝N-2が答え
【実装】
Tの後ろから一文字ずつ、Sの後ろから比較していく＝順序を保てる位置にあるかをチェック
解説にある通り、2分探索を使わずに、愚直な比較でAC頂けました。
https://atcoder.jp/contests/arc154/submissions/38280421
以上