Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

2010 Round 1A (参加記録) (この記事を編集する[管理者用])

2010年05月22日10時から2時間30分,3問.
[ Link ]

開始前

3回あるなかのどれかで勝ち抜けられれば良いので,まだ気楽なラウンド.
2時間半なので4問か(もしくは5問?)と思ってたら3問しかなかった.

A. Rotate

N*NのグリッドにRかBの文字が書いてある.重力によって,文字は下に落ちている.
90度時計回りに回転させる.文字は重力によって下に落ちる.
縦横斜め,一直線上にRとBがそれぞれK個以上繋がっている場所があるかどうかを,それぞれ判定する問題.
small: Nは7以下
large: Nは50以下

なんか予選より問題わかりやすいなぁ,英語読解力的な意味で.
そして,やるだけ問題.largeでもサイズ小さい.
書いた.WAった.あれ?
左下の斜めのライン考えてないじゃんorz
直した.small correct.largeもついでにサブミット.

B. Make it Smooth

0以上255以下を要素に持つ長さNの整数列が与えられる.
それの隣り合う項の差をM以下にするために必要なコストを求める問題.
できる操作は以下の3種類.
 コストDで1要素を消す
 コストIで好きな場所に好きな要素を挿入する
 コスト1である要素の数字を1だけ増やすか減らす
small: Nは3以下
large: Nは100以下

DPですよねっ.
うーん,dp[残り要素の数][一つ前の要素の数字]でいいかぁ….
ま,サイズ小さいし,最も愚直に書いても実行時間大丈夫だろう.
書く.
あれ?これループしないか?
dp[a][b]から数字cを付け加えたらdp[a][c]が必要になる…,ループする.
まぁ,数字付け加えるのは,次の値に近くなるように付け加えるんじゃなければ無意味なので,そういう時だけ考えよう.
これならループしないよね!
書いた.WAった….またかい.
うーん?
次の要素を変えて,目的を満たす場合もあるよね…,なんでそれ考えてないんだ….
直した.自分で作ったサンプルが合わない.くだらないミスを潰す.自分で作ったサンプルは合った.
small correct.largeもサブミット.

C. Number Game

2人でゲームをする.
最初正整数AとBが与えられている.
二人交互に任意の正整数kを選んで以下のどちらかを行う
 A を kB だけ減らす.ただし結果はAは正整数でなければいけない.
 B を kA だけ減らす.ただし結果はBは正整数でなければいけない.
打つ手がなくなったら負け.
A1, A2, B1, B2が与えられるので,
 A ∈ [A1, A2]
 B ∈ [B1, B2]
なる先手必勝パターンの数を求める問題.
small: A1, A2, B1, B2は1000000以下,A2-A1, B2-B1は30以下
large: A1, A2, B1, B2は1000000以下

えーっと…,規則を見つけるゲーム?
とりあえず,小さい場合の答えを列挙しよう.規則わからなければそれでsmallだけサブミットしてもいいし.
A, Bが与えられたとき,先手必勝か後手必勝かを判定するには…
 大きい方が小さい方の2倍以上なら,kを何を選ぶかの選択権があるので,必勝
 そうでなければ,減らし方は1通りしかないのでシミュレーションする
さて,規則は見えるかな….
あからさまに,見えるなぁw
Aを固定したとき,必勝パターンでないのはBがある区間に入っているとき.
この区間の最大値の値って,たぶん(1+sqrt(5))/2ずつ増えてるんだよね…? 確かめる.うん,たぶんそう.
よし,書こう.
書いた.small correct.largeサブミット.

Result

あれ,B落ちた….
> まぁ,数字付け加えるのは,次の値に近くなるように付け加えるんじゃなければ無意味なので
これ嘘じゃない? (これつけててもLarge通ったのでよくわからないけど)
てか,前回使った数字も書き換え直してるし,そんなことやっちゃ駄目じゃん.
もうめちゃくちゃ….

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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