SOMPO HD プログラミングコンテスト2021(AtCoder Beginner Contest 192)参加記（～E問題）

f:id:mmnkblog:20210222021259p:plain

A - Star

高橋君が最後に ~~1UPキノコ~~ ご褒美をもらったあと何枚コインを集めているかわかるなら、 $100$ からその枚数を引けば必要な枚数がわかる。これは剰余算を用いて計算することができる。答えは $100 - (X \% 100)$ となる。

計算量は、 $O(1)$ 。

B - uNrEaDaBlE sTrInG

まず前提として、「ある文字が英大文字か？」を判定する関数と、「ある文字が英小文字か？」を判定する関数を書いてしまう（標準で用意されているなら使い方を調べる）。こうすることで考えることを減らせるし、デバッグの速度も上がる。

文字列を先頭から一文字ずつ見ていき、奇数番目の文字なら英小文字か判定して、偶数番目の文字なら英大文字か判定すると解ける。一文字でも条件を満たしていないのなら答えはNoである。

主要な言語だと配列や文字列の添え字番号は0から始まるので、奇数・偶数が入れ替わるのがややこしいところ。

計算量は、 $O(|S|)$ 。

C - Kaprekar Number

とりあえず、 $g_1(x)$ と $g_2(x)$ を実装する。これは、整数を文字列に変換してからソートしてまた整数に戻す、という処理で実現可能である。これらの関数があれば、定義通り $f(x)$ も問題なく実装できる。 $f(x)$ の計算量は $O(\log x)$ である。

この関数 $f(x)$ についての漸化式が与えられている。制約を見ると求める項は最大でも $10^5$ 番目までなので、愚直に漸化式の定義通り計算しても間に合う。

計算量は、 $O(K\log N)$ 。

D - Base n

誤読した。1桁のとき、何進数でも $M$ 以下になるじゃねえか！と思って15分経ったところでclarを投げたところ、10秒でテンプレ質問が返ってきたのでいったん別の問題に逃げた。

再び戻ってよく読むと、 $n$ の種類数ではなく、計算して得られる値の種類数を求める問題だった。なにこれ？あほくさ

$X$ の長さが $2$ 以上のとき、 $n$ の値が大きくなると得られる値も大きくなる。つまり、 $n$ について条件を満たす境界を二分探索で探すことができる。 $X$ の長さが大きい時、 $n$ が1増えるだけで指数的に増加する場合があるのでオーバーフローに注意しながら実装すること、解が $0$ 種類になるパターンもあること、 $X$ の長さが $1$ のときの場合分けなど、考えることが多い。しかも問題文がわかりづらくて誤読したせいで解いた時の達成感が無かった。クソ

計算量は、 $O(|X|\log M)$ 。

E - Train

都市を頂点、鉄道路を辺と見たグラフを考える。このグラフの頂点 $X$ から各頂点までの最短コスト（問題文中では到着までにかかる時間）を求めたいので、ダイクストラ法が適用できないか考える。

辺のコストが固定ですべて正のコストならばダイクストラ法を適用できる。もし列車が発車するタイミングちょうどに出発都市に到着した場合、コストは $T_i$ である。もし発車までに時間があるなら、その時間をコストに追加してやればよい。頂点への到着時刻を $t$ とすると、 $t-(t\%K_i)+K_i$ がコストとなる。よって、最短コストで移動している場合の辺のコストは固定であるとみなすことができ、すべて正のコストであるので、ダイクストラ法を適用することができる。