2017-07

Latest Entries

スポンサーサイト

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

Codeforces Beta Round #76 Div. 1

手を付けた順は D → E → A → B.E はすぐ書いたものは TLE で一旦放置して最後に解いた.Hack は残り 10 分で部屋の E をすべて落とした.4 問通って 2 位.

A: Frames


Windows のエクスプローラ.n 個のアイコンが 1 行に m 個ずつ並んでいる.a 番目から b 番目までを選択したい.1 回の操作で選択できるのは長方形領域で,二重に選択されると選択が解除される.最小操作回数を求める.
n, m <= 10^9.

場合分け.
・a と b が同じ列にあれば 1 回.
・「a が行の先頭」かつ「b が行の末尾 or b = n」ならば 1 回.
・「a が行の先頭」または「b が行の末尾 or b = n」ならば 2 回.
・a の行の 1 つ下が b の行であれば 2 回.
・a の列の 1 つ左が b の列であれば 2 回 (これのみ縦に区切る).
・その他は 3 回.

4 つ目と 5 つ目を忘れていて pretest で何回か WA を出した.

B: End of Exams


n 個のミルクの瓶があり,それぞれに w 入っていて,これらを m 人で等分したい.同じ瓶からは高々 2 人までに配るとするとき,可能かどうか判定し,可能ならその方法を出力する.
1 <= n <= 50,2 <= m <= 50.

「長さ m の棒が n 本あり,それぞれを高々 2 つの整数長さに分割し,m 人に長さ n ぶんずつ配れるか」という問題として考えられる.
n < m かつ n が d = m - n で割り切れないときを考える.m の分け方として (n, d), (n - 1, d + 1), ... が考えられるが,たとえば (n - 1, d + 1) を使うと n - 1 に対応して長さ 1 が必要になるが 1 は作れないのでこれは使えない,といったようにしていくと,(n - kd, (k + 1)d) しか使えないことがわかる.すると各棒からは d で割り切れない断片は高々 1 つしか生じず,m 人には与えられない.よって不可能.
一方,その他の場合は 1 人目から順番に貪欲に使っていけば可能であることがわかるのでそうする.

コンテスト中は証明をせず,貪欲に配り途中で棒が 3 分割されたら不可能,というコードを出した.

C: Azembler


26 箇所のメモリがある.最初,1 つ目のメモリにある数が入っていてそれを n 倍してどこかに保存したい.他のメモリは最初 0.可能な演算は,x <- kz or x <- ky + z (x, y, z はメモリ,k = 1, 2, 4, 8).最短操作数を求めて操作を 1 つ求める.
1 <= n <= 255.

26 個も使わないことはすぐわかるので,今まで作った数をすべて記憶できているとしてよい.また演算は数を減らさないので,昇順に作っていくとしてよい.これをもとに探索する.
作った数の vector からの map で,最短手数と次に作るべき数,を pair にしてメモ化再帰したら通った.
より単純には,iterative deepning + DFS で見つけることもできる.

D: Flags


白・黒・赤・黄の 4 色からなる 1 * n の旗を作る.満たすべき条件は,
・同じ色は隣接しない.
・白と黄は隣接しない.
・赤と黒は隣接しない.
・黒,白,赤あるいはその逆の順に並ばない.
裏返しを同一視するとき,L <= n <= R において何通りあるか mod 1,000,000,007 で求める.
1 <= L <= R <= 10^9.

行列累乗.直前 2 文字のパターンと,「終了した」という状態を考えれば,n <= N の場合の数がわかる.裏返しを除くには線対称な旗の個数を足して 2 で割ればよいが,線対称で条件を満たす旗は必ず n が奇数で,n = 2m + 1 で線対称な旗が条件を満たすことは,中央までの n = m の旗が条件を満たすことと同値なので,これも数えられる.

E: Lostborn


a[1], ..., a[k] は互いに素.n 以下の正の整数であって,a[1], ..., a[k] のいずれでも割り切れないものの個数を求める.
1 <= n <= 10^13,1 <= k <= 100,1 <= a[i] <= 1,000.

包除原理.ただし愚直に DFS を書くと 100^4 以上回るので間に合わない.
包除原理の DFS を呼ぶとき,x / y / z = x / (y * z) (除算は切り捨て) を用いると最初に N で呼んで割り算で再帰していくことができる (互いに素であることを使っている).よってそれ以降の結果は「n について a の i 番目以降で解く」のような形になるので,小さい値についてのメモ化ができる.a をソートしておけばこれで間に合う.

コンテスト中は,「メモ化」という考えに至らず,n が小さいときに (n, i) に関して直接問題を解く,ということを行った (テーブルのサイズの計算量).素数を並べたケースで間に合うことを確認して提出したが,1 と素数たち,というケースで TLE する様子 (ジャッジデータには入っていないと思われる).a に 1 があれば答 0 なのでその処理は加えるべきだった.

コメント

コメントの投稿


管理者にだけ表示を許可する

トラックバック

http://hos0lyric.blog89.fc2.com/tb.php/34-0a0057a8

この記事にトラックバックする(FC2ブログユーザー)

«  | ホーム |  »

プロフィール

hos.lyric

Author:hos.lyric

 

最新記事

最新コメント

 

最新トラックバック

 

月別アーカイブ

カテゴリ

検索フォーム

 

 

RSSリンクの表示

リンク

ブロとも申請フォーム

QRコード

 

QR

 

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