Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

SRM472 DIV1 参加記録 (この記事を編集する[管理者用])

2010年06月06日03時02分から.

Assignment

GCJ Round2が直前にあったため,時間帯がいつもと違う.
結構上位が沢山いる部屋.

EASY

2人ゲーム.1つの山でやるNim.石の数はn個.1回にとれる石の数は4^k (k=0, 1, 2, ...)
先手必勝か後手必勝か判定する問題.nは10億以下.

・・・わからん.
え,何これ,どうするのよ?
気づけば一発なの?
わからん,普通にDPで,100まで答えだしてみる!
…わからん.なんかもう提出してる人がいる.なにか気づいたの?
100000ぐらいまでDPで答えだしてみる.
後手必勝の数字だけ出してみる.
なんか,下1桁が0257でループしてる気がする,てかmod 10が0257のどれかなら後手必勝?
反例を全部出力してみよう.
100000までで反例がない!
これだ!
提出.
…,DPのコード間違えてたりしないだろうな….
大丈夫そう,次行こう.

MEDIUM

N個のカードの表に1~Nの数字が,裏に1~Nの数字が書かれている.
表,裏,それぞれ同じ数字は1回のみ.
書かれている数字が与えられたとき,N個のカードを1列に並べてできる文字列のパターンの数をmod 1000000007で求める問題.
Nは50以下.

方針が見えない…,どうするのよこれも….
これは,気づくようなものじゃないしなぁ…,ちゃんと考えないと….
サイクルに分解できるよね…,サイクルごとに考えれば良さそう.
後は,階乗とか掛けながら適当に計算できる.全部がサイクルになってる場合さえ求まれば….
全部がサイクルの場合どうする….
サイクルに分解したところで,裏表,全パターン試すと2^50….
あ,DP!?
前回使った選んだ表裏に書かれてる数字が,次のカードにも書かれているかどうか,状態数N*2でDPする.
ループするから,最初に選んだ数字も必要か,状態数N*2*2.
で,2回登場する数字の数がkのものの作り方の数を全部記録すれば良い.
配列のサイズはN*2*2*(N/2)ぐらい.いける!
行けるか…?なんか組み合わせの数も絡んでくるからちょっと心配.
でも,大丈夫だよね,書こう!
ってか,めんどくさくないか….600だからか….
書いた.合わない.合わない.合わない.
うーん.
じっくり見てみると,2個同じ数字使うのが0種類の場合の数が,全部表と全部裏の2通りとしていた.
これだけ無理やり1に直す…,え,なんかサンプル通った!
サンプル通れば大丈夫だろう,提出!

HARD

50*50のグリッドのマスがそれぞれ4種類の色のどれかで塗られている.
Kマス以下塗りなおして,隣接するマスの色は異なるようにしたい.
隣接というのは,斜めも含めて,各マスは8マスと隣り合っている.
そのような方法は何通りあるか,mod 1000000007で求める問題.

これも,取り敢えず,パッと見でわかるような問題じゃない….
まずは,同じ色が隣り合わないの,どんな感じか書いてみよう.
…,ん,隣接が斜めもあるので制約きつい.
これって,各列ごとに見ると,2文字ずつ交互に出てくるのでは.
あ,行ごとかもしれない….
とりあえず,
 ABABABABA
 CDCDCDCDC
 BABABABAB
 CDCDCDCDC
みたいなパターンか,その転置だと仮定してみると,DPで解ける.
AB,CDの選び形とか全部試す.転置も全部試す.
本当にこれで正しいの…?怪しい….
でも,書いてみよう.
…,あれ,これって,行数か列数が1の時は例外処理が必要…,いやらしい.
書いてみた.
あ,答えのオーダー違うや,こんなに単純なことじゃないんだね.
もう時間ない.諦めた.

Challenge

250は何か勘違いしてる人がいるかも? 後,250でDPしてたら撃墜する.
開けまくる.あれ,mod 5? 自分mod 10ってmod 5でいいじゃないか….
250がどんどん落ちていく.
なんか,探索してる人いた,TLEだろ,投げる!
間違った答えを返してきて落ちた.あれ,怖い.まぁ,結果オーライ.
後は…,もう落ちないなぁ.

System tests

250と600通った.
久しぶりに難しいMediumだったなぁ…,解けて良かった.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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