pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

Codeforces Round #350 (Div. 2) F. Restore a Number

問題文が短いにもかかわらず題意を汲み取るのに苦戦した。

http://codeforces.com/contest/670/problem/F

問題

ある整数 n があり、n に n の桁数をくっつけてシャッフルした文字列 Sと n の一部分 T が与えられる。ありうる n の最小値を求めよ。

解法

n の桁数は一意に定まる。

T=56xxxx だったら 1001122334455 + 56xxxx + 66778899 のようにするのが最小。

T=54xxxx だったら 10011223344 + 54xxxx + 5566778899 のようにするのが最小。

T=0xxxxx だったら余っている 0 以外の数字のなかで最も小さいものを先頭に置くのが最小。

Codeforces Round #350 (Div. 2) F. Restore a Numbe ...

本番中は n の桁数が一意に定まることに気付けなくて、強実装をして挙句の果てにバグっていて systest で落ちた。