Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

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

2010年10月19日19時から2時間,5問.codeforces format.
[ Link ]

A. Extra-terrestrial Intelligence

100文字以下の0と1からなる文字列が与えられる.
1の文字が全部等間隔に並んでいるかどうかを判定する問題.

まあ,やるだけ.
書く.今回は入力がファイルからなので気をつける.
提出.Presentation Error.えーーー.
どういうことだ….
入力ファイルがinput.txtなのにinputにしてた,出力も.txtがなかった….
これでPEになるのか.
提出.pretest passed.

C. Bowls

上辺が下辺より広い台形を積み重ねていく.
上辺は実態がなくて,下辺はある.
順番にn個 (3000以下) 積み重ねたときの高さを求める問題.

B問題が問題文表示されないので先にこっちをやる.
この図はZOJだったかどこかで見たことあるぞ….
下からどの高さになるか決めていって,下に積んであるのに重ねたとき,どの高さになるかってのの最大値を取ればいい.
O(n^2)…,nは3000だけど,間に合うか…,多分大丈夫だろう.
書く.
すっぽり入っちゃう場合や,入らず上に乗る場合とかをテストする.
大丈夫そう.
n=3000を突っ込む.0.2秒.いけそう.
サブミット.pretest passed.

B. Fractal

与えられた図形を元に,1ステップで縦横n倍の図形をフラクタルっぽく作っていく問題.

問題見れるようになってた.
どうみてもやるだけ.
簡単.
pretest passed.

D. New Game with a Chess Piece

n*mのチェス盤の左上にコマがある.
2人でゲームを行う.順番にコマを動かしていき,行える行動がなくなったら負け.
出来る行動は,右に1マス動かすか,下に1マス動かすか,右下ななめにkマスだけ動かす.
n,m,kは1以上10億以下.

わからん.簡単な規則でもあるのではないか?
k=2とk=3の答えをn,mが50以下の部分を出力してみる.
規則が見える.
書く.
提出.pretest passed.

E. Two paths

ノード数10000以下の無向グラフで,枝が10000個以下与えられる.
空でない2つのパスの組で,枝をちょうど1度ずつ使うものを求める問題.

うーん.
次数が奇数のものが4つ以下ならできそう.
いや,全部が連結じゃなくて,2つにわかれている場合は,それぞれで1つのパスを作らなきゃ.
うーん,どうやってパスを復元するのだろう….
これって,連結の時の方が難しい!
下手に復元すると,もう片方がパス作れなくなる.
結構,これ難しいのでは….
諦めた.

Hack

Cで,底辺を突き抜ける人を2つ落として2つ失敗.
Aで問題読み間違えてる人を2つ落とす….てか,こんなのでpretest通るんかい….

Result

CとDが落ちた.
Dはhos先生がDしかRockしてないのに,Hackで点数稼いでいる時点で怪しいと思うべきだった.k=1がコーナーケース.
Cは普通に場合分けを1つ忘れていた.すっぽりと中に入ってるのだけど,つっかえてる場合.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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