Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

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

2010年06月05日23時から2時間30分,4問.
[ Link ]

A. Elegant Diamond

ダイヤモンド型に文字列に,新しく何文字か付け加えて,左右対称かつ上下対称なダイヤモンド型文字列にしたい.
付け加える最小の文字の数を求める問題.

やるだけの実装問題っぽいけど,どうやるんだろう….
とりあえず,Round 2なので落ち着いて,問題を読んでいこう.

B. World Cup 2010

2^pチームでトーナメントが行われる.pは10以下.
各対戦のチケットの価格が与えられる.
各チームに対して,そのチームの対戦を最大で何個まで見逃しても良いか,という数字が与えられる.
勝敗がわからないとき,買うチケットを選んで,コストを最小化する問題.
small: チケットの値段は全て1
large: チケットの値段は0以上100000以下

…,どうみてもDPに見える.
segment treeみたいな感じのツリー作って,
 今みているノード,今までその集合は何回見逃したか
を状態にしてDPすればいい.
てか,smallだけ解く方法とかが分からない.
まぁ,これは…,解ける.次の問題読もう.

C. Bacteria

ライフゲーム.
 生きていて,上か左が生きてたら,次のターンも生きてる
 死んでて,上と左が生きてたら,次のターン生きる
 それ以外は死ぬ
全滅するまでにかかるターンするを求める問題.
最初の生きてるマスの集合は,長方形型のグリッドで与えられる.
small: 盤面のサイズが100*100以下,長方形の数は10以下
large: 盤面のサイズが1000000*1000000以下,長方形の数は1000以下

うーん,問題文のサンプル見ると,なんか右下にうにょうにょ動いていく感じ.
わからんから,次の問題見よう.

D. Grazing Google Goats

2次元平面上の,N個の点p[i]と,M個の点q[i]が与えられる.
各q[i]に対して,
 p[k]を中心として,q[i]を通る円を考えて,そのN円の共通部分の面積
を求める問題.
small: N=2, Mは10以下 large: Nは5000以下,Mは1000以下

問題文読みにくい.図だけ見て多分理解.
largeが無理ゲーにしか見えない.

B. World Cup 2010

これはDP書くだけ.
書こう.
…めんどうじゃないか,これ.
普通にheapとかsegment treeっぽくノードに番号つけると,入力と上下入れ替えないといけない.
色々書くのが面倒….
まぁ,時間掛かっちゃったけど書いた.一発でサンプルはあった.
smallサブミット,correct.largeもサブミット.

A. Elegant Diamond

とりあえず,実装するだけっぽいので,やってみよう.
でも,どうすればいいの…,ちゃんと考えないと.
小さい対称なダイヤを探して,それを有効活用するように,やれば良い.
で,見つかった最大のサイズをr,もともとのサイズをnとして,答えは
 (2n-r)^2 - n^2
だ.
・・・本当か?
いや,真ん中の方で,対称なダイヤ見つけても,それを有効活用できないし….
4つの頂点のうち,どれかを含む最大サイズの対称なダイヤを見つければ良さそう…かな.
書いてみる.
二次元配列に落として…,めんどうだなこれ.
数字は1桁だっけ?
1桁だ.
アスキーアートのまま扱おう.
で,90度回転する関数用意して,4回回転しながら一番上の頂点を含むような対称ダイヤの最大サイズを全探索する.
書いた.
smallサブミット.Incorrect.がーん.
しばらくコード見なおすけどよく分からない…,やばいぞ….

C. Bacteria

とりあえず,Cのsmallはシミュレーションするだけで良いはず.
部分点を拾っておこう.書いた.smallサブミット.correct.

A. Elegant Diamond

あ,頂点を含まなくても,小さい対称ダイヤが辺上にあれば有効活用できる….
直そう…,これ計算量大丈夫か?
最悪ケース(largeの場合の)を入れてみる.作るの面倒だった.0.2秒ぐらい,まぁ大丈夫かな….
small提出.Incorrect….
うーん….
ちょっといろいろ出力してみよう.
回転がちゃんとできてない!
変数名打ち間違えてるorz
修正.サブミット.Incorrect.むーん….
自分で色々作ったケース全部合うんだけどなぁ….
プログラムが間違えてる?考え方がマズイの?

D. Grazing Google Goats

とりあえず,なんかこのままだと500位以内怪しいので,Dもsmallだけ拾っておこう.
えっと…,2円の重なる部分のライブラリは…,あれ,僕作ってなかったのかな,見つからない….
もういいや,n円で覆われる部分の面積を計算するライブラリと包除原理使って無理やり求める!
smallサブミット.correct.

A. Elegant Diamond

いろいろわからず,とりあえず,-O0 (最適化なし)でコンパイルし直して送ってみるとかいろいろ試す.
まぁ,もちろん全部Incorrect.

Result

B両方と,CとDのsmallのみ正解.
Aができないとか酷い….
普通にデカイダイヤの中心を全探索すれば良かった,そういう方法が何故見えない….
はまったら,違う視点から見て,全部コード書き直しても良いかも.
危険な位置だったけど,なんとか通過.
次は正念場なので,今回の結果は気にせず次頑張ろう.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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