Ruteのプログラミング日記

競技プログラミング(AtCoder)の問題の解説や、過去問を解いた感想、また解けない過去問について共有したいと思ってます。

Codeforces #629 (Div.3) 感想等

Codeforces #629 (Div.3)が昨日23:35から行われました。

当記事では、当該コンテストの問題についての解説を行います。

が、その前に

Codeforce重かったですよね....今回、20000人以上の参加になったみたいなので、ジャッジなども重くなったみたいです。(問題文が見れなくなることもありました)

A問題

$t$ 個のテストケースが与えられて、それぞれに対して以下の問題を解きます:

2つの整数 $a,b$ が与えられます。

$a$ を $a+1$ に任意回変更することが出来ます。(つまり、 $a$ に何度も1を足すことが出来ます)

この時、 $a$ を $b$ で割り切れるようにするには、 $a$ を何回変更する必要があるか求めなさい。

制約: $1≦t≦10^4 , 1≦a,b≦10^9$

解法

まず、 $a$ が $b$ で割れるかどうかで条件分岐を行います。

(ここで、 $a$ を $b$ で割ったあまりを $d$ とします。)

$d=0$ なら、何も操作する必要がありませんから、0を出力します。

$d ＞ 0$ なら、bに対して $b-d$ 回の操作が必要ですから、

$b-d$ の値を出力します。

これでこの問題を解くことが出来ました。

B問題

$t$ 個のテストケースが与えられて、それぞれに対して以下の問題を解きます:

2つの整数 $n (n＞2)$ 、 $k$ が与えられます

$n-2$ 文字が"a"で、それ以外の文字が"b"である文字列を考えます。このとき、

$n$ 桁でこれを満たす文字列の内辞書順で $k$ 番目の文字列を出力して下さい。

制約: $1≦t≦10^4, 3≦n≦10^5, 1≦k≦min(2×10^9,\frac{(n-1)n}{2})$

考察(Ruteは解けませんでした)

問題文を読むと、

"2桁が"b"で、残りの桁が"a"である文字列のうち $k$ 番目の文字列を出力しなさい。"と言い換えることが出来ます。

ここで考えたのは、「異なる2つの2のべき乗で表される数字」というものです。

f:id:Rute_programming:20200327131613p:plain — 今回考える数列

例えば、 $3 = 2^{0}+2^{1}$ 、 $5 = 2^{0}+2^{2}$ 、 $6 = 2^{1}+2^{2}$

のように、 $n = 2^{a}+2^{b} (a \neq b)$ で表される数 $n$ が数列になっています。

これを利用すれば、条件を満たす2進数を列挙することが可能になります。

追記13:45)例えば、 $n = 5,k=1$ のとき、数列の1項目である $3$ を考える2進数としましょう。

$3$ の2進数表現は"11"なので、5桁にゼロ埋めし、その後に"1"の部分を"b","0"の部分を"a"としました。すると、"aaabb"が出力されます。

これを他の $n,k$ でも同様にすれば良いです。

ただ、一般項などが分からなかったために、作成したリストを提出しようとしましたが

65536文字以上のコードなので提出できません。

orz。まぁ対策はされていたということを初めて知ったので良い経験になりました。

A問題の1完です。koboshiさんの記事を読んでまた勉強したいと思います。

解説は以上です。コードなどの提示を求められましたら随時このブログに掲載します。