結果

A,B,C,Dの4問正解でした。

C問題でそこそこ時間を使ったのが痛かった。 E問題はちょっとしか時間が取れなかったから解ききれなかった。

A - 321-like Checker

与えられた数値の各桁が狭義単調減少になっているかどうかを判定する問題。

数値を文字列として受け取って上から1桁目から順番に次の桁の値と比較して判定していった。
charで'0'から'9'のどれかだから上からx桁目とx+1桁目を直接比較しても問題ないと思うし、数値にしたいならcharの値から'0'を引いてあげれば０～9の数値に変換できる。

数値として処理したいなら、2桁以上の場合は 10で割った余り(下から1桁目)と100で割った余りを10で割ったもの(下から2桁目)を比較してみて、OKなら元々の数を10で割ってまた比較をするって具合に繰り返していけば良い。

数値がN個ある時、ソート済みの数列の最初と最後以外を足した値(スコア)について考える。 N個中のN-1まで数列が与えられたときにN個目の値はいくつ以上ならスコアがX以上になるかどうかを答える問題。

N個目の値が取りうる値は最大でも100程度なので0の時から100の時まで全通り探索して答えを求めれば良い。

値によって以下の3パターンが考えられるので、どれに該当するか判定して最終的なスコアを計算する。

計算したスコアがXを超えれば、その時考えているN個目の値が解の候補になる。

スコアの計算用に、N-1個の数列をソートしたものの最初と最後以外の値を合計しておけば、N個目の値を決めたときのスコア計算が楽になる。

A問題でみた各桁が狭義単調減少となっている数値の中からK番目に小さいものを答える問題。

TLEとかMLEとかCEとかいろいろエラーになってその度に解き方の方針を考え直した。

案1

最大値が $10 ^ {9}$ なので、そこまで探索することになるならTLEするだろうなと思いつつ提出したらTLEになった。

案2
案1から無駄な部分を削ぎ落とそうとした。

案1同様1から順番に全探索する。
ある値が条件を満たすかどうかの判定は、上記A問題の数値として処理したい場合の考え方の方針で実装する。
1度条件を満たさないとなったものはメモしておき、10で割った後に下1桁目と2桁目を求めて判定を始める前にその値がメモにあるかどうかを確認する。メモに登録のある値ならそれ以降の桁の判定は時間の無駄なので省略する。

メモ用にサイズが9876543210の配列をboolで用意しようとしたらメモリを使いすぎてMLEになったり、コンパイルエラーになったりした。

案3

条件を満たすある値があるとして、条件を満たすように1桁追加したものをqueue/stackに追加していく幅優先探索や深さ優先探索を行う。条件を満たす値すべてを洗い出した後にソートし、K番目のものを答える。

最初に0~9をqueueに入れてそれらを初期として幅優先探索を行った。とりあえずこの方針で解けた。

最初に思いついた方針だと全然だめだったので少し遠回りしたのが時間的に痛かった。

N個ある $A _ {i}$ とM個ある $B _ {j}$ 全通りの組み合わせで足し算をして $min(A _ {i} + B _ {j}, P)$ の総和を求める問題。

足すのはPじゃなくて $A _ {i} + B _ {j}$ として手元で計算してみると各 $A _ {i}$ はM回足されていて、各 $B _ {j}$ はN回足されていると気づいた。

このM回、N回のうちの何回かが代わりにPになる。

各 $A _ {i}$ に対してM個ある $B _ {j}$ のいくつが足したときにP以上になるのかを数えていき、 P以上にならない回数だけ $A _ {i}$ 、 $B _ {j}$ を足して、最後に数えていたPになる回数分Pを足した。

$B _ {j}$ をソートしておけば二分探索でP以上になる $B _ {j}$ の境目が高速に探索できる。