なかけんの競プロノート
🕒 2021/02/21 🔄 2021/06/14

ABC192感想戦

🛵

AtCoder Beginner Contest 192 に参加しました（SOMPO HD プログラミングコンテスト2021）。結果は、Eまで解けたものの、DでWAを出しまくりました。

Aは、100で割った余りを100から引けばOK。割り切れる場合は場合分けをしなくてもいい。1分。

Bは、奇数番目が小文字で、偶数番目が大文字、となっているかどうかをまじめにチェックする。ここまでで3分。

Cは、整数が与えられるので、「各桁の数を大きい方から順に並び替えた数」から「各桁の数を小さい方から順に並び替えた数」を引く操作を繰り返して、答えを求める問題。回数は多くないのでまじめに実装すればいいんだけど、わりとめんどくさい。

0から9までの各数字が何回出るかを数えて、「大きい順に並べた数」と「小さい順に並べた数」を作って計算していく。もっとうまいやり方はある気がするけど、とりあえず通すだけ通せた（提出 #20297140）。ここまでで12分。

D。XとMが与えられるので、Xをn進数の数とみなして得られる数を考えて、それらの中からM以下のものは何個あるか、という問題。

サンプルにあるX=22, M=10なら、3進数だと3*2+2=8なのでOK、4進数だと4*2+2=10なのでOK、5進数だと超える、だから2種類となる。n進数でOKならn-1進数でもOKなので、ギリギリを考えればいい。つまり、二分探索をすればいい。

オーバーフローを気にしなければ、愚直にやるだけなんだけど、オーバーフローを気にする場合はどうすればいいのかわからず。。。数が大きければスルーする、という方針で最初は書いてみたけど、WAが1回出たのでもうあきらめる（提出 #20309183）。ここまでで35分。

順位表を見ると、Eの方が解かれてる。ので、Eを見てみる。町と鉄道の情報が与えられていて、移動にかかる時間も与えられている。また、電車iはK_iの倍数の時刻でしか出発しない、という条件。

ほとんどダイクストラでOKで、K_iの倍数になるまで余分に時間がかかると思えばOK。ダイクストラをちょっといじってAC。今実行してみたら、after contestもちゃんと通ってた。ここまで47分。このムーブができたのがよかった。

Dに戻る。

まず、掛け算のまま考えると、オーバーフローのところで無限にバグりそうだったので、方針を変えて割り算にすることを考える。つまり、Xをn進数で見たときに、Mを超えてないかどうかを考えるときに、Mをn進数に変換してXと比較する方針で行く。例えば、Xが4桁の数だったら、Mをnで3回割ってその答えとXの一番上の位を比較する。Xが勝ってたらダメ、Mが勝ってたらOK、同点だったら次の桁を見る。これを繰り返していく。こうすれば、Mをnで割っていくので、オーバーフローは関係なくなる。

あと、1桁のときは、特別に考えないといけない。1桁のときは1だな、と考えた。

で、書いてみたら通らず（提出 #20324701）。ただ、WAの数は減った。で、また考える。

そういえば、1桁のとき、そもそもMのほうが小さいケースもあるのか。。。それはそう。ここも追加して提出したが通らず。その後も格闘したけど、二分探索の初期値を変えたらなぜか通った。今でもよくわかってない。。。テストケースが公開されたら見てみたい。ここまでで88分。

残り時間はないので、とりあえずFは見るだけ見て終了。Eを解いていなければ死んでた。