Entries

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

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

PKU 1659 - Frogs' Neighborhood (この記事を編集する[管理者用])

Problem: http://acm.pku.edu.cn/JudgeOnline/problem?id=1659
問題文が中国語なので日本語訳を書いておく.

Description
名も無き湖の周辺には大小様々な湖が n 湖,L_1, L_2, ... L_n が存在する(その中に名も無き湖も含む).
各々の湖にはそれぞれ1匹の蛙 F_1, F_2, ... F_n が住んでいる.
もし,湖 L_i, L_j が直接的に水路で繋がれていれば,その2つの湖に住む蛙 F_i, F_j はお互いを隣人と呼ぶことにする.
それぞれの蛙は自分の隣人の数 x_1, x_2, ... x_n を知っているとき,それをもとに,どの湖が水路で繋がれているか調べるプログラムを書きなさい.

Input
最初の1行にはテストケースの数 t ( 0 <= t <= 20 ) が書かれている.
それぞれのテストケースは2行からなり,1行目には湖の数(整数) n ( 2 <= n <= 10 ),
2行目には n 個の整数 x_1, x_2, ..., x_n ( 0 <= x_i < n )が書かれている.

Output
それぞれのテストケースに対して以下の様に出力しなさい.
もし,そのような湖の関係が存在しないのであれば,"NO"と1行出力しなさい.
そうでなければ,1行目に"YES"と出力した後, n * n の行列を出力しなさい.
その行列の第 i , j 成分が1であるのは,湖 i と湖 j が直接的に水路で繋がっていることを示し,0であるのは,繋がっていないことを示す.
行列の要素は1個のスペースによって区切られる.
そのような行列が複数存在するならば,そのうちの1つを出力すれば良い.
2つの連続するテストケースの間には1つの空行を出力せよ.

続きを読む

PKU 3378 - Crazy Thairs (この記事を編集する[管理者用])

Problem: http://acm.pku.edu.cn/JudgeOnline/problem?id=3378

続きを読む

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

2008年08月27日10時から.

EASY
Sort + Greedy.

MEDIUM
両側探索.やられた.

HARD
DPで数え上げ.計算量と領域量が厳しい.

(2008/08/28 15:30追記)
Overview: http://www.topcoder.com/stat?c=round_overview&er=5&rd=13506

アスガルド (この記事を編集する[管理者用])

ワングスフォルテの街解放まで進んだ.

続きを読む

アスガルド (この記事を編集する[管理者用])

友達6人できました.

続きを読む

TopCoder Marathon Match 39 (この記事を編集する[管理者用])

賞金付きだったので問題文だけ取り敢えず読んでみた.
前回の賞金付きも文字列復元問題だったような….

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

> We are pleased to let you know that your local onsite competition location will be Google Tokyo.
予想通りだったか….

アスガルド -歪曲のテスタメント- (この記事を編集する[管理者用])

とっても今更な気がするんだけども,何故か始めてみた.
しかし,思ったより古い,1998年のゲームらしい.
なんとかXPでも動きそう.

ZONEのゲームは,昔にAvaronをやったことがあるだけ.
Avaronも確か,固定敵に勝つのと負けるのと,最後2通りに分岐したと思うんだけど,どっちかしかクリアしていないはず.
というか,もう覚えてない…,ストーリーとかも断片的に覚えているだけで,大筋すら思い出せない.
ZONEのRPGのいくつか,アスガルドやAvaronを含めて,世界観が同じだったはずなので,Avaronを覚えていないのがちょっと悔しい.

続きを読む

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

Lunatic Rave(の2007年夏ぐらいのバージョン)からLunatic Rave 2 (version 080709)にしたら嘘の様に音ズレが直った.
楽しすぎる.
IIDXの専用コントローラーを態々実家から持ってきた甲斐があったってもんだ.

しかし,難しすぎる譜面が多すぎると思うんだ….
いつかできるようになるのかな?

→ LunaticRave 2 Official Site http://lunatic-rave.com/

一昨日か昨日ぐらいに,なんか懐かしい気がする音楽が2曲ほど頭の中で流れてたんだけど,何か思い出せなかった.
思い出した.
Daytime CinderellaとLilacの告白だった.

懐かしすぎると思うんだ.
僕の進む道が歪みはじめた初期時代.

→ YouTube 悠久幻想曲2・キャラソン「シャララ!~元気になあれ~」 http://jp.youtube.com/watch?v=fpGVZcS_4fE

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

2006年02月04日 (EDT).
chokudaiさんの練習会問題セット. 2008年08月12日21時から.

Match Overview: http://www.topcoder.com/stat?c=round_overview&er=5&rd=9808
Editorial: http://www.topcoder.com/tc?module=Static&d1=match_editorials&d2=srm287

EASY
Math.
2元連立1次方程式を解くだけの問題.
簡単そうなのに意外と面倒.

MEDIUM
Math または 3分探索.EASYより簡単.
微分して最小値を求めるか,3分探索を書くか.

HARD
状態遷移行列作ってn乗する問題.

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

2008年08月17日01時から.

EASY
時間に依存しない計算時間で解けるはずだけど,時間の上限も少ないし,
開始時間を全探索でもOK.

MEDIUM
Greedy.
簡単すぎて逆にこれで良いのか不安.(前回のMEDIUMがトリッキー過ぎたため)
でもGreedyの正当性の証明も難しくない.突撃あるのみ.

HARD
Math + 有理数計算を頑張る.
後は,包除原理みたいなの.なんて呼ぶのか知らない.

(2008/08/17 06:20追記)
HARDが思ってたほど簡単ではないことに気づいた.
どうするんだ,これ….

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

五山送り火 (この記事を編集する[管理者用])

を見た.
天気が心配だったけど大丈夫だった.

ぼやきいろいろ (この記事を編集する[管理者用])

どうやら正式にGoogle Code Jam 2008 Round 3突破が決まったみたい.
いきなり,未読メールが50件超えてたから何事かと思ったよ.

PS2,Beatmania IIDX 14 GOLDちょっとやってみたけど,曲自体は13の方が好きなの多かったかもしれない.
PS2は帰省中しかできないので,今度IIDXができるのは年末正月かな.
因みに,正味IIDXシリーズは2-3週間程度しかやってないので,その程度の実力.
SINGLEでHARDつけて☆10がクリアできたりできなかったり.CS13では7段,CS14では8段.

100人の囚人パズルに素直に感動した.
http://sspp2nd.blogspot.com/2008/04/100_29.html

Limitless Bit ~王国の勇士たち~がちょっと欲しくなってきた.
が,買っても消化が追いつかないよなぁ.
http://inutoneko.jp/bijyutukan/sekai/game/llb/llb_top.html

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

2006年01月21日 (EDT).
chokudaiさんの練習会第4回問題セット. 2008年08月09日21時から.

Match Overview: http://www.topcoder.com/stat?c=round_overview&er=5&rd=8081
Editorial: http://www.topcoder.com/tc?module=Static&d1=match_editorials&d2=srm284

EASY
Math.
答えが10億越えた時点で打ち切ればn^2のループでも通る.
計算すればO(n)で解ける.

MEDIUM
文字列処理 + ソート.

HARD
Math.
与えられた数を3倍して整数部分を見たりする.

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

2008年08月10日01時から,2時間,4問.
http://code.google.com/codejam/contest/dashboard?c=agdjb2RlamFtchALEghjb250ZXN0cxiM4AYM

簡単な問題がない.全部難しい.

A. How Big Are the Pockets?
線を引いて横から眺めたり(塗りつぶしたり),上下から眺めれば終わり.
とかすると,メモリが6000*6000必要なのは如何なものか….

おそらく,想定解法は,
それぞれのx(y)座標に対して,領域内に含まれるy(x)座標の最大値と最小値を覚えておく,という方針で上手くやれば解けるっぽい?

B. Portal
入っていくほうのportalは入る直前に打てばいいということで,状態空間は,マップサイズの2乗.
(自分の座標と,portal1個の座標)
壁にぶつかると設置したportalに出る,と言う感じで普通にBFS.

C. No Cheating
グラフ理論らしい.
これは単純に勉強不足です.わかりません.
Smallを通すだけなら普通のDP.

D. Endless Knight
Smallは普通のDP.
Largeは包除原理 + パスカルの三角形を(mod 素数)で書いたときの再帰構造を利用すればOK.
後, n! mod p, n=0,1,2,...,p-1 と 1/n! mod p, n=0,1,...,p-1 をメモしておけば完璧.
 1/a = a^(p-2) mod p
も使う.

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

I'veで時々曲作ってる井内舞子さんって羽越実有さんと同一人物だったのか.
初めて知った.(正確には外注らしいが)

I'veの中で,平均値を取るとこの人の曲が一番好きな気がする.

ところで,Google Code Jam Round 3終わりました.
簡単な問題が1問もなくなったうえ,4問2時間とか自分にとっては狂気の沙汰です.
1問目解けたとき1時間経過してた….
殆ど解法わからないので解法勉強してから書く.

80点とか取ってる人は凄いと言わざるを得ない.

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

2006年01月19日 (EDT).
chokudaiさんの練習会第3回問題セット. 2008年08月08日21時05分から.

Match Overview: http://www.topcoder.com/stat?c=round_overview&er=5&rd=8080
Editorial: http://www.topcoder.com/tc?module=Static&d1=match_editorials&d2=srm283

EASY
Math.
4つの軸で全て調べる.

MEDIUM
Math.
a^phi(m) = a (mod m).

HARD
実装問題.
状態遷移行列を作ってn乗する.

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

2006年01月05日 (EDT).
chokudaiさんの練習会第2回問題セット. 2008年08月07日21時から.

Match Overview: http://www.topcoder.com/stat?c=round_overview&er=5&rd=8078
Editorial: http://www.topcoder.com/tc?module=Static&d1=match_editorials&d2=srm281

EASY
Ad-hoc.
与えられた数字のみを使ってできる数字で,与えられた数字の次のものを返す.

MEDIUM
実装問題.

HARD
Math.
公差を三分探索で求める.
もしは調べるべき交差のみ調べる.

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

2008年08月07日00時から.
Match Overviews: http://www.topcoder.com/stat?c=round_overview&er=5&rd=13504

EASY
それぞれの要素に対して公差の取りうる範囲をちゃんと計算する.
恐る恐るdoubleで計算したけど,有理数で計算することも可能.
でもdoubleで十分.

MEDIUM
ちゃんと計算時間量・領域量を考えとかないと,MLE食らう問題.
うーむ….

HARD
ちょっと面倒な普通のDP.

Next Generation Contest - 5 (この記事を編集する[管理者用])

2008年08月03日20時から,5時間,10問.
http://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_onlinejudge&Itemid=13&page=show_contest&contest=202

1位: 8 Accepts
8 Accepts: 3人
7 Accepts: 27人
6 Accepts: 13人
参加人数: 264人

(最終追記: 2008/08/05 08:50)

続きを読む

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

2008年08月03日1時から,2時間,4問.

Round 1に比べて問題数が増えて時間が足りなくなったかわりに,極端に難しい問題がなくなった気がする.
しかし,時間が足りない….
一応Round 3には進める模様.

ところで,Large Inputをダウンロードしてから計算量を見積もり間違っていることに気づいて,
8分間でコードを一部書き直してサブミットして通った.
通ったから良かったけど,怖い怖い….

A. Cheating a Boolean Tree
一番簡単な問題からDP.結構面倒.

B. Triangle Areas
Ad hoc.
1点を原点に固定して,後はなんとかする.

C. Star Wars
絶対値を展開する.
 x ± y ± z
を4通り計算して,もっとも差が大きくものを採用すればよい.
後はbinary search.

D. PermRLE
普通のDP.巡回セールスマン問題(TSP)系.別に難しくないはず.
なんでこれが一番点数高いのかわからない.


(2008/08/03 15:50追記)
何かC問題がRejudgeされる(された?)模様.
まぁ,現状85点あるので,Cで-30点,ソースファイル送るの間違えてて-5点食らっても50点あるのでRound 3には行けると思うけども.

ところで,他の人のブログを漁ると,解き方が違ったり賢すぎる人がいて楽しい.
かなり多くの人が,C問題は座標を45度ずつ傾けて,電波の届く範囲を立方体にしてやったらしい….
確かにソース見たら45度回転してるよ!

(2008/08/03 18:00追記)
C-LargeのRejudge終了した模様.ボーダーには殆ど変化なし.
自分は65点→85点になった.もふもふ.

Maximum-Cup 2008 (この記事を編集する[管理者用])

2008年08月02日14時から,4時間30分,8問.

オープン参加含めて,
1位は6 Accepts.
おそらく,6 Acceptsは3人.
参加人数は28人ぐらい.

僕はオープン参加.

A. Opinion Poll
Sort.

B. Pirates of the Mediterranean: The Curse of the Black Perl
問題文をよく読む問題 + Dijkstra.

C. iDOL M@STER
DP + 経路復元.

D. FAN Mail Analyzer
文字列処理 + 実装問題 + simple DP.

E. Sub Version Network System
謎.
何も考えないと計算時間量 50^2 * 3^50 程度.

F. Maximum Rectangular Window
幾何 + これ(http://algorithms.blog55.fc2.com/blog-entry-132.html).
面倒.

G. TOKOSHI's Roll Cake Cutting Problem
simple DP.

H. Forever...?
謎.
入力m<2^31に対して,自然対数の底をeとして,
 ne - floor(ne)
が最小となるような 1<=n<=m を出力する問題.

LINKは結果出たら追記する,覚えていたら.

(2008/08/04 2:10追記)
E-Hの解説がEmKさん(Judgeのうちの1人)のBlog( http://d.hatena.ne.jp/EmK/20080803 )にあった.
Eは本番中にこれきっと最小カットなんだよね?と思いながらもグラフが書けなかった.
実はおしいところまでいってたのか.
でも,こんなグラフ思いつかない.

Appendix

Recent Articles

ブログ内検索

Ads


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