Entries

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

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

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

2008年10月29日午前10時から.

やっぱりこの時間帯のSRMは苦手らしい….
ケアレスミスでMEDIUMもHARDも落とした.

EASY (300pt)
n 個の駒がチェス盤にいて,1回の行動でどれかの駒を縦横に1マス動かせる.
k 個以上の駒が同じ場所に辿り着くための最小手数を求める問題.

座標軸ごとに独立に考えれて,皆が向かう先は,今駒がいる場所の何処かに向かえばよいので,
向かう先の候補は n^2 しかなくて全パターン試す.

MEDIUM (500pt)
n × n のチェス盤で,2つの駒がおいてあって,交互に自分の駒を動かす.
動ける範囲はEASYと同じ.
と思い込んでたら,後手は上下左右1マスか2マス動けるらしい….
相手の駒と同じ位置に行けば勝ち.
勝つ側は最小手で勝ちたい,負ける側は最大限勝負を長引かせたい.
勝つか負けるか?何手で決着がつくか?を求める問題.

ベルマンフォードっぽく更新していって更新がなくなったら終わり.
相手が良くなるのだから,自分は悪くなる可能性もあるのに,それを考慮してなくて落ちた.

HARD (1000pt)
Polyaの定理,数論.
n × n のチェス盤の上に,いろいろな色の駒を全部置くパターンは何通りか?

n が奇数のとき,真ん中に何も置かないという選択肢を考えてないとか間抜けすぎた.

(2008/10/29 21:25 EDIT)

UVa 11546 - Olympic Swimming (この記事を編集する[管理者用])

[ Link ]
BUET:: CSE Day Programming Contest 2008で解けなかった問題.( blog )

全てのコースで同じ数だけハードルを含む区間のうち,最長のものは何メートルですか,という問題.
コースの数は30以下,コースの長さ50000メートル以下,各コースのハードルの数は5000以下.

最後のコースのハードルをなくすかわりに,最後のコースにハードルがある場所に,他のコースには -1 個のハードルがあるとする.
そうすると, k - 1 個のコースの全てで,ハードルが合計で 0 個ある区間のうち最大のものを求めれば良い.

0 <= x <= コースの長さ に対して,
0 ~ x の区間にあるハードルの数を全て計算して,
 x = y, z
に対してハードルの数が同じなら, yz の区間にはハードルが0個.

O( コースの長さ * コースの数 ) で解けるけれども,それでも結構制限時間が厳しくて,あまりに効率悪い実装をするとTLEをもらえる.

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

[ Link ]
2008年10月06日18時から2時間,4問.

一転して問題の難易度格差が小さい.
どれも難しいのに,一番難しいのはそれほど難しくない.
APACが一番バランスが取れてた気がするなぁ.

A. Scaled Triangle
いきなり幾何.
三角形と,それを回転 + 縮小した三角形が与えられる.
同じ点が重なっている場所があればそれを答えよ,という問題.

B. Painting a Fence
1~10000までのフェンスに色を塗りたい.
各業者に頼むと,ある区間のフェンスをある色に塗ってもらえる.
3色までしか使ってはいけない場合に,最小で何個の業者に頼めばいいかを求める問題.

使う色3色を固定した場合,後はGreedyに塗れば良い.
同じ色の業者をグループ化することによって,限りなく O( n^3 ) に近づくとは思うのだけども,計算量が見積もれない.
単純に効率悪い実装してなければ O( n^4 ) で間に合うらしい.

C. Rainbow Trees
Ad-hoc.
Treeの枝に色を塗る.ただし隣り合う2つの枝,3つの枝がそれぞれ違う色に塗らないといけない.
Ad-hocに塗っていって,塗るときに塗ることができる色の数をかけていけば良い.
だけど,塗る順番をちゃんと考えないと駄目.

D. Bus Stops
バスが K 個,バス停が N 個ある.
それぞれのバス停に1個のバスが止まるような方法がいくつあるかを答える問題.
バスが止まる間隔等に制約がある.

状態遷移行列を作ってべき乗を求めるお馴染みの問題.

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

[ Link ]
2008年09月30日01時30分から2時間,4問.
今更感ぷんぷん.

問題の難易度格差が大きい,というかDが難しすぎる.
Bは良問だと思った.

A. Mixing Bowls
Tree + (Greedy or DP).
料理するときに必要なボウルの数の最小値を求める問題.
Treeを作って葉から必要なボウルの数を計算していく.
自分の子供のうちでたくさんボウルが必要なものを先に作ればよい.

B. Code Sequence
ある数列の k番目の数字は k を2進数表示したときに j 桁目が1とすると, ∑ C_j である.
C_jはある知らない定数.
その数列の途中からいくつか与えられたとき,その次の数を答えよ,もしくはunknownを返せ,という問題.

j桁目が0から1になるのは 2^j 回ごとに起こり,そのときの前の項からの変動は定数 ( C_j - ... - C_1 ) ということに気づけばOK.

C. Test Passing Probability
4択問題が Q 個あって,それぞれの問題に対して,それぞれの選択肢が正しい確率がわかっている.
合計で M 回答えることができて,一度で全部に正解したら終了.
最適戦略をとった場合正解することができる確率はいくらか?

DPでそれぞれ答えたときの正解の確率を計算して,大きいほうから M 個足せば良い.
ただし,すべてのパターンの確率を計算したら死ぬので,大きいほうから M 個だけ残しながら計算する.

D. King
Largeが100点中38点を占める最難関問題.結局Accept数0.
ところどころ移動できないチェス盤の上で交互にKingを動かす.
ただし,同じ場所には1回しか行けない.
先手必勝か,後手必勝かを判定せよ,という問題.

チェス盤の各マスのノードとして,そこから1回で動ける場所に枝を張る.
最初のKingの場所を含めて動ける場所を全て含めて最大マッチングを求めて,
最初のKingの場所を除いて最大マッチングを求める.
前者のほうがマッチング数が多ければ先手必勝.
なぜなら,先手は最大マッチングにそって動かせばよい.
後手はどう動かそうと,最大マッチングに含まれる別のノードに行くしかない(もしくは動かせない).
なぜなら,最大マッチングに含まれないノードに移動できたとすると,今まで移動してきた枝を全て反転させることで,最初にKingがあった場所を含まないで,同じ数のマッチングができてしまうから.

最大マッチングを求めるにも,2部グラフではないので工夫が必要.
枝は前の行から次の行までにしか張られないので,各行総当り+DPで求まったりする.

UVa 11542 - Square (この記事を編集する[管理者用])

[ Link ]
BUET:: CSE Day Programming Contest 2008で解けなかった問題.( blog )

1以上10^15以下の整数からなる集合のサブセットのうち,全ての要素の積を取るとsquare numberとなるものはいくつあるか,という問題.

素因数分解すれば,連立一次方程式
 A x = 0
の解の数を求めればいいことになる.ただし mod 2 で考えている.
そして,解の数は 2^{解空間の次元} だったりするわけで, A の rank を求めれば終わりだった.

UVa 11531 - Solve the Broken Maze (この記事を編集する[管理者用])

[ Link ]
Another Bangladeshi contestで解けなかった問題. ( blog )

左から右に抜ける経路が存在する場合があるかどうかを判定する問題.
DPで解ける.
0 列目から k - 1 列目まで状態を列挙しておいて,
それを使って,0 列目から k 列目までの状態を作る.
0 列目から k 列目までの状態が保持してる情報は,
 0 列目の何行目の左から入ったときにどこにたどり着くか
 k 列目の何行目の左から入ったときにどこにたどり着くか
などなど.
(UVaのBBSに書いた. [ Link ] )

ACM/ICPC アジア地区予選 (この記事を編集する[管理者用])

もうすぐ ACM/ICPCアジア地区予選 @ 会津 ですね.
東大頂上決戦はどうなるのかなー,わくわく.
後,とりあえず京大頑張れー.

BUET:: CSE Day Programming Contest 2008 (この記事を編集する[管理者用])

2008年10月25日20時から5時間,9問.
[ Link ]

E, F, I以外の6問解いた.
Cが解けたのは満足.
EやIが解けないのは反省するべきなんだろうなぁ.

UVaのコンテストランキングの順位が1個上がった.
もう一歩なんだけど,その一歩が果てしなく遠い.

A. Chess Queen
Math.
n × m のチェス盤の上に色が違う2つのQUEENをお互いが攻撃できる状態でおく.
そのような置き方は何通りありますか,という問題.
n, m <= 1000000
計算するのみ. summationをめんどくさがって O( n )のループまわしたらTLEもらえた.
O(1)でやるべし.

B. Another Word Game
典型的なDP.
ただし,単語の数が多いので,一致する単語があるかどうかを O(1) or O( log(単語数) )とかで調べれるようにしておく.

C. Sultan's Chandelier
文字列処理 + ルートつきTree上のDP + Polyaの定理.
あえて細かいことまで書かない.とりあえず面倒.

D. Decoding
今回の簡単問題.文字列処理 + やるだけ.
ランレングス形式の文字列を解凍する.

E. Square
要素数100以下で,1以上10^15以下の整数からなる集合のサブセットのうち,
全ての要素の積を取るとsquare numberとなるものはいくつあるか,という問題.
ただし,答えはlong longで収まり,集合の各要素は,500以上の素数で割り切れることはない.

F. Two Points and Curious MumboJumbo
読んでない.
が,とりあえず絵がやばそう.
AC数もやばそう.

G. Recruiter's Problem
グラフ理論,最大流(2部マッチング).
AC数が少ないのが謎.
まず,最大流を求めて,後はGreedyに番号の小さい人から決め付けて,再度最大流を流す.
流量が減っちゃったら却下,減らなかったら決め付けた案を採用して次の人を決めにかかる.

制限時間2秒で,1.6秒もかかってしまったので結構ぎりぎり.
マッチングは最大流に帰着する方法しか知らないので,ちゃんとマッチングを勉強するべきなのかもしれない.
後は,安定結婚とか,割り当て問題系も全く知らないのでその辺も勉強すべきな気がする.

(2008/10/26 02:00追記)
0.08sとかで通している人もいるので,もっと効率的な解法があるっぽいか….
(追記ここまで)

H. Avoiding Jungle in the Dark
ダイクストラ.
ノードは今いる場所×今の時間で24000程度で,次数は高々17.

この問題の真の恐ろしさはそんなところじゃなくて,問題文をきちんと読まなければいけないところ.
細かい条件があったり,さいたまチックなトラップがあったり.

I. Olympic Swimming
全てのコースで同じ数だけハードルを含む区間のうち,最長のものは何メートルですか,という問題.
コースの数は30以下,コースの長さ50000メートル以下,各コースのハードルの数は5000以下.
わからない.

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

敵レベルもだいぶ上がったので,そろそろレベル上げをしようと思いだしたところ.
もうそろそろ黒崎社長をメインキャラ化するかもしれない.

続きを読む

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

2008年10月19日18時から6時間,9問.
[ Link ]

予約投稿でコンテスト終了時投稿されるようにしとく.

A. Strange Tax Calculation (謎)
平面上に n 点与えられる.
そのうち,ランダムに3点を選んでできる三角形の中に含まれる点の数の平均値を答える問題.
n <= 1200.
3点が一直線になることはない.

B. SMS Typing (とても簡単)
文字列を携帯で入力するとき,何回キーを押せばいいのかを求める問題.
やるだけ.

C. Solve the Broken Maze (謎)
迷路が解ける可能性があるかどうかを判定する問題.
気をつけないといけない入力はこんなのとか.

10
XXXBAAAAAA
XXXBAABBXX
XXXXXXBAXX
AAAAAAABAA
 → Try.

4
XBBX
AABA
XBBX
XXXX
 → Don't Try.

D. Simple Adjacency Maximization (やや簡単)
Greedy.
TopCoderのSRMでやった気がする問題.SRM277 DVI1のMEDIUMと同じ.

E. Special Number (やや簡単)
Ad-hoc.
N進数で,最後の文字を先頭に回したら Y 倍された.
最後の文字は X である.
そのような数字のうち最小のものは何か?
2 <= N <= 256

問題文が不親切すぎる.
先頭が0で始まるのも許されるらしい….

F. Say Goodbye to Tic-Tac-Toe (やや難しい)
ゲーム + Grundy number.
適当にGrundy numberを求めるだけ.

G. Set of Marbles (やや簡単)
Ad-hoc.

H. Smallest Sub-Array (やや簡単)
尺取虫.
長さ n の数列の連続する部分列の中で, 1から k までを全て含むものの中で,もっとも短いものを求める問題.
n <= 1000000, k <= 100.
計算時間量 O( n ).

I. Secret Problemsetters' Union (やや難しい)
ヒープ + optimization.
ヒープやqriority_queueで書くだけだと思ったらそれだとTLE.
Rateが100007までしかないことを利用して,同じRateの問題が複数ある場合はまとめて,qriority_queueの中身を減らすと通った.
それだけで,制限時間12sのところ,約4sで通った.

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

2008年10月19日01時から.

参加上限人数が1500人から1750人に引き上げられて以降,僕の知る限りで初めてレジストした人が1750人に到達した.
これからはまた,直前にレジストする気でいると参加できなかったりする不幸に見舞われるかもしれない.

内容は,MEDIUMが面倒な感じ + サンプルが貧弱なので落としている人が多いみたいだった.
HARDは今回は簡単だったみたい.僕が解けるわけないけどね!

今回のネタはquoteと同じ.Get Backersより.

EASY (250pt)
単純な確率系DP.
サンプルが通れば全く問題ない.

MEDIUM (500pt)
超絶ダイクストラ.実装あるのみ.

帰るときに必ず1人で帰っている人がいたのでチャレンジしようとテストケース作ってる間に
いつの間にかチャレンジフェイズ終わってた….

HARD (1000pt)
グラフ理論,max-flow.
SourceからSilverに流し込んで,多重化したWorkerのノードを経由して,GoldからSinkに流し込む.
エレガントすぎる.格好良い.
こういうのが思いつけないのは,あからさまに応用力が足りてない.

PKU 3263 - Tallest Cow (この記事を編集する[管理者用])

[ Link ]

[ 問題概要 ]
n 匹のcow達が一列に並んでいる.
s 番目のcowが t 番目のcowを見ることができるというのは,
 s 番目のcowは高々 t 番目のcowの身長であって,
 その間にいるcow達は厳密にs 番目のcowの身長より低い.
このような関係が r 個与えられたとき,それぞれのcowの考えうる身長の最大値を出力する問題.
身長は非負整数であり,一番高いcowの場所と,その身長 h も与えられる.
それと,制約条件を全て満たすようなcowの身長は存在することが保証されている.

制約は
 n <= 10000,
 r <= 10000,
 h <= 1000000.

[ 解法 ]
条件を満たす身長の存在が保証されているので,制約の範囲が重なっている場合は,その範囲は片方が片方を包含しているはずである.
これに気づけば,番号の小さいcowが含まれる制約条件から解決していけば良い.
それが複数ある場合,その中で最も大きい区間の制約を先に解決する.

それぞれの制約に対して, 間のcow達を全部なぞると O( n ) かかっちゃって,全体の計算時間量は O( n r ) となる.
実際に計算量が10000*10000になっちゃうテストケースは簡単に作れるんだけども,システムにそんなケースはないらしく,これであっさり通ってしまう.

PKU 2598 - Match Throwing Game (この記事を編集する[管理者用])

[ Link ]

[ 問題概要 ]
テーブルの上に平行な直線が1cm間隔に引いてある.
長さ L cmのマッチを適当にテーブルの上に投げる.
1000回投げたとき,直線とマッチが交わる回数が P となる確率を X ( P ) とする.

0 < L < 10が入力として与えられたとき, X ( P ) が最大となる P を出力せよという問題.

[ 解法 ]
取り敢えず,1回投げたときに直線と交わる確率を頑張って計算する.
後は,その確率 * 1000回の周辺の X ( P ) を2項係数とか使いながら計算する.
たぶん,logとっておかないとoverflow or underflowするような気もする.

1回投げたとき交わる確率の計算はこんな感じ.[ png ]

pdfがアップロードできないことに初めて気づいた…orz
pdfの拡張子をtxtに変えたもの. [ pdf ]

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

超久しぶりに進捗状況メモ.
あんまりキャラレベル上がってないけれど.

前回の予告どおりリック君がメインキャラ昇格.
ミシェーラがメインキャラから降格.

続きを読む

PKU 3690 - Constellations (この記事を編集する[管理者用])

[ Link ]

[ 問題概要 ]
星空の中に含まれる正座の種類を数える問題.
星空は2次元の長方形の形の文字列で与えられ, * が星を表し, . が空白を表す.
正座も2次元の長方形の形の文字列で与えられ,星空の何処かに全く同じパターンが出現するなら,その星空に正座が含まれているとする.

星空のサイズは縦横1000以下.
正座の種類は100以下で,正座のサイズは全て同じで縦横50以下.

[ 解法 ]
正座のサイズが全部同じなので,Rabin-Karpする.
適当な定数 c != d を用いて, A [ x , y ] から A [ x + m , y + n ] からなるHASHを
 ∑ c^{ m - 1 - i } d^{ n - 1 - j } A [ x + i , y + j ]
などとすれば良い.
計算時間量は O( 与えられた星空,正座の面積の和 ).

HASHで文字列検索 (この記事を編集する[管理者用])

過去の記事で時々,hashでごにょごにょするとか言ってると思うのだけども,その話.
長さ n 文字列 A と長さ m の文字列 B が与えられたとき, BA の部分文字列になっているかどうかを判定する問題を考える.

KMP法 ( Wikipedia JP ) とかBM法 ( Wikipedia JP ) で十分だと思うのだけど,使える道具が多いに越したことないのでHASHでやってしまう方法をメモしておく.
一般的に知られている方法なのかどうかわからないのだけど,たぶん何処かにある話で名前もついているのかもしれない.
計算時間量は O( n + m ).

以下出てくるHASHの値はunsigned intやunsigned long longなどで勝手に2^32もしくは2^64などの法で考えているとする.
文字列 B のHASHを適当な定数を c として
 c^{ m - 1 } B [ 0 ] + c^{ m - 2 } B [ 1 ] + ... + c^0 B [ m - 1 ]
とする.
文字列 Ai 文字目から i + m - 1 文字目で作られる部分文字列のHASHが H だとすると,
i + 1 文字目から i + m 文字目で作られる部分文字列のHASHは
 c H + A [ i + m ] - c^m A [ i ]
で計算される.
c^m は何回も使うので最初に計算しておく.
こうやって計算すれば, A の長さ m の部分文字列すべてのHASHを O( n ) で計算することができる.

(2008/10/15 13:00追記)
Rabin-Karp アルゴリズム ( Wikipedia EN ) というらしい.
コメントで教えてもらった.

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

最近なんか時々名前を目にするAho-Corasickを書いてみた.
というか,そもそもKMPすら分かっていなかった.
BFS一発で枝はれることに感動した.
1年以上放置していたUVa 10679 - I Love Strings!!が通ったー,やたっ.
ただ,ジャッジデータが弱いみたいで,本当にバグなく書けてるかは少し不安.

suffix arrayとかでも解けるみたいだけど,そっちはまだ構成法を全く知らない.

ACM ICPC::Regional Warmup 2 (この記事を編集する[管理者用])

2008年10月11日18時から6時間,9問.
[ Link ]

なんというか,個人的には優良問題セットだと思った.
Bはジャッジサーバが落ちてて通してないので,通ってなければ書き換えるかも.

A. Fill the Square (かなり簡単)
greedy.
隣り合うマスは違うアルファベットが入るようにアルファベットを入れる問題.
答えのうち,辞書式で最小のものを返せ.

B. Compressor (かなり難しい)
DP + 経路復元.
文字列を圧縮する問題.
普通にやると計算量が O( n^5 ) なので,適当に枝刈りをしなければいけない.
( n <= 200 )
それとも O( n^4 ) の解法があるのかもしれない.
案の定TLE食らってた.なので意地で通してきた.
実は,ここの文字列一緒にできるけどしないでおこう…なんてことは考えなくて,一部greedyにやってしまえば良いらしい.
ならば, O( n^4 ) でいける.
WA食らってた理由は単なるしょうもないバグだった.

C. Pyramid Number (やや難しい)
サンプルがヒント.
実は,Pyramid Numberでない最大の自然数は80だったか90だったかそのぐらい.
100ぐらいまで全探索して,Pyramid Numberを求めれば良い.

D. Recycling (ちょっとだけ難しい)
DP.
計算量が O( 100^4 ) になるのだけどかまわず突撃すれば通る.

E. InCircle (普通)
Math.
2分探索で通してしまったけど,2分探索できるところまで数式弄ってれば解析的に解けてる….

F. Permutation (普通)
segment tree.
ライブラリ用に新しく書いたsegment treeにバグがあったらしくずっとWAもらってた.
大昔に書いたsegment treeを使ったら通った.
デバグしなきゃ…,なんか新しいsegment treeで何か問題通した気がするんだけどな….

G. H(n) (普通)
O( sqrt(n) )で頑張る問題.
n/i が一定の値となる i の範囲を計算してやって省略しながら計算する.

H. Morning Walk (謎)
大雑把に言えば,頂点が格子点上で,三辺の長さが整数の三角形のうち,
三辺の長さの和が S <= 80000 となるものを列挙せよ,という問題.
たぶん….

I. Switch Grid (やや難しい)
グラフを作ってDFS.
昔これと同じ問題に出くわした気がするのだけど,そのときは全然解けなかったような気がする.

グラフはノード 0, 1, .., N - 1 を各行に対応させて, N, N + 1, ..., N + M - 1 を各列に対応させる.
座標 ( i , j ) にスイッチがあるのならば,ノード iN+ j の間に枝を張る.
このとき, i から j にパスが存在するならば,そのパスに対応するスイッチを動かすことで ij をそれぞれ反転させることができる.

(2008/10/12 9:00 修正 追記)
B問題に関して.

UVa 10872 - Triangles (この記事を編集する[管理者用])

[ Link ]

[ 問題概要 ]
入力: n <= 2^31 - 1
辺の長さの和が n となる三角形は何個あるか?
ただし,辺の長さは整数で,回転,鏡像で一致するものは同じとみなす.

[ 解法 ]
求めるものは,
 #{ a, b, c \in Z : a + b + c = n, a <= b <= c, a + b > c }
なんだけども,このまま考えてたら結構面倒だったので
 Par( n, 3) - #{ a, b, c \in Z : a + b + c = n, a <= b <= c, a + b <= c }
を求める.分割数(Par)に関してはこっちの記事参照.
 #{ a, b, c \in Z : a + b + c = n, a <= b <= c, a + b <= c }
は c の値を固定して適当に和を取ればOK.

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

分割数ちょっと計算したのでメモ.
 Par( n , k ) := n 個のものを k 個に分ける分け方.

例えば,
 Par( 7, 2 ) = 3.
  なぜなら, 7 = 1+6 = 2+5 = 3+4.
 Par( 7, 3 ) = 4.
  なぜなら,7 = 1+1+5 = 1+2+4 = 1+3+3 = 2+2+3.

DPで計算する方法は良く知られている気がする.
今回はそれじゃなくてk が小さいとき計算してみた.

k = 1 )
 Par( n, 1 ) = 1

k = 2 )
 Par( n, 2 ) = floor( n / 2 )

k = 3 )
 Par( 6 m + 1 , 3 ) = 3 m^2 + m
 Par( 6 m + 2 , 3 ) = 3 m^2 + 2 m
 Par( 6 m + 3 , 3 ) = 3 m^2 + 3 m + 1
 Par( 6 m + 4 , 3 ) = 3 m^2 + 4 m + 1
 Par( 6 m + 5 , 3 ) = 3 m^2 + 5 m + 2
 Par( 6 m + 6 , 3 ) = 3 m^2 + 6 m + 3

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

2008年10月09日00時から.
[ overview ] [ summary (Japan) (otinn.com) ]

EASYとMEDIUMは簡単で,HARDに時間をまわすことができる問題セット.
HARDは普通に難しい.
EASYとMEDIUMの速解き競争セットともいう.

今回のネタの元ネタは,
「夢の世界は不変だが、現実の世界ならば自分次第でどこまでも良い状態に出来ると思ったからだ by フェルザー」

EASY (250pt)
binary search.
1次元空間.固定された n 個の質点ある.
新しく質点を置いたとき,重力がつりあって力が働かない場所( n - 1 個)を列挙せよという問題.

MEDIUM (500pt)
greedy + simple math.
n 個ケーキの大きさが与えられる.
合計で c 回まで切ることができるとき,ケーキのサイズの最大値と最小値の差を最小化する問題.
1回のカットでは1個のケーキを2つのケーキにすることができて,それぞれの大きさの比は自由.

あるケーキを m 回切るとしたら, m 等分するのが最適なのがすぐ証明できるので,実際に一番大きなケーキから,何等分するか?という値を1ずつ増やしていくだけ.

HARD (1000pt)
グラフ理論 + DP?
謎.

(200810/09 04:00 EDIT)
-- overview,各問題,otinn.comのsummaryへのLink追加.

(200810/09 04:00 追記)
意外とEASY,MEDIUMを通している人が少なかった.
速解きセットではないみたい.
それにしても,最近強い日本人増えたなぁ…,負けないようにしないと.

THE BMS OF FIGHTERS 2008 - Resurrection - (この記事を編集する[管理者用])

なんか,いつの間にかTHE BMS OF FIGHTERS 2008やってたらしい.
[ Link ]

ちまちま落として全部解凍したら軽く6GB超えやがった….
でも,楽しー.

闘神都市3 ベンチマーク (この記事を編集する[管理者用])

闘神都市3のベンチマーク.
[ Link ]

高画質で23.0 fps,通常画質で143.9 fpsだった.
なんとかまだプレイできそうね.
どっちみちそろそろ新しいPC欲しいような気もするけど.

それより,ベンチマークの時に流れる音楽聞いたところ今回はShadeさんっぽい.
ハルカの時みたいに一部だけShadeさんとか言うことも考えられるけれども….
( ちなみに,AliveZは知らない )
曲調的には,過去の闘神都市シリーズの曲調を踏襲するっぽいのかなー,1曲しか聴いてないわけだけど.

Rance 5DがShadeさん,Rance 6がDragon Attackさん,Rance 7がShadeさんで,
さらに,今回は闘神なので,てっきりDragon Attackさんだと思ってた.

POJ Founder Monthly Contest – 2008.10.05 (この記事を編集する[管理者用])

2008年10月05日13時から5時間,8問.
[ Link ]

UVa人間なのでPKUのコンテストに出るのは久しぶり.
しかし,POJ Monthlyはいつもながら難しすぎる….
結局,実装問題しか通してない…,アルゴリズムってナンデスカ?

Problem A: miniSQL (普通)
超絶実装問題.
書くだけ.
今回の最易問題その1.

Problem B: Missile Defence System (謎)
数列が与えられて,1回の操作で増加部分列または減少部分列を取り除くことができる.
すべて取り除くには何回の操作が必要ですか?最小値を求めてください.
数列のサイズは50以下.

サイズが20~30ぐらいなら全探索しても大丈夫なんだけど,50だと無理だった.

Problem C: Rubik's Cube: 0-1 Version (謎)
普通のルービックキューブを1面だけ揃える方法を書き出してくださいという問題.
最小手を求めなくても良いので,Ad-hocにやればたぶん良い.
でも,誰1人として通してないので怖くて書けない.

Problem D: Chessman (普通)
search,DFS or BFS.
今回の最易問題その2.
 場所が0, 4, 8, 12, ... にある * の数と,
 場所が1, 5, 9, 13, ... にある * の数と,
 場所が2, 6, 10, 14, ... にある * の数と,
 場所が3, 7, 11, 15, ... にある * の数
を状態としてDFSするだけ.

Problem E: Intuition of Escape (やや難しい)
幾何,実装問題.
原点からある頂点までの距離を d ,その頂点のある角度を t とすると,進む方向は
 t ± arcsin( r / d )
だけチェックすればよい.
(つまり,その点をぎりぎりかするように進む)

n = 0の場合を考慮してなくてWA2桁食らった….

Problem F: Mover (謎)
サイズ 100 * 100 以下のチェス盤の上の駒を上下左右に動かせる.
全部が隣接した状態になるには最低何回動かせば良いか?

Problem G: Reverse (謎)
1回の処理で,配列から連続した部分を一部取り出して,順番を変えずにそのまま別の場所に突っ込むことができる.
 { 1, 2, 3, ..., n} → { n, ... , 3, 2, 1 }
とするための最小手を求めよ.(回数だけじゃなくて具体的に与えろ)
n <= 100.

今回の最易問題その3.でも解けない.

Problem H: System Test (謎)
TopCoderの準決勝戦.
参加者数 n <= 40,問題数 m <= 40.
一気にFinalへ勝ち進む人数 c1, Wildcard Roundに進む人数 c2.
今,チャレンジフェイズが終了して,システムテスト待ち.
皆の各問題の点数と,チャレンジの点数が与えられたとき,
 Finalへ勝ち進む人,Wildcard Roundに進む人
として考えられるのは何通りあるか?
ただし,点数が全く同じ場合,SEEDの小さいほう(RATEの高いほう)が順位が上とする.

Waterloo ACM Programming Contest Fall 2 (この記事を編集する[管理者用])

2008年10月05日02時から3時間30分,5問.
もともと3時間の予定だったけど,最初問題が見れなくて30分延長したらしい.
[ Link ]

先週行われたWaterloo ACM Programming Contest Fall 1と比べてとても簡単になったなぁという印象.
実装の重い問題がないし,アルゴリズム的にも難しい問題もなくて,1時間で5問解けちゃった.
ってことで予約投稿.

Problem A: Cranes (だいぶ簡単)
brute-force.2^n.

Problem B: WiFi (やや簡単)
binary search.

Problem C: Exact Change (簡単)
DP.コインを使う枚数を最小化しましょう系.

Problem D: Dominos 2 (かなり簡単)
DFSするだけ.

Problem E: Logo 2 (やや簡単)
simulation.精度が意外と厳しい.
移動する距離が ? になっている場合は,そのコマンドを無視して最終的に原点からのずれを整数に丸めて出力する.
角度が ? になっている場合は, 0 ~ 359まで全部シミュレーション試して,最終的に一番原点に近かったものを出力する.

キャッスルファンタジア アリハト戦記 (この記事を編集する[管理者用])

キャッスルファンタジアシリーズは初代はやったことなくて,聖魔大戦(2作目)がすっごい好き.
エレンシア戦記(3作目)も嫌いじゃないけど聖魔大戦には及ばない.
で,アリハト戦記は聖魔大戦の数年前のお話で外伝的なもの.
以前からやりたいやりたいと思っててようやくやってみた.

やっぱり凄い楽しかった.こういうの好きだなぁ.
ヒューイ君すでに大活躍じゃないですか…,昔は駄目駄目なイメージなのかと思ってた.
デュシス君が影薄かったけど,皆良いキャラしてるよなぁ…,ガヤックとか.
外伝だとは思うのだけど,そこまで短くはなかった.
戦闘や選択肢がないので3~4時間ぐらいで終わった気がするけども.

キャッスルファンタジアの新作 白銀の騎士(4作目)は現在製作中?
3作目が2000年発売なので8~9年ぶりになるのかな.
期待せずに期待してます.

PKU 3695 - Rectangles (この記事を編集する[管理者用])

[問題概要]
0 <= x , y <= 1000 の範囲に長方形が n 個与えられる.頂点は格子点上.
便宜上,長方形に 1 から n まで番号をつける.
m 個のクエリが与えられ,クエリごとに,{ 1, ... , n } のサブセットが与えられて,
サブセットに含まれる長方形が占める面積を書き出す問題.
n <= 20, m <= 100000.

[解答]
k を2進数表記したとき,1が現れる桁の集合を Kとする.
k = 13 =1101(2) ならば,K = {1, 3, 4} .
まず,
 area[ k ] := ちょうど K をインデックスにもつ長方形のみで占められている面積
を計算する.包除原理でも良いし,1000*1000の領域を塗りつぶしていっても良い.
後は,クエリごとに2進数表記に直して,それを q とすると, k & q != 0 となる k に対して,
 area[ k ]
を足すだけ.
ナイーブに足すと,k は 0 から 2^n - 1 まで動くので計算時間 O ( m * 2^n ) となってTLEを食らう.
だが,area[ k ]が 0 じゃない場合はかなり少ないので,それだけ覚えておいて足せばOK.
かなり少ないといっても,うまく見積もれないけども,2次元なので,多くても O( n^2 ) しかないのは確か.
なので,計算時間は粗く見積もっても O ( m * n^2 + 2^n ) 程度.

PKU 3697 - USTC campus network (この記事を編集する[管理者用])

昨日PKUで行われた2008 Asia Hefei Regional Contest Online by USTCの問題.
ちょっとPCがトラブっていて出れなかったので,のんびりまったり解こう….

で,そのコンテストでは最易問っぽい3697.
通れない枝だけ与えるとか,発想が面白いと思った.
DFSまたはBFSするだけなのに,ちゃんとデータ構造考えないと駄目なあたりが面白かった.

[問題概要]
ノード数 n の完全グラフがあって, m 個の枝のリストが与えられる.
与えられた枝を通らずに,番号 0 のノードから到達できるノード数を答えよ.
n <= 10000, m <= 1000000.

[解法]
基本的にはDFS or BFSするだけ.
計算時間 O( n + m ) で解ける.
まず,通れない枝をhashにぶち込んで,ノード i からノード j へ直接行けるかどうかを O(1) で計算できるようにしておく.
DFSするとき,まだ,辿り着けていないノードをスタック等に突っ込んでおいて,まだ辿り着いていないノードのみを調べる.

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

2008年10月02日20時から.

久しぶりに簡単な問題セット.
頑張れば3問とも解けるかもしれない.
まぁ,未だに不等号で条件判定するとき,等号を忘れてシステム落ちちゃう僕には夢のような話.
いつもながらSRMの後は欝にしかならない.

いつもプログラムの先頭にネタ書いてますが,今回はUCRに引っかかりそうで消してしまった….
ちなみに今日のネタは「行く道一つの、唯一つ これが我らの生きる道 by 三島 塔子/燐子」でした.
まぁ,長かったな….

EASY (250pt)
シミュレーション,実装問題.
STL使いこなせますか?的な問題.

MEDIUM (500pt)
典型的なDP.
2次元配列でドカンとメモリとっちゃうとMLE食らうので1次元で頑張るだけ.

HARD (1000pt)
ad-hoc + DP + simulation.
x 円支払うのに必要な硬貨の枚数を最小化するタイプのDP.
後は,simulation + もう1個DP.

XXII Colombian Programming Contest (この記事を編集する[管理者用])

2008年10月01日17時から5時間,9問.
http://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_onlinejudge&Itemid=11&page=show_contest&contest=211

今回はなんとか全部解けたので,予約投稿で終了時間に投稿されるようにしておく.

A. Angry Programmer (普通)
グラフ理論,max-flow.
最小カットを求める問題.
ノードを壊すのはノードを2つに分裂させて,その間に枝を1本張ればよい.

B. Bender B. Rodríguez Problem (やや簡単)
Ad-hoc.
回転させて回転させて…とやるだけ.

C. Life on Mars? (やや簡単)
Ad-hoc.

D. Touring Robot (やや簡単)
シミュレーション + 2辺のなす角度.

E. Erdös Unit Fractions (普通)
brute force,search.
xとyを全探索しても十分間に合った.

F. Frieze Patterns (普通)
Ad-hoc.
周期的になると思ったので,1周期分計算すればよかった.

G. GATTACA (普通)
文字列.
ハッシュを使ってごにょごにょ.
rotate hash?

H. 9 Puzzle (普通)
search,BFS.
初期状態から1回BFSしておけば,全ての入力に対して一発で答えが出せる.

I. Batman (普通)
典型的DP + 文字列操作.

Appendix

Recent Articles

ブログ内検索

Ads


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