Entries

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

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

SRM412 DIV1 (この記事を編集する[管理者用])

2008年07月31日20時から.

後2分あれば1000ptが解けたなぁ…,最初プラグインを外しててその辺で間誤付かなければいけたかも.
(Intermission中に書きあがった,practiceでsystem testも通った)
まぁ,しょうもないバグ埋め込まなければ余裕で書けたので,それが一番悪い.

EASY (250pt)
simple DP.
良くある問題.

MEDIUM (500pt)
英文読解 + Greedy.
取り敢えず,問題文が長い.問題は単純な実装問題.

HARD (1000pt)
DP + 法則に気づけば勝ち.
観察すると,x,y>0, x!=yのときは絶対に勝てることがわかる.
証明はEditorialに期待.

(2008/07/31 22:10追記)
今回のHARDみたいな勝ち負けを判定するゲーム系の問題は,小さい部分だけ計算して出力してみるとパターンが見えてくることが良くあります.
( 今回の場合はこんな感じ img )
解法が見えないときは取り敢えず試してみると良いかもね.
ゲーム系の問題だけじゃなく一般に言えることだけれども.

(2008/07/31 22:20追記)
Arena, Chat Room 1
(22:03:59) Soultaker> Or was it just a matter of DP or search that had to be optimized enough to run in time/memory?
(22:04:10) writer> Soultaker: yes, O(N), notice that one can lose only on diagonals and orthogonals
(22:04:24) writer> (I have no mathematical proof for that)

あれ…,証明は…?orz

UVa Vol.112 (この記事を編集する[管理者用])

UVaのVol.112にちょっと粘着してみた.(img)
残りはどうやれば良いのかなぁ….

UVa 11256 - Repetitive Multiple (この記事を編集する[管理者用])

ようやく11256の解き方がわかった.
嬉しかったので単発の問題解説でも書いてみる.
Vol.112は結構解いたけど,まだ解ける問題は残ってるかな.

続きを読む

なのは (この記事を編集する[管理者用])

魔法少女リリカルなのはが映画化するらしいですね.
個人的には映画はあんまり好きじゃなくて,
普通に1クールか2クールぐらいのアニメをまったり見るのが好きなのだけども.

でも,まぁ,またちっちゃいなのはさんに会えるのは嬉しいことです.

それより,とらハ1と2は少しやったのだけども,3はやってなくて,気になるので,
とらハ3をアニメ化したりしないかな….

Waterloo Local Spring 2008 (この記事を編集する[管理者用])

2008年06月21日18時から3時間,5問.
1問ジャッジデータが間違ってて最近Rejudgeされた.

参加人数: 75人
1位: 4 Accepts
4 Accepts: 2人
3 Accepts: 2人

A. Trainsorting
LIS.

B. Classified
greatest lower boundに置き換えて置き換えていくシミュレーション.
どうやれば良いのかわからない.
というか,glbって絶対存在するのだろうか,その辺はちゃんと問題読んでないだけ?

C. Hot Spot
BFS.ちょっと面倒な実装問題.

D. Snakes and Ladders
簡単なシミュレーション.
ジャッジデータが間違ってたのはこの問題.

E. Balance
幾何.
y=0でぶった切って,上下それぞれ重心を求める問題.

http://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_onlinejudge&Itemid=13&page=show_contest&contest=201

Google Code Jam 2008 Round 1B (この記事を編集する[管理者用])

2008年07月27日01時から2時間,3問.

1Aの方が楽しかった.
1Bは典型的な問題といった感じかなぁ.
1Bは閃きで何とかなるわけじゃなくて,ある程度アルゴリズムとか詳しくないと辛い感じもする.

A. Crop Triangles
mod 3で落とせば終了.

B. Number Sets
エラトステネスの篩っぽくunionするだけ.

C. Mousetrap
ヨフセスかと思ったらそんなに単純ではなかった.
ちゃんとしたデータ構造を使わないと(多分)駄目.

ニコニコ動画 (この記事を編集する[管理者用])

動画の作り方とかちょっと気になったので,なんとなく調べて1個作ってupしてみた.

SRM411 DIV1 (この記事を編集する[管理者用])

2008年07月24日10時から.

EASY (250)
DP + 文字列操作.
EASYから,こんな結構面倒なDPとか…,と思ってた下位層も皆ちゃんと解いてた,しかも結構すばやく正確に.
皆凄いな.

MEDIUM (500)
Ad-hoc.正確に実装できますか系.
拡大グラフ作って線引いて塗りつぶしてる人が賢すぎると思った.
500点問題だし,ケーキの形を長方形じゃなくて円にしても面白いんじゃないかと思った.
多少面倒になる.

HARD (1000)
グラフ理論.
解いた人0.解法謎.

http://www.topcoder.com/stat?c=round_overview&er=5&rd=12183

A Malaysian Contest (この記事を編集する[管理者用])

2008年07月12日23時から5時間,10問.

参加人数: 215人
1位: 8問 Solve
8問 Solve: 4人

A. Square Numbers
Easy.

B. Age Sort
バケットソート.

C. Commandos
グラフ理論.BFS+BFS.

D. Even Parity
1列だけbrute-force.

E. Count the Polygons
枝刈り探索.

F. Largest Prime Divisor
エラトステネスの篩.

G. Pythagorean Triangles
形だけ全部作って,横幅,縦幅ごとにカウントしていく.
後は,入力に対する答えを全部計算して答えだけ送る.
取り敢えず,TimeLimit 4secでジャッジ解法が5.536secってなってるのですが….

H. Substring
Accept 0.というか,ジャッジ入出力間違えてるんじゃ…?
グラフ(遷移行列)をちゃんと作って,後はループ回すだけ.

I. Treasure Hunt
グラフ理論.
問題は,枝を一度だけ通る閉路で,頂点をできるだけ沢山通るものを求めよ.(通った頂点数を出力)
制約は,頂点数10000以下,枝1000000以下.
解法わかんない.

J. Square Sums
Easy.

http://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_onlinejudge&Itemid=13&page=show_contest&contest=203

Google Code Jam 2008 Round 1A (この記事を編集する[管理者用])

2008年07月26日10時から2時間,3問.

これは楽しすぎる問題セット.
てか,1回戦から普通に難しい….
一応2回戦には進めるみたい.

A. Minimum Scalar Product
Sort + Greedy.
小さいものと大きいものをぶつける,ってのが0とか負の数とか含まれててもOKであることを確認するのに時間かかりすぎ,自分.

B. Milkshakes
Ad-hoc.
昔解いた問題のはずだけども,解けなかった….
At most one of the types a customer likes will be a "malted" flavor.を見逃してたのが解けなかった原因だった.(2008/07/26 23:30修正追記)

C. Numbers
Math.気づきのゲーム.
ペアの相方(3-sqrt(5))^nを思い出せば解ける.

Google Code Jam 2008 Qualification Round (この記事を編集する[管理者用])

Google Code Jamが今年も始まりました.
予選ラウンドは 7月17日午前8時から7月18日午前8時まで.(日本時間)

A. Saving the Universe
(Greedy or DP) + 文字列操作.
頭の悪いDPしか思いつかなかった…,要反省.

B. Train Timetable
Greedy + Simulation.

C. Fly Swatter
幾何 + 積分.

この辺の人が良くまとめてくれています.
http://www.icefree.org/~vvp/194.html

ままにょにょ 異空窟Lv. 1204 (この記事を編集する[管理者用])

メインキャラは全員レベル4桁突破.

レイラさんメインキャラ化.
かわりにファネル降格.

リックあたりが次のメインキャラ昇格候補.
その他,今回メインキャラ以外でレベルが上がっているのも,未来のメインキャラ候補.

続きを読む

SRM 409 DIV 1 (この記事を編集する[管理者用])

日本時間2008年07月11日00時から.

とっても簡単な問題セット.( Summary )
Yellow Coder上位層は全部解きたい.
Red Coderはできるだけ素早くかつミスなく解きたい.
Blue CoderはもしかしたらHardが解けるかもしれないチャンス.

250pt: 書くだけ.添え字が面倒でこんがらがりそう.しっかり頭の中を整理する.
600pt: 問題文が読みにくい.gnomesAvailableから1ずつ減らしながら全部チェック.
900pt: 確率なので数学苦手な人は苦手かも.各セルごとに塗りつぶされる期待値を求めて足せばよい.

イロモネア ゴールドラッシュ (この記事を編集する[管理者用])

ルールは,審査員が10人程度いて,ランダムに選ばれた数人を全て笑わせればクリア.
ただし,選ばれる人数は,1回目が3人,2回目が4人,3回目は5人.

クリアする確率.
審査員が全員でn人いて,m人笑った場合は,C(m,x)/C(n,x).
ただし,1回目はx=3,2回目はx=4,3回目はx=5.

思ったよりも,ちゃんと後半になるほど辛くなるのがわかる.
3回目は2人笑わない人がいると辛いか.

m/n1回目2回目3回目
5/80.1785710.0714290.017857
6/80.3571430.2142860.107143
7/80.6250000.5000000.375000
8/81.0000001.0000001.000000
5/90.1190480.0396830.007937
6/90.2380950.1190480.047619
7/90.4166670.2777780.166667
8/90.6666670.5555560.444444
9/91.0000001.0000001.000000
5/100.0833330.0238100.003968
6/100.1666670.0714290.023810
7/100.2916670.1666670.083333
8/100.4666670.3333330.222222
9/100.7000000.6000000.500000
10/101.0000001.0000001.000000
5/110.0606060.0151520.002165
6/110.1212120.0454550.012987
7/110.2121210.1060610.045455
8/110.3393940.2121210.121212
9/110.5090910.3818180.272727
10/110.7272730.6363640.545455
11/111.0000001.0000001.000000
5/120.0454550.0101010.001263
6/120.0909090.0303030.007576
7/120.1590910.0707070.026515
8/120.2545450.1414140.070707
9/120.3818180.2545450.159091
10/120.5454550.4242420.318182
11/120.7500000.6666670.583333
12/121.0000001.0000001.000000

ままにょにょ 異空窟Lv. 1160 (この記事を編集する[管理者用])

現在までのアイテムゲット
ドラ猫の鈴 5個
雷入りボール 9個
身軽の羽 4個
ダイヤチェーン 5個

あれ,3時だ…orz

続きを読む

戦女神ZERO 4章終了 (この記事を編集する[管理者用])

もしかして固定敵は全部,敗北時のメッセージが用意されてたりしますか…?
無駄なところで頑張ってるな…,こういうの好きです.

-----
ver 1.01
セリカ Lv.103
アビルース Lv.98
パズモ Lv.93
リ・クティナ Lv.92
ペルル Lv.95
save data 1/2
save data 2/2

戦女神ZERO 3章終了 (この記事を編集する[管理者用])

第3章はダンジョン1つだけ.
必殺技がランクSまで使えるようになった.

-----
ver 1.01
セリカ Lv.82
save data 1/2
save data 2/2

typo (この記事を編集する[管理者用])

[新着状況]
異空窟Lv. 1150
キャラGET 86/92
別次元面の攻略 11/54

[進捗状況]
異空窟Lv. 1150
キャラGET 86/92
別次元面の攻略 11/54

次回から直しますorz

ままにょにょ 異空窟Lv. 1150 (この記事を編集する[管理者用])

バレスゲットで宝箱キャラクター全員集合.

取り敢えず,キャラのレベル上げ後回しで異空窟レベルを進めるだけ進めてみた.
ドラ猫の鈴が欲しい….

続きを読む

戦女神ZERO 2章終了 (この記事を編集する[管理者用])

2章終わり.何章ぐらいあるのかな?

スキルの攻撃力が高すぎる気がするなぁ….
というか,全体的に味方も敵も攻撃力が高くて脆いのかな…?
一発決めるまで耐え切れれば勝てる,という感じ.

-----
ver 1.01
セリカ Lv.64
save data 1/2
save data 2/2

戦女神ZERO 1章終了 (この記事を編集する[管理者用])

結構面白い.

カバキの砦をクリアしなくても大聖堂で準備は万全とか選択肢が出てきた.
本気で準備が万全じゃねぇ….
カバキの砦は隠し通路に気づかず,ずっと彷徨ってましたよ….

鉄屑の谷で開かない扉あるんだけど,あれは遣り残したことではないと思いたい….

クライナ集落で虐殺しまくったのは,たぶん拙かったんだろうなぁ….
一度クリアしたら攻略サイトみながら2周目やろう….

-----
ver 1.01
セリカ Lv.44
サティア Lv.38
パズモ Lv.34
save data 1/2
save data 2/2

戦女神ZERO 序章終了 (この記事を編集する[管理者用])

戦女神ZEROをプレイ開始.取り敢えず序章を終わらした.
実はエウシュリーのゲームでクリアしたことがあるのが皆無だったりします.
多分,色々頑張って作ってるメーカーさんだと思うし,自分好みのゲームセンスな気もするのですが.

ということで,楽しみにしてやります.

-----
ver 1.01
セリカ Lv.21
ダルノス Lv.25
カヤ Lv.24
save data 1/2
save data 2/2

ACM/ICPC 2008 国内予選 (この記事を編集する[管理者用])

結果でました.
やっぱり東大は強いですね.
というか,全問解いたのが3チームもいたのは凄いです.
問題見て1チームぐらいは全部解きそうだなーとは思ったのですが.

ACM/ICPC 2008 国内予選 (この記事を編集する[管理者用])

現在開催中ですが,取り敢えずF以外は解いたつもりになってみた.
(サンプルは通るプログラムを書いた)
5問で1時間10~1時間20分ぐらい.

A. Brute-force

B. 変形エラトステネスで全部月曜土曜素数を求める

C. 実装.文字列処理.

D. 国内予選おなじみ,変形ダイクストラ.
ダイクストラを真面目に書くのは面倒だったので,更新されなくなるまでベルマン・フォードっぽく.
これだと最悪計算量がだいたい(30*30*4)^2=3600^2なのでオンラインジャッジでは危険かも.

E. 幾何.線分と線分との距離って思ってたより面倒なことがわかった….

F. 1が36個以下らしいので,たぶん頑張って探索…?

闘神都市3 (この記事を編集する[管理者用])

今頃気づいた.
闘神都市3今冬発売予定.
これを見て3時間,未だに興奮が収まらない.

闘神都市は1990年,闘神都市2は1994年発売か….
プレイしたのはもっと後だけど,ずっと待ち続けてきましたよ!

SRM 406 DIV 1 / SRM 407 DIV 1 / SRM 408 DIV 1 (この記事を編集する[管理者用])

SRM 406は難しい問題セット.
折り紙 (500pt) が計算時間見積もりにくい…,最悪12*2^24ぐらいだけど,2^24よりは少ないでしょ…と思えばいいのか.
k-th shortest path (1000pt) はまだ解法理解してない.Editiorialがわかりやすいと良いな.

SRM 407はDP+DP+最小費用流の問題セット.
DPできる人にとっては250ptも500ptも単純作業.
250からDPというのは辛い人も居るような気がする….
最小費用流のライブラリ持ってなかったのが痛すぎた….いい加減書かないと.

SRM 408はGreedy+Greedy+Greedyという魔の問題セット.
Greedyは頭悪いと辛いのよ(ToT
500ptはsubmitした後に,自分が書いたGreedyが正しいかどうか悩みに悩んだ….
1000ptが未だにどうすれば良いのかわかってない….

SRM 406は日本時間2008年06月18日10時から.
SRM 407は日本時間2008年06月27日00時から.
SRM 408は日本時間2008年07月01日20時から.
SRM 406: http://www.topcoder.com/stat?c=round_overview&er=5&rd=12178
SRM 407: http://www.topcoder.com/stat?c=round_overview&er=5&rd=12179
SRM 408: http://www.topcoder.com/stat?c=round_overview&er=5&rd=12180

Appendix

Recent Articles

ブログ内検索

Ads


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