2017-10

Latest Entries

スポンサーサイト

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

COOK16: November Cookoff

初参加.BUYING が解けず 4 完で 3 位.

BUYING: Buying Candles


箱が N 個あり,箱 i には A[i] 個のキャンディーが入っている.ちょうど M 個の箱を選び,キャンディーの個数の合計が K の倍数になるような方法を考える.個数の合計の最小値を求める.不可能ならば指摘.
1 <= M <= N <= 50,000,1 <= K <= 20,1 <= A[i] <= 10^9.

A[i] の小さい順にまず M 個とってしまい,そこから入れ替えることを考える.n 個除いて n 個加えたとすると,n >= 2K - 1 ならば「2K - 1 個の整数が与えられたとき,そのうち K 個を選んで和を K の倍数にできる」という事実を用いると除いたうち K 個と加えたうち K 個を打ち消すことができる.よって n < 2K - 1 を考えればよい.mod K で同じものは大きいものから除き,小さいものから加えるのがよいため,除く候補,加える候補の個数はそれぞれ高々 K(2K - 1) 個となり,O(K^4) の DP で最適値が求まる.
「」内の事実は,「和が K の倍数であるような 2K 個の整数が与えられたとき,」としても同値.K が素数のときに帰着でき,mod K でソートしたのち「i 番目または i + K 番目を選ぶ」と制限して,DP を想像すれば示せる.

除く候補,加える候補を正しく列挙できず WA.最初に vector などに入れるのではなく,大きい順,小さい順に見ていって,長さ K の配列をカウンタとして用いるのが楽だった.
コンテスト中は mod K で同じものをまとまるアイデアしかなく,遅いもの・嘘枝刈りを提出していた.

COLCHAIN: Colorful Chain


link を N 個並べる.各 link は M 色のうちどれかである.どの連続する M + 1 個の link にもすべての色が使われていなければならない.並べ方は何通りあるか mod 1,000,000,007 で求める.
1 <= M < N <= 10^5.

dp[n] = (n 個並べて,最後の M 個に重複を含まない並べ方の個数) として,この配列を計算したい.そうでない並べ方に対しては,最後の k 個で初めて重複を含むような k を状態とすれば,漸化式が立つ.すると dp の各要素は dp の以前の要素かいずれかの状態の初期値として定数時間で求まるので,全体で O(N) にできる.

GRAPLANE: Graph on a Plane


N 頂点の単純グラフが与えられる.各頂点を座標平面上の点に対応させる.各象限には均等に (最大と最小の差が 1 以下) 置かなければならない.辺が座標軸と交わる回数が最小である配置を 1 つ求める.点は座標軸に乗ってはならないが,重なってもよい.原点で交わったら 1 回と数える.
N <= 18,N は偶数.

直線 y = ±x 上に置けばよい.頂点集合 V を部分集合 S[i] (0 <= i < 4) に分割して,カット (S[i], V \ S[i]) のコストの和を最小化すればよい.S[i] のサイズが適切なものは 10,000 個くらいしかないため,まず 2 つの組み合わせを作って最後に合併させた.

MVCOIN: Moving Coins


直線状に並んだ 1,000 マスがあり,N 個のマスにコインが置かれている.コインを 1 つ選び,左に連続して並んでいるコインたちを飛び越した先のマスに動かす,という操作ができる.ただし,1 回で動ける距離は K 以下.最小何回で左に詰められるか求める.
1 <= N <= 1,000,1 <= K <= 1,000.

右から動かして集団をくっつけていくのが最適.長さ s の集団が全体として 1 マス動くのには ceil(s / K) 回かかる.

SUBANAGR: Subanagrams


N 個の文字列が与えられるので,それらのすべての「部分文字列の anagram」になっている,最長の文字列を答える.複数あるならば辞書順最小,空しかないならば指摘.
1 <= N <= 100,1 <= (各文字列の長さ) <= 100,文字はアルファベット小文字.

各文字の出現回数を数えて min をとり,a から順にその個数ずつ並べればよい.
スポンサーサイト

«  | ホーム |  »

プロフィール

hos.lyric

Author:hos.lyric

 

最新記事

最新コメント

 

最新トラックバック

 

月別アーカイブ

カテゴリ

検索フォーム

 

 

RSSリンクの表示

リンク

ブロとも申請フォーム

QRコード

 

QR

 

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