Entries

スポンサーサイト (この記事を編集する[管理者用])

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

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1901-2d1a6510
この記事にトラックバックする(FC2ブログユーザー)

Beta Round #56 (参加記録) (この記事を編集する[管理者用])

2011年02月20日01時から2時間,5問.codeforcesルール
[ LINK ]

A. Where Are My Flakes?

n個 (1000以下) の箱が一直線上に並んでいて,左から番号を1, 2, ..., Nとつける.
ある1個の箱にだけ中身が入っている.
中身の入ってる箱を当てるためにm個 (1000以下) のヒントが与えられる.
ヒントは,
 箱kより左の箱に中身入りの箱がある
 箱kより右の箱に中身入りの箱がある
のどちらかの形式.
中身入りの箱の可能性がある箱は何箱あるかを求める問題.ヒントに矛盾があるならそれを指摘する.

えっと,結局は….
この箱より右だよ,って言ってる最も右の箱より右で,この箱より左だよ,って言ってる最も左の箱より左.
だから,それぞれ最大値と最小値を求めて,その間の箱の数を返せば良い.
で,箱の数がマイナスなら矛盾.
書いた.合わない.
あ,箱の数が0でも矛盾だ.修正.
サブミット.

B. Serial Time!

3次元のk*n*m (10*10*10以下) のグリッドが与えられる.
各セルは空か何かで埋まっている.上下縦横6マスが隣接セルとみなす.
一番上の座標x,yのセルから辿りつけるセルが何マスあるかを求める問題.

問題の意味が分からない….何言ってるんだ….
サンプルを見る.
.の数を返してるだけのように見えるが,そんなわけないよなぁ.
あ,最後のサンプルは微妙に違う.
食器を重ねて,水が辿りつける場所の数…,食器を重ねてる部分がよくわからない.
あ,もしかして,単に3次元グリッドと思って辿りつける場所の数か? 水は上にも登れるとして.
辻褄合うな…,そんな気がするな.
それだとDFSするだけ.
書く.書いた.サブミット.

C. Mushroom Strife

ヒントからn個 (100以下) の正整数a[0], a[1], ..., a[n-1]を当てる問題.(a[k]の値は1以上10^6以下)
答えが複数あるなら何を答えても良く,答えが存在しないならそれを指摘する.
ヒントはm個与えられ,それぞれのヒントではあるペアについて最小公倍数と最大公約数
 GCD(a[i], a[j]) と LCM(a[i], a[j])
が与えられる.与えられるGCD, LCMの値は10^6以下.

どうやるんだろう….
全然一意に決まらないケースあるよな….素直な探索は無理っぽいなぁ.
とりあえず,GCDとかLCMなので,素因数に分けて考えれば良いよね.
例えば,それぞれの正整数に素因数2がいくつ含まれるか,を考える.
GCDってのはMINだし,LCMってのはMAXの意味になるな.
だからどうするんだ….
それでも,どっちにMINを割り当てて,どっちにMAXを割り当てるか,2^たくさん パターンを調べなきゃいけないが….
ん?あれ?
これ,MINの値はどっちかに割り当てないといけないし,MAXの値もどっちかに割り当てないといけない….
ってことは,1つの値を決めると,それから連結成分は全部決まっちゃうんじゃないか?
決まるよ!
2彩色可能かどうかみたいな感じでやるだけだ.
書こう.
ん,計算時間怪しくないか….
素因数2がどれだけ含まれてるか計算するのにO(枝数)のコストはかかるから,最悪で…
 10^6以下の素数の数 * 100 * 100
ぐらいかかる.これはTLEっぽい….
いや,LCMに含まれてないような素数は考えなくて良い.
与えられるLCMの個数は100*100だから,そんなに素数の種類は多くない.
異なる素数ばっかだと答えなしですぐ計算終わりそうだし.
それでいこう.
書く.
書いた.
提出.
てもやっぱり少しTLEが心配.

D. Savior

n個 (10^6以下) の街にそれぞれ笑い茸がa[k]個 (10^7以下) ある.
街sから街tに笑い茸を全部まとめて移動するには
 あるkが存在して,a[s], a[t], kがどれがどれに対応してもよいので x^2 + y^2 = z^2
という関係になければいけない.
最終的に笑い茸のある街の数を最小化したい.最小値を求める問題.

少し考えたが全然わからない.
というか問題の意味をちゃんと理解できているかどうかも怪しい.
Eに移動した.

E. Chess

一直線上のn箇所 (10^6以下) にきのこが生えている.
各きのこの重量w[i]が与えられ,最初は非減少になるようにソートされている.
時間が1経つと,隣り合う茸の間に,2つの茸の重さの和の重さを持つ茸ができる.
時間x経過 (10^18以下) した後,茸の重さが非現象になるように並び替えた.
さらに時間がy経過 (10^18以下) した.
すべての茸の重さの総和をmod p (2以上10^9以下の整数)で求める問題.

値の範囲見る限り行列べき乗っぽい範囲.
えっと,どうなるんだ.
まずはyを考えず,時間x経過後のみを考えると?
うーん.
これ両端以外は,毎回左右に分裂して3倍に増えていく感じ.
両端はちょっと違うけど.
これはすぐ計算できそう.
yはどうする?
うーん.
一番重さが小さいのと,一番重さが大きいのが端に行くだけ.
一番重さが小さいのはすぐわかるから,一番重さが大きいのは何になるかさえ分かれば良い.
うーん.
紙に書いて,小さいケースでやってみる.
最初,一番大きい2つがaとbだったとすると….
最初はb,次はa+b,次はa+2b,次は2a+3b,次は…
これフィボナッチっぽい.
あ,なるほど,フィボナッチになる.fib(x)*a + fib(x+1)*bみたいな.
これは行列冪乗か.
書く.
書いた.
サブミット!
自信ないので小さいケースで愚直にやったのと比べてみる.
あれ?なんか違う.
愚直にやるほうが間違えてるorz
うん,あってそう.

Hacks

何もせず.

Results

ABCが通って,Eが落ちる.
CはTLEが心配だったけど,全然余裕だった.まぁジャッジケースも弱かったみたいだけど….
Eはなぜ落ちたーorz

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1901-2d1a6510
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。