Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

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

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

A. Flea travel

n個 (1000以下) のセルが円周上に並んでいる.
あるセルから,1個右に移動,次はそこから2個右に移動,次はそこから3個右に移動,…
と無限に移動したとき,最終的に全てのセルに到達するかどうかを調べる問題.

えっとー,状態数はn^2だからループを回して同じ状態に来たら終了.
状態は,今いる場所と,ジャンプ幅 mod n.
書いた.4以下で手計算と合うこと,1000近くの値でも一瞬で終わることを確認してサブミット.
pretest passed.

B. Smallest number

0以上1000以下の整数が4つ与えられる.また,+か*からなる3文字の文字列が与えられる.
kターン目 (k = 1, 2, 3) は整数を2つ選び,それを文字列のk文字目が+なら2つの整数の和に,*なら2つの整数の積に変える.
最終的に得られる数字の最小値を求める問題.

4つ固定なので全パターン試せば良いよね.
即書く.lldをI64dに直すのを忘れない.サブミット.pretest passed.

C. Pie or die

2人でゲームを行う.
n*mのグリッド上 (100*100以下) にK個 (100以下) のパイが置かれている.
先手は1個でもパイを盤面の外に出して手に入れたら勝ち.後手は先手がパイを手に入れれないと勝ち.
各ターン,先手は1つのパイを選んで上下左右に移動させることができる.
後手は,盤面の縁を1つ選んで,壁を作って,そこをパイを通れなくすることができる.
先手必勝か,後手必勝か,を判定する問題.
パイは同じセルに複数存在することができる.

時間が経つと先手は不利になるだけなので,1つのパイにのみ着目してそれを外に出せるかどうかを判定すれば良い…はず.
で,まぁ,一番近い縁に向かって動かせば良いよね.
って,最初から1ターンで勝てないなら先手は勝てないじゃん.
後は,後手は先手の移動先が縁のそばだったらそれを塞ぐだけでいい.
submit.WA.あれ.
あー,縁にたどり着いた後,左右に移動したら,その先の壁の向こうから出れるのか.
でも,縁から距離3だと,両端を塞げてしまうので,距離2以下なら勝ち.
submit.WA.むー.
わからないのでD問題を考える.
D問題をサブミットした後,コンテスト残り時間2分で戻ってくる.
うーん.
適当に,上下の壁,左右の壁から両方から距離3なら先手が勝てるのでは?
とか意味不明なコードをサブミットしたらpretest passed.
絶対こんなので正しいとは思えないのだが,残り時間がなくて何も検証できなかった.

D. Beautiful numbers

A以上B以下 (Bは9*10^18以下) の整数で,
 その整数がk (kは1以上9以下) の数字が含まれていたら整数はkの倍数であるという性質を満たす
ものの数を求める問題.

はて….
DP+包除原理な気がする.
各桁を使うかどうかで場合分けする.
それだと,使うと決めた桁の一部分しか使わない場合もあるかもしれないから包除原理.
後は,DPでmod 2520で幾つになるものが幾つあるかを求めればOK.
….
いや,これ重いぞ.
制限時間は…4秒あるし,テストケースも10個しかないらしい.
ならいけるのかな?
書いてみよう.
….
書いたけど,時間かかりすぎる+答えが全部マイナスが返ってくる.
あれぇ….
包除原理間違えてる.
まだ答えがマイナス.
あ,ループの終点まで1個足りてなかった.
答えはそれっぽいのが帰ってくるようになった.
初めてCUSTOM TEST機能使って,codeforcesでの実行時間を測ってみる.
15秒以上….ダメじゃん.
うーん….
小手先の高速化をする.
テストケース4個でローカルで8秒ぐらい.CUSTOM TESTでも8秒ぐらい.
ほう,codeforcesはローカルと実行時間だいたい同じと思えば良いのか.
うーん….
再度小手先の高速化をする.
うーん….
0~9まで全部使うかどうか2^10試す必要はないじゃないか!
0とか1とか使っても使わなくてもLCMに影響しないので2~9まで2^8通りやれば良い.
….
これで3秒ぐらいで終わるようになった.
が…,なんかさっきと答え変わったぞw
えー….
でも小さいところを出してみると合ってるように見える.
もう残り時間も少ないし,試しにサブミット.WA.
うーん.
包除原理でループで回す範囲間違えてた….
修正.サブミット,pretest passed.

E. Very simple problem

凸なN角形 (100000以下) が与えられる.
また,その対角線上にないt個 (20以下) の点が与えられる.
各点に対して,その点を含むような三角形の数をそれぞれ求める問題.三角形の頂点はN角形の頂点から3つ選んでこなければいけない.

考えてない.

Hacks

Bで演算子の順番もnext_permutationで回してるように見えたのを落とそうとして失敗した.見間違えでした.

Results

CはWA,DはTLEで落ちる.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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