読者です 読者をやめる 読者になる 読者になる

pekempeyのブログ

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

Codeforces Round #387 (Div. 2) A..F

http://codeforces.com/contest/747

A. Display Size

問題概要

$n$ピクセルのディスプレイを作りたい。ディスプレイは縦$a$ピクセル、横$b$ピクセル、$a\le b$の横長の長方形型にする予定である。$b-a$ができるだけ小さくなるような$a,b$を出力せよ。

解法

$a$を決めれば$b$も決まるので、$a$を全探索してしまえばいい。

$a \le b$ なので、$a>\sqrt{n}$としてしまうと$a\times b>n$ となる。つまり$a \le \sqrt{n}$ としてよく、実は$n \le 10^{12}$程度の制約であっても解くことができる。

B. Mammoth's Genome Decoding

問題概要

'A','G','C','T','?'の5種類の文字で構成される文字列が与えられる。それぞれの'?'を'A','C','G','T'のいずれかに書き換えて、'A','G','C','T'の出現回数がすべて等しくなるようにせよ。

解法

A,G,C,Tの出現回数が等しいのだから、nは4の倍数でないときは構成できない。 また、ある文字の出現回数がn/4を超えている場合も構成できない。それ以外は構成できる。

C. Servers

$O(nq)$が通るため、愚直なシミュレーションにより通すことができる。

実装方法としては、fin[i]:=i番目のサーバが作業を終える時刻という配列を用意して、先頭から順に使えるかどうかを調べていくというものがある。

priority queue を用いたシミュレーションもできる。配列よりは計算量に無駄が出るが、こちらも時間制限に間に合う。

D. Winter Is Coming

問題概要

n日間の気温が与えられる。気温が非負の日はどのタイヤでも走行可能で、気温が負の日はスノータイヤで走る必要がある。スノータイヤはk日までしか使うことができない。n日間のタイヤの最小交換回数を求めよ。

解法

スノータイヤで走る日数が最小になるような交換を考えてみよう。これは各区間の先頭で交換すればいい。

f:id:pekempey:20161222134742p:plain

一番左の0度以上の区間は無視してもかまわない。0度以上の区間でもスノータイヤで走るようにすると、交換回数は基本的に2回減る。

f:id:pekempey:20161222135221p:plain

ただし注意が必要なのが、一番右の区間を潰したときで、1回しか減らない。

f:id:pekempey:20161222135917p:plain

一番右の扱いが面倒である。ここは素直に、一番右の区間を潰すか潰さないかで場合分けしよう。

それ以外の区間はどれを潰しても交換回数が2回減るので、区間の長さをソートして、短いものから貪欲に潰していけばいい。

E. Comments

スタックを使って愚直にシミュレーションすればいい。

F. Igor and Interesting Numbers

$t=1$のとき、9桁のinteresting numberがいくつあるかというと、$15 \times 15 \times 14 \times 13 \times \cdots \times 8 = 3891888000$ 個ある。

つまり、$2\times 10^9$ 番目の interesting number は9桁以下で収まる。$t \ge 2$であれば8桁以下で収まる。

このことを考えると半分全列挙的な考え方が使えることがわかる。上位4桁を決めてしまうと、条件を満たす下位4桁の組み合わせはDPにより計算できる。このことを使うと、k番目の数の上4桁が何であるかが判明する。上4桁が何であるかが分かれば、下4桁は単純にループを回すだけで求まる。

桁DPっぽいけど桁DPがうまく適用できないと思ったら、半分全列挙がうまくいくかもしれない。AtCoderでもそういう問題があった気がする。

かなり珍しい朝開催のCodeforces