スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

Codeforces Round #116 (Div. 2, ACM-ICPC Rules)

2012/04/22
Codeforces Round #116 (Div. 2, ACM-ICPC Rules)

Tags : プログラミング Codeforces

問題

問題セットの原文はここを参照。

A. Defragmentation

ハードディスクに m 個のファイルが断片化して格納されている。
ハードディスクは n 個のブロックに分かれていて、各ブロックは空かファイルの一つの断片が入っているかのいずれか。
ファイル i は n[i] 個の断片に分かれていて、その断片 j はブロック a[i][j] に格納されている。

任意の二つの異なるブロックを選び、一方の中身をもう一方で上書きすることができる。
この操作を 2・n 回以下行い、ファイルの断片化を解消せよ。
すなわち、以下の条件をすべてみたすような上書きの手順を一つ求めよ。

・ すべての i について、ファイル i の断片 1, 断片 2, ..., 断片 n[i] は連続したブロックに格納されている
・ ファイルはブロック 0 から始まる連続したブロックに格納されている ( すなわち、ブロック Σn[i] 以降は空 or ゴミである )

1 ≦ n, m ≦ 200
n[i] ≧ 1
Σ_i n[i] < n

B. Divisibility Rules

任意の正整数 a について、a が d で割り切れるかどうかを判定したい。
・ 「 a が d で割り切れるかどうかが a を b 進数で書いたときの下位 n 桁のみによって決まる 」 とき、d は 2-type であるという ( n は a によらない )
・ 「 a が d で割り切れる ⇔ a を b 進数で書いたときの各桁の和が d で割り切れる 」 とき、d は 3-type であるという
・ 「 a が d で割り切れる ⇔ a を b 進数で書いたときの 1桁目 - 2桁目 + 3 桁目 - ... が d で割り切れる 」 とき、d は 11-type であるという
・ 「 a が d で割り切れるかどうかが 2-type, 3-type, 11-type の判定法を組み合わせることで判定できる 」 とき、d は 6-type であるという
・ 「 a が d で割り切れるかどうかが上記のいずれの方法でも判定できない 」 とき、d は 7-type であるという

d がどの type であるかを求めよ。
2-type のときは、最小の n の値も求めよ。

2 ≦ b, d ≦ 100

C. Letter

アルファベットのみからなる文字列 s が与えられる。
s の何文字かについて、大文字小文字を反転する操作を施すことで、
ある i があって、
・ s[i] より左はすべて大文字
・ s[i] より右はすべて小文字
となるようにしたい。
必要な操作の最小回数を求めよ。

1 ≦ |s| ≦ 10^5

D. Name

文字列 s, t が与えられる。
s の permutation で、t より辞書順で大きいもののうち、辞書順最小のものを求めよ。
そのようなものが存在しないときは -1。

1 ≦ |s|, |t| ≦ 5000

E. Cubes

n 個のキューブが一列に並んでいる。
m 種類の色があり、各キューブはどれか一色で塗られている。
好きなキューブを k 個以下だけ選んで消すことができる。
消したあとの、連続する同色のキューブの個数の最大値が得点になる。
得点を最大化せよ。

1 ≦ n ≦ 2・10^5
1 ≦ m ≦ 10^5
0 ≦ k < n

F. Mathematical Analysis Rocks!

n 人の生徒がいて、それぞれノートを持っている。
{ 1, 2, ..., n } の順列 p があって、生徒たちは一日ごとに持っているノートを p にしたがって交換する。
すなわち、生徒 i は生徒 p[i] にノートを渡す。
三日目と四日目に各生徒がどのノートを持っているかが与えられるとき、p を求めよ。

1 ≦ n ≦ 10^5

解答

A.
制約から、必ず一つは空きブロックがあることがわかる。これを用いると、2 回の上書きで任意の断片を任意の位置に移動させられる。
2・n 回の上書きが許されているので、単にそれを n 回くり返せばいい。
制約ゆるすぎ。
上書きするブロックと上書きされるブロックが同じものであってはいけないことに注意。
http://www.codeforces.com/contest/180/submission/1610887

B.
10 進数のときのアナロジーでがんばる。

a = a0 + a1・b + a2・b^2 + ... と書く。

d が 2-type であるとは、ある n 以降の b^n は mod d で 0 に等しくなるということ。
つまり、
a = a0 + a1・b + a2・b^2 + ... a(n-1)・b^(n-1) (mod d)
となって、下位 n 桁だけで割り切れるかどうかが決まる。

d が 3-type であるとは、b mod d == 1 となること。
つまり、
a = a0 + a1 + a2 + ... (mod d)
となって、各桁の和が d で割り切れることが必要十分になる。

d が 11-type であるとは、b mod d == -1 となること。
つまり、
a = a0 - a1 + a2 - ... (mod d)
となって、( 略 )。

6-type の判定はちょっと難しい。
10 進数のときに、「 6 の倍数 ⇔ 2 の倍数 かつ 3 の倍数 」 であったのを思い出す。
これと同じように、d の約数 d' をうまく選んで、
「 d の倍数 ⇔ d' の倍数 かつ d/d' の倍数 」
という風に判定する。
この⇔は必ずしも成立しないことに注意。
たとえば、d = 8, d' = 2 のとき。
つまり、⇔が成立するためには lcm(d', d/d') == d でないといけない。
ここまで詰めれば、6-type かどうかは d', d/d' について再帰的に計算することで求められる。
※ もっと単純に計算している人がたくさんいるけど、なぜあれでいいのかわからない。誰か教えて・・・

どれでもなければ 7-type になる。
http://www.codeforces.com/contest/180/submission/1662066

C.
大文字と小文字が切り替わるタイミング n 通りをすべて試す。
あるところより左にある大文字の個数を DP で計算しておけば、各タイミングについて O(1) でコストを計算できる。
http://www.codeforces.com/contest/180/submission/1608250

D.
辞書順最小を求める問題なので、一つずつ決めていく典型パターンが使える。
( たとえば OUPC 2012 : Divisor の解説スライドが詳しい )
ある prefix を固定したときの辞書順最大の permutation を求める問題は単に greedy に大きいものから使えばいい。
コードは 5000^2・26 かかっているけど、途中でループを打ち切ったりしているので間に合ってしまった。
http://www.codeforces.com/contest/180/submission/1609763

E.
i 番目のキューブが連続する同色キューブの左端であるとして、最大いくつ連続させられるかを求める。
この部分には二分探索 ( or 尺取法 ) が使えるので、計算量は O(n log n) になる。
日本語で説明しにくいのでコードを読んでください。
http://www.codeforces.com/contest/180/submission/1609177

F.
逆置換とかを考えて、サンプルが合うようにごにょごにょした。
すっきりと説明できない。
http://www.codeforces.com/contest/180/submission/1608571
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

Author : fura2
数学・コンピュータを中心に、考えたこと・やったことを書いていきます。

誤植等を含め、間違いはご指摘いただければ幸いです。

FC2カウンター
検索フォーム
最新記事
最新コメント
最新トラックバック
月別アーカイブ
リンク
RSSリンクの表示
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。