Entries

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

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

Facebook Hacker Cup 2011 Round 1A [無効試合] 3問目 - First or Last (この記事を編集する[管理者用])

Source

Facebook Hacker Cup 2011 Round 1A [無効試合] 3問目
Facebook Hacker Cup 2011 Round 1A [無効試合]の参加記録

問題概要

R人でレースを行う.最初自分は最下位.
T箇所だけ,コーナーがあって,各場所について
 今の順位を維持するなら 1/p[k] の確率でクラッシュする
 1人だけ抜くなら 1/q[k] の確率でクラッシュする
という確率が与えられる.
クラッシュせずにR-1人抜く確率の最大値を有理数で厳密に求める問題.
Tは50以下,p[k],q[k]は500以下.

解法

多倍長の有理数が必要な問題.
greedyにp[k]/q[k]の値が小さい方から抜くことにする.
以下のコードは無駄にDPしているコード.

C言語のスパゲッティなコード (not verified)

続きを読む

Facebook Hacker Cup 2011 Round 1A [無効試合] 2問目 - Power Overwhelming (この記事を編集する[管理者用])

Source

Facebook Hacker Cup 2011 Round 1A [無効試合] 2問目 (問題削除済み)
Facebook Hacker Cup 2011 Round 1A [無効試合]の参加記録

問題概要

整数A, B (1以上100以下) とC (A+B以上10^12以下) が与えられる.
正整数x, yをxA + yBがC以下という制約のもとでxyを最大化するものとする.
ただし,答えが複数あるならxを最大化する.
xを求める問題.

解法

xとyが実数全体なら二次方程式の最大値なので解析的に求まる.
A, Bが小さいので,その周辺を調べれば良い.
xyの最大値が64bit整数に収まらないので注意.(多倍長が必要)
以下のコードでは,解析的にやらず,整数のまま三分探索しているのでかなり怪しい.

C言語のスパゲッティなコード (not verified)

続きを読む

Facebook Hacker Cup 2011 Round 1A [無効試合] 1問目 - After the Dance Battle (この記事を編集する[管理者用])

Source

Facebook Hacker Cup 2011 Round 1A [無効試合] 1問目
Facebook Hacker Cup 2011 Round 1A [無効試合]の参加記録

問題概要

100*100以下のグリッドが与えられる.
スタート地点,ゴール地点が1箇所ずつ与えられるので,スタートからゴールまでのステップ数の最小値を求める問題.
グリッドは壁(入れない)か空白(0)か色がぬられている(1--9).
1ステップでできる行動は上下左右に移動するか,同じ色の他のセルにワープすることができる.

解法

BFSするだけ.

C言語のスパゲッティなコード (not verified)

続きを読む

Facebook Hacker Cup 2011 Round 1A [無効試合] (参加記録) (この記事を編集する[管理者用])

2011年01月16日00時から3時間(の予定だった),3問.
1回戦は3ラウンドのうち,それぞれ上位1000人が通過.
[Problems] [Score board]

はじめに・・・

サブミットしようとしてもサーバーが応答せずサブミットできない現象が起きたのと,
2問目のサンプルが間違えている,3問目のサンプルが入力の制約を満たしていない,などという問題があり,何故か早めに終了.
現在結果も明らかにならず,2問目は削除されている様子.
Round 1は1週間以上は延期するとのこと.

1問目 - After the Dance Battle

100*100以下のグリッドが与えられる.
スタート地点,ゴール地点が1箇所ずつ与えられるので,スタートからゴールまでのステップ数の最小値を求める問題.
グリッドは壁(入れない)か空白(0)か色がぬられている(1--9).
1ステップでできる行動は上下左右に移動するか,同じ色の他のセルにワープすることができる.

問題文が読みにくい.
入力から読む.入力と出力だけ読めば意味がわかるじゃん….
単にBFSするだけだ.
最悪ケースは,全部のマスが同じ色の場合だけど,10000^2程度なのでなんとかなるだろう.
書く.
書いた.サンプル通ったのでサブミット.

2問目 - Power Overwhelming

整数A, B (1以上100以下) とC (A+B以上10^12以下) が与えられる.
正整数x, yをxA + yBがC以下という制約のもとでxyを最大化するものとする.
ただし,答えが複数あるならxを最大化する.
xを求める問題.

三分探索やるだけでいいよね.
…違う!
x,yは整数なんだから,関数はギザギザしてるはず….
まぁ,適当にやればよさそうだが….
てか,待てよ!
Cが10^12ってことは…,xyの最大値が64bitで収まらないんだけど….
…,先に3問目に行こう.
3問目提出して戻ってきた.
twitterなどでは提出できないという噂がチラホラ見える.普通にできたけどなぁ.
多倍長+三分探索して,後はその周辺を調べたらいいんじゃないの?
ってことで書く.
合わない.
問題文ではyの最大値なんだけど,xの最大値を出力してみたらサンプルっぽいのがでてきた.
でも,結構違う….
てか,このサンプル間違ってないか?
なんか,自分の答えのほうがxyでかいんだが….
もういいや,サンプル無視してサブミットしてみよう.
インプットダウンロードして実行.
サブミット…できない.サブミットボタン押しても反応なし.
chrome, firefox, IEで試したけど駄目だった.
そうこうしてる間に6分間過ぎた.
しばらくしたら,6分過ぎてもサブミットしたら受け付けてあげるよ,とのアナウンスが.
ってことで,サブミット…,してもしてもできない.
10分ぐらい粘ったらサブミットできた.
残り1時間残して全部提出したので寝る.

3問目 - First or Last

R人でレースを行う.最初自分は最下位.
T箇所だけ,コーナーがあって,各場所について
 今の順位を維持するなら 1/p[k] の確率でクラッシュする
 1人だけ抜くなら 1/q[k] の確率でクラッシュする
という確率が与えられる.
クラッシュせずにR-1人抜く確率の最大値を有理数で厳密に求める問題.
Tは50以下,p[k],q[k]は500以下.

…多倍長から逃げてきたら,多倍長有理数ときたよ….
問題自体はDPするだけ.(実はgreedyで良いのに気づかない)
多倍長有理数のライブラリを貼りつけて書くか.
書いた.
インプットダウンロードして実行.
….時間かかるなぁ.
1分ぐらいかかった.怖い.
サブミット.

Beta Round #51 D問題 - Beautiful numbers (この記事を編集する[管理者用])

Source

Codeforces Beta Round #51 D問題
Problem description
Beta Round #51の自分の参加記録

問題概要

A以上B以下 (Bは9*10^18以下) の整数で,
 その整数がk (kは1以上9以下) の数字が含まれていたら整数はkの倍数であるという性質を満たす
ものの数を求める問題.

解法

DP+包除原理.
各桁を使うかどうかで場合分けして求める.
それは,使える桁 (使わなくても良い) を指定してDPして,包除原理で求める.
単純にやるとTLEするが,0とか1はそもそも使っても使わなくてもLCMに関係しない良いので使わない場合は考えない.
同様に,例えば6を使うときは,2とか3とかは使っても使わなくても構わないので使わない場合は考えない,とすれば通る.
他にも,LCM(1, 2, ..., 9) = 2520が10の倍数であることと,DPの更新式を見比べて,最後以外mod 252で保存しておけば良いなどを利用すると更に早くなる.(以下のコードではやってない)

C言語のスパゲッティなコード

続きを読む

Beta Round #51 C問題 - Pie or die (この記事を編集する[管理者用])

Source

Codeforces Beta Round #51 C問題
Problem description
Beta Round #51の自分の参加記録

問題概要

2人でゲームを行う.
n*mのグリッド上 (100*100以下) にK個 (100以下) のパイが置かれている.
先手は1個でもパイを盤面の外に出して手に入れたら勝ち.後手は先手がパイを手に入れれないと勝ち.
各ターン,先手は1つのパイを選んで上下左右に移動させることができる.
後手は,盤面の縁を1つ選んで,壁を作って,そこをパイを通れなくすることができる.
先手必勝か,後手必勝か,を判定する問題.
パイは同じセルに複数存在することができる.

解法

先手は,縁に一番近いパイを縁の周りをぐるぐる回していくのが最適.
後手は,一番端は1箇所で2箇所塞がないといけないので,4ターンの余裕があれば,全部塞げる.

C言語のスパゲッティなコード

続きを読む

Beta Round #51 B問題 - Smallest number (この記事を編集する[管理者用])

Source

Codeforces Beta Round #51 B問題
Problem description
Beta Round #51の自分の参加記録

問題概要

0以上1000以下の整数が4つ与えられる.また,+か*からなる3文字の文字列が与えられる.
kターン目 (k = 1, 2, 3) は整数を2つ選び,それを文字列のk文字目が+なら2つの整数の和に,*なら2つの整数の積に変える.
最終的に得られる数字の最小値を求める問題.

解法

全探索する.

C言語のスパゲッティなコード

続きを読む

Beta Round #51 A問題 - Flea travel (この記事を編集する[管理者用])

Source

Codeforces Beta Round #51 A問題
Problem description
Beta Round #51の自分の参加記録

問題概要

n個 (1000以下) のセルが円周上に並んでいる.
あるセルから,1個右に移動,次はそこから2個右に移動,次はそこから3個右に移動,…
と無限に移動したとき,最終的に全てのセルに到達するかどうかを調べる問題.

解法

適当にループを回してシミュレーションすれば良い.
2n回移動すると,初期値に戻り,ジャンプの幅もmod nで最初に等しくなるので2n回ループを回せば十分.
解析的に考えると,nが2のべき乗であるときのみYESが答えになる.
nは10^9以下のバージョンはPKU 3372 (http://poj.org/problem?id=3372) にある.
以下のコードは,場所とジャンプ幅を状態として同じ状態になるまでループを回すプログラム.

C言語のスパゲッティなコード

続きを読む

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

2011年01月14日17時から2時間,5問.codeforcesルール
[ LINK ]

A. Flea travel

n個 (1000以下) のセルが円周上に並んでいる.
あるセルから,1個右に移動,次はそこから2個右に移動,次はそこから3個右に移動,…
と無限に移動したとき,最終的に全てのセルに到達するかどうかを調べる問題.

えっとー,状態数はn^2だからループを回して同じ状態に来たら終了.
状態は,今いる場所と,ジャンプ幅 mod n.
書いた.4以下で手計算と合うこと,1000近くの値でも一瞬で終わることを確認してサブミット.
pretest passed.

B. Smallest number

0以上1000以下の整数が4つ与えられる.また,+か*からなる3文字の文字列が与えられる.
kターン目 (k = 1, 2, 3) は整数を2つ選び,それを文字列のk文字目が+なら2つの整数の和に,*なら2つの整数の積に変える.
最終的に得られる数字の最小値を求める問題.

4つ固定なので全パターン試せば良いよね.
即書く.lldをI64dに直すのを忘れない.サブミット.pretest passed.

C. Pie or die

2人でゲームを行う.
n*mのグリッド上 (100*100以下) にK個 (100以下) のパイが置かれている.
先手は1個でもパイを盤面の外に出して手に入れたら勝ち.後手は先手がパイを手に入れれないと勝ち.
各ターン,先手は1つのパイを選んで上下左右に移動させることができる.
後手は,盤面の縁を1つ選んで,壁を作って,そこをパイを通れなくすることができる.
先手必勝か,後手必勝か,を判定する問題.
パイは同じセルに複数存在することができる.

時間が経つと先手は不利になるだけなので,1つのパイにのみ着目してそれを外に出せるかどうかを判定すれば良い…はず.
で,まぁ,一番近い縁に向かって動かせば良いよね.
って,最初から1ターンで勝てないなら先手は勝てないじゃん.
後は,後手は先手の移動先が縁のそばだったらそれを塞ぐだけでいい.
submit.WA.あれ.
あー,縁にたどり着いた後,左右に移動したら,その先の壁の向こうから出れるのか.
でも,縁から距離3だと,両端を塞げてしまうので,距離2以下なら勝ち.
submit.WA.むー.
わからないのでD問題を考える.
D問題をサブミットした後,コンテスト残り時間2分で戻ってくる.
うーん.
適当に,上下の壁,左右の壁から両方から距離3なら先手が勝てるのでは?
とか意味不明なコードをサブミットしたらpretest passed.
絶対こんなので正しいとは思えないのだが,残り時間がなくて何も検証できなかった.

D. Beautiful numbers

A以上B以下 (Bは9*10^18以下) の整数で,
 その整数がk (kは1以上9以下) の数字が含まれていたら整数はkの倍数であるという性質を満たす
ものの数を求める問題.

はて….
DP+包除原理な気がする.
各桁を使うかどうかで場合分けする.
それだと,使うと決めた桁の一部分しか使わない場合もあるかもしれないから包除原理.
後は,DPでmod 2520で幾つになるものが幾つあるかを求めればOK.
….
いや,これ重いぞ.
制限時間は…4秒あるし,テストケースも10個しかないらしい.
ならいけるのかな?
書いてみよう.
….
書いたけど,時間かかりすぎる+答えが全部マイナスが返ってくる.
あれぇ….
包除原理間違えてる.
まだ答えがマイナス.
あ,ループの終点まで1個足りてなかった.
答えはそれっぽいのが帰ってくるようになった.
初めてCUSTOM TEST機能使って,codeforcesでの実行時間を測ってみる.
15秒以上….ダメじゃん.
うーん….
小手先の高速化をする.
テストケース4個でローカルで8秒ぐらい.CUSTOM TESTでも8秒ぐらい.
ほう,codeforcesはローカルと実行時間だいたい同じと思えば良いのか.
うーん….
再度小手先の高速化をする.
うーん….
0~9まで全部使うかどうか2^10試す必要はないじゃないか!
0とか1とか使っても使わなくてもLCMに影響しないので2~9まで2^8通りやれば良い.
….
これで3秒ぐらいで終わるようになった.
が…,なんかさっきと答え変わったぞw
えー….
でも小さいところを出してみると合ってるように見える.
もう残り時間も少ないし,試しにサブミット.WA.
うーん.
包除原理でループで回す範囲間違えてた….
修正.サブミット,pretest passed.

E. Very simple problem

凸なN角形 (100000以下) が与えられる.
また,その対角線上にないt個 (20以下) の点が与えられる.
各点に対して,その点を含むような三角形の数をそれぞれ求める問題.三角形の頂点はN角形の頂点から3つ選んでこなければいけない.

考えてない.

Hacks

Bで演算子の順番もnext_permutationで回してるように見えたのを落とそうとして失敗した.見間違えでした.

Results

CはWA,DはTLEで落ちる.

SRM394 DIV2 HARD - ProperDivisors (この記事を編集する[管理者用])

Source

TopCoder SRM394 DIV2 HARD (1000pt)
Problem Statement

問題概要

d(m)でmのcoolな約数の数を表す.
coolな約数xとは,xは1以上m未満で,xはmを割り切り,x^nはmを割り切れないもの.
 d(a)+d(a+1)+…d(a+b)
を求める問題.
aは10^6以下,bは10^7以下,nは2以上10以下.

解法

Σの順番を入れ替える.結局答えはだいたい
 a~a+bまでの中の2の倍数の数(2を除く) + a~a+bまでの中の3の倍数の数(3を除く) + …
 - a~a+bまでの中の2^nの倍数の数 - a~a+bまでの中の3^nの倍数の数 + …
みたいな感じになる.

C++によるスパゲッティなソースコード

続きを読む

SRM394 DIV2 EASY - MountainWalk (この記事を編集する[管理者用])

Source

TopCoder SRM394 DIV2 EASY (250pt)
Problem Statement

問題概要

50*50以下のグリッドの標高が与えられる.
最初左上にいて,下,左,上,右の4方向セルのうち,移動できる最初のセルに移動する.
移動できるセルは,まだ行ったことがなくて,標高差がheightDifference以下のセル.
最終的に何セルに辿りつけるかを求める問題.

解法

やるだけ.

C++によるスパゲッティなソースコード

続きを読む

SRM394 DIV1 EASY/DIV2 MEDIUM - RoughStrings (この記事を編集する[管理者用])

Source

TopCoder SRM394 DIV1 EASY (250pt)
TopCoder SRM394 DIV2 MEDIUM (500pt)
Problem Statement

問題概要

アルファベット小文字のみからなる長さK (50以下) の文字列が与えられる.
n文字 (K-1以下) 以下だけ消して,ラフネスを最小化したい.最小値を求める問題.
ラフネスとは,文字列に最も多く現れる文字の文字数 - 文字列に最も少なく(ただし1文字以上)現れる文字の文字数.

解法

最も多い文字の文字数MAXと,最も少ない文字の文字数MINを決め付ける.
それが可能かどうかは,各文字に対して,MAXより多ければMAXになるまで消す,MINより小さければ全てなくなるまで消す,として,n回の削除で実行可能かどうかを判定する.
使う文字をgreedyに全探索して,残りは多い文字からgreedyに消すなどという方法でも可能.

C++によるスパゲッティなソースコード

続きを読む

SRM493 DIV1 MEDIUM - AmoebaCode (この記事を編集する[管理者用])

Source

TopCoder SRM493 DIV1 MEDIUM (450pt)
Problem Statement
SRM493 DIV1 自分の参加記録

問題概要

LEN文字 (K+1以上50以下) の文字列が与えられる.
各文字は,未確定(0)か,数字の1~Kのどれか.(Kは7以下)
未確定の文字を1~Kのどれかに置き換えて,最も近くにある同じ文字間の距離を最大化したい.
最大値を求める問題.

解法

答えの最大値は高々K.
なので,前使った文字K-1文字と,今の場所を状態としてDPすれば良い.
以下コードは,違う方針で,各文字について最後に出てきた場所を状態としてDPするコード.ただしK文字より前だとK文字前と同じとみなす.

C++によるスパゲッティなソースコード

続きを読む

SRM493 DIV1 EASY/DIV2 MEDIUM - StonesGame (この記事を編集する[管理者用])

Source

TopCoder SRM493 DIV1 EASY (300pt)
TopCoder SRM493 DIV2 MEDIUM (600pt)
Problem Statement
SRM493 DIV1 自分の参加記録

問題概要

N個 (10^6以下) の石が一直線に並んでいる.
左からM番目の石のみ白くて,他は黒い.
2人でゲームをする.順番にターンが回ってくる.
毎ターン,白い石を含むように連続するK個の石を選び,順番をひっくり返し,白い石を左からL番目に移動した人の勝ち.
先手必勝か,後手必勝か,永遠に長引かせられるか,を判定する問題.

解法

全ての手は可逆なので,後手は順番が回ってきて勝てないなら,先手の手を打ち消すことで引き分けに持ち込める.
よって,
 1手でMからLに移動できるなら先手の勝ち
 先手がどう動かそうが,次にLに移動可能なら後手の勝ち
 そうでなければ引き分け

C++によるスパゲッティなソースコード

続きを読む

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

2011年01月13日11時02分から.

Assignment

300-450-1000の変則セット.
チャレンジの神様などと一緒の部屋.

EASY

N個 (10^6以下) の石が一直線に並んでいる.
左からM番目の石のみ白くて,他は黒い.
2人でゲームをする.順番にターンが回ってくる.
毎ターン,白い石を含むように連続するK個の石を選び,順番をひっくり返し,白い石を左からL番目に移動した人の勝ち.
先手必勝か,後手必勝か,永遠に長引かせられるか,を判定する問題.

状態数が100万しかないし普通にDPすれば良いのでは!
…,いや,各ノードからの枝数もO(100万)ぐらいあるし,無理っぽ.
そもそも引き分けにできるとかそういうのでループするし….
!!
これ,後手は絶対ループに持ち込める.すべての手は可逆だから.
ってことで,1手で勝てるなら先手必勝,そうでなければ引き分け.
いや,なんか,サンプルに後手必勝とかあるんですけど….
ああ,そうか,どんな先手の手に対しても.その後,後手が1手で勝てちゃうことがあるのか.
ってか,このサンプル弱くないか?
基本的に最初にある白い石の場所が端ばっかり.先手の手が1手に限られてる場合が殆ど.
まぁ,書く.
….
if文の条件が面倒…,というか間違えそうで怖い.等号がいるか要らないかとか慎重に検証しながら書く.
書けた.サンプル通った.サブミット.慎重になったせいか遅い….でも間違えるよりマシ.
450は瞬殺できる可能性が高いし,さらに1文ずつ見直してから次の問題へ.

MEDIUM

LEN文字 (K+1以上50以下) の文字列が与えられる.
各文字は,未確定(0)か,数字の1~Kのどれか.(Kは7以下)
未確定の文字を1~Kのどれかに置き換えて,最も近くにある同じ文字間の距離を最大化したい.
最大値を求める問題.

とりあえず制約を読む.
Kが小さい.K!の全探索+アルファとかか何かか?
問題を読む.
うーん…,何か違う….
Greedyか何かでできるんだろうか….
わからない.
DPするとすれば….
各文字が前出てきた場所を覚えておけば状態数50 * 50^7でできる…,厳しい.
えー.
あ,答えの最大値はKだよね.
だから,K以上前に現れたものはKぐらい前に現れたものと同じと思っても問題ない.
状態数 LEN * K^K か….これいくら?
 50 * 7^7 = 41,177,150.
厳しい?いやTopCoderさんならやってくれる.
計算量は
 50 * 7^7 * 7 * 7 = 2,017,680,350
…,無理じゃん.
いや,頑張れば7は1個消せて
 50 * 7^7 * 7 = 288,240,050
かな.
えーーーー.
でも,めんどうだし,450でこんな難しいはずはない….
サマリーを見ると…,自分は300で遅れてる方なのに,みんな提出してない.
やっぱりこれ難しいんだ.
そうと決まったら書く!
とりあえず,書きやすい50 * 7^7 * 7 * 7 = 2,017,680,350で書く.
K=6なら余裕で間に合うけど,K=7で明らかに死亡.
1個ループを削って,50 * 7^7 * 7 = 288,240,050に直す.
K=7で,Arenaで6秒ぐらいかかる様子….えええええええ.
どうしよう….3倍の最適化は厳しい….
….
試行錯誤の末,単に,たどり着けてない状態は処理しないようにしたら0.4秒程度で終わるようになった.
え.なんか怪しいけど大丈夫かな….
そうか,前にこの数字が出てきた場所,ってのは同じ場所にならないから状態数はK^Kじゃなくて全然もっと少ないはず.(K!+アルファぐらい)
サブミット.
(システムテストで最悪ケースで0.5~0.6秒程度でした)

HARD

100*100以下のグリッドが与えられる.使えるマスと使えないマスが指定される.
使えるマスのみからなる,空でなく,連結で凸な一連のマスを選ぶ方法は何通りあるかを mod 1000000007 で求める問題.
凸とは,2つの同じ行または列のセルが含まれてるなら,その間のセルも含まれてなければならない,という条件.

これもDPな気がする.
前の行に使ったセルの左端,右端はとりあえず状態に含まれる.
あと,左端は単調減少→単調増加,右端は逆,とならなければ行けないので,極地を超えたかどうかのフラグを用意する.
状態数はO(4*50^3)で,状態の更新に50^2かかる….
微妙だけど,頑張れば通るような気がしないでもない感じ.
違った.サイズの最大は100ではないか!
状態数はO(4*100^3)で,状態の更新に100^2かかる…から…,O(100^5)….
無理だ.
うーん,取り敢えず書きながら考えよう….
って思ってたら,書くだけでも時間なかった.

Challenge

450でTLE狙い.か,250で条件ミス狙いか.
250を見る.
なんか,条件がいろいろ怪しい人が1人いたので落とす.
後は見てるだけで終了.

System tests

結構自信なかったけど300も450も通った.一安心.

January 2011 Challenge 6問目 - Splitting Giant Subs (チャレンジ形式) (この記事を編集する[管理者用])

Source

codechef January 2011 Challenge 6問目 (チャレンジ形式)
Problem Statement
January 2011 Challengeの参加記録

問題概要

要素数N (1000以下) の整数列が与えられる.
各要素は1以上500以下で,同じ数字はちょうど偶数個だけ含まれている.
途中で分断して,奇数個目の塊をAに,偶数個目の塊をBに分けたとき,AとBに含まれる各数字の数を等しくしたい.
そのような分断の仕方を1つ求める問題.
スコアは,分断の数が小さいほうが良いスコア.

解法

各数字をAに分けるかBに分けるか決めて,隣接するのが違う方に分けなければいけない場所で分断すれば良い.
焼きなました.

C言語のスパゲッティなコード (スコア1743)

続きを読む

January 2011 Challenge 5問目 - Restaurant Expansion (この記事を編集する[管理者用])

Source

codechef January 2011 Challenge 5問目
Problem Statement
January 2011 Challengeの参加記録

問題概要

Nノード (30以下) の木が与えられる.
最初はノード1にシェフがC人 (30以下) いる.
各ノードに店を建てた場合の収益 (-1000以上1000以下) が与えられる.
各日に出来る行動は以下のとおり
 ・なにもしない
 ・シェフのいる場所,かつまだ店の建ててないノードに店を建てる
 ・店の建ててないノードのシェフを隣接するあるノードに移動させる.一度に何人でも移動できるが,移動先は同じ場所
D日間 (30以下) で収益を最大化する方法と最大値を求める問題.

解法

木の上でDPする.
今どこのノードにいて,シェフが何人いて,このサブツリーで費やせる日数を状態とする.
経路復元までしないといけないので実装は多少面倒.

C言語のスパゲッティなコード

続きを読む

January 2011 Challenge 4問目 - Flu Shot Lineup (この記事を編集する[管理者用])

Source

codechef January 2011 Challenge 4問目
Problem Statement
January 2011 Challengeの参加記録

問題概要

半直線上 (x≧0) にN人 (10000以下) の人がいる.
それぞれの人がD以下だけ動いて,最も近い2人の距離をT (1000000以下) 以上にできる.
N人の初期位置とTが与えられたとき,Dの最小値を求める問題.

解法

取り敢えず,答えに対して2分探索.
Dだけ動いて,最も近い2人の距離をT以上にできるかどうかは,左の人から,できるだけ左で,左の人とT以下になるまで近づかないようにできるだけ左に移動するgreedyで確かめられる.

C言語のスパゲッティなコード

続きを読む

January 2011 Challenge 3問目 - Count Relations (この記事を編集する[管理者用])

Source

codechef January 2011 Challenge 3問目
Problem Statement
January 2011 Challengeの参加記録

問題概要

1~N (10^18以下) の整数からなる集合{1, 2, ..., N}の部分集合を2つを
 1. 2つの部分集合が包含関係でなく,部分集合の共通部分が空のもの
 2. 2つの部分集合が包含関係でなく,部分集合の共通部分が空でないもの
を満たすように取ってくる方法はそれぞれ何通りあるかを mod 100000007 で求める問題.

解法

各数字を,どれにも入れない,1つ目の部分集合に入れる,2つ目の部分集合に入れる,両方の部分集合に入れる,と考える.
そうすると,1は
 各数字を3つのどれかに分類するが,1つ目と2つ目に分類される数字が1つもなければそれはダメ
2は
 各数字を4つのどれかに分類するが,1つ目と2つ目と3つ目に分類される数字が1つもなければそれはダメ
とか言った感じの場合の数の数え上げになる.
後は,包除原理を利用して求める.

C言語のスパゲッティなコード

続きを読む

January 2011 Challenge 2問目 - Chess Pushing Game (この記事を編集する[管理者用])

Source

codechef January 2011 Challenge 2問目
Problem Statement
January 2011 Challengeの参加記録

問題概要

3列の半無限のチェス盤の端に,1列に1つのコマが置いてある.
各ターン,1つのコマを選んで1マス進む.
1つ目のコマは2つ目のコマより先に行くことができず,2つ目のコマは3つ目のコマより先に行くことができない.
2つ目のコマは1つ目のコマよりDマス (7以下) より先に行くことはできず,3つ目のコマは2つ目のコマよりDマスより先に行くことはできない.
Kターン後 (10^9以下) に同じ場所に3つのコマがいるとき,そのような移動方法は何通りあるか mod 1000000007 で求める問題.

解法

状態遷移を行列で書き下して,行列べき乗.

C言語のスパゲッティなコード

続きを読む

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

2011年01月01日18時から10日間,6問.(1問はマラソン形式)
[LINK]

前回の2010年12月と比べてアルゴリズムの簡単なの4問はすごい簡単になった.
5問目は相変わらず難しい.
ってことで,4問+チャレンジ問題を解いた.
以下問題別.

・1問目 Chef attic window
難しくてわからない.方針すら立たなかった.
・2問目 Chess Pushing Game
どう考えても行列べき乗. 最初,1つ目と3つ目の差がD以下だと勘違いしてWAった.
・3問目 Count Relations
解析的に求めるだけ.簡単.
・4問目 Flu Shot Lineup
見え見えの2分探索+greedy.
・5問目 Restaurant Expansion
サイズが小さくて一瞬全探索で良いのかと思ったけど,冷静になって考えてみたらどう考えてもDPだったのでDPした.
・6問目 Splitting Giant Subs (チャレンジ問題)
1問目が解けなくてやる気なかった.適当に焼きなました.

Facebook Hacker Cup 2011 Qualification Round C問題 - Studious Student (この記事を編集する[管理者用])

Source

Facebook Hacker Cup 2011 Qualification Round C問題
Facebook Hacker Cup 2011 Qualification Roundの参加記録

問題概要

10文字以下の文字列がN個 (9以下) 与えられる.
それらを繋げてできる文字列のうち辞書順で最小のものを求める問題.

解法

効率良く解く方法もあるのだけど,今回はNが小さいのでN!通り全部試せば良い.

C++言語のスパゲッティなコード

続きを読む

Facebook Hacker Cup 2011 Qualification Round B問題 - Peg Game (この記事を編集する[管理者用])

Source

Facebook Hacker Cup 2011 Qualification Round B問題
Facebook Hacker Cup 2011 Qualification Roundの参加記録

問題概要

ボールを落とす.パチンコみたいに,pegに当たると左下か右下に当確率で移動する.
pegがなければ真下に落ちる.
一番下のある場所に落とす確率を最大化するためには,一番上のどの場所から落とせば良いか,また最大値を求める問題.
グリッドのサイズは100*100ぐらい以下.

解法

DPする.ここからゴールに辿りつける確率を各セルについて覚えておく.

C言語のスパゲッティなコード

続きを読む

Facebook Hacker Cup 2011 Qualification Round A問題 - Double Squares (この記事を編集する[管理者用])

Source

Facebook Hacker Cup 2011 Qualification Round A問題
Facebook Hacker Cup 2011 Qualification Roundの参加記録

問題概要

0以上2^31未満の整数Xが与えられるので,2つの非負整数の平方数の和で書く方法のパターンの数を求める問題.
10=1^2+3^2=3^2+1^2と順番を入れ替えたものは同一視する.

解法

平方数Yに対してX-Yが平方数かどうかを判定する.

C言語のスパゲッティなコード

続きを読む

Facebook Hacker Cup 2011 Qualification Round (この記事を編集する[管理者用])

2011年01月08日09時から72時間,3問.
予選は1問正解で通過.
[Problems] [Score board]

Facebook Hacker Cupのルール

ソースコードと出力を提出.(予選は出力のみ)
提出はインプットをダウンロード後6分以内にしなければいけない.
合ってるかどうかの判定はコンテスト終了後.
スコアは合ってる問題数,タイブレークに最後に正答を提出した時間の早いほうが上位.
(2011-01-18 15:20追記) タイブレークは最終正答提出時間から,正答提出時間の和に変更された模様.

問題A - Double Squares

0以上2^31未満の整数Xが与えられるので,2つの非負整数の平方数の和で書く方法のパターンの数を求める問題.

とりあえず問題見たけど流石にやるだけ.
(最初なかったのに,後で確認したらテストケースの数の制約が追加されていた)
平方数引いて残りが平方数かどうかチェック!
書く.
FAQを一通り読んでルール確認してからインプットダウンロード.
インプットが2回クリックしないとダウンロード出来ない….
提出しようとしたけど,提出するウインドウが開いたらテキストエリアが一つしか無い….
アウトプットを貼りつけてとりあえず提出.
これ,ちゃんと提出出来てるのか心配だなぁ….
てか,ソースコードはどこから提出するの?
わからない.
取り敢えず,ランクリストは…,上位10人しか表示されないのでよくわからない.
色々ウォール眺めてると,どうやら,予選はソースコードは提出しなくていいという噂が.
でもオフィシャルでそう言ってる記事が見つからない.
なんか色々怪しいので,残り2問は時間を置いて色々情報を集めてからにする.

何時まで経ってもオフィシャルな記事は見えない.
その代わりにTopCoderのForumで中の人が対応しているように見える.
オフィシャルの記事を探すには,TopCoderのForumを見ればいいのか,なるほど.…いや,ぇ.
まぁ,提出しなくても良さそうなので残り2問も解く.

問題B - Peg Game

ボールを落とす.パチンコみたいに,pegに当たると左下か右下に当確率で移動する.
pegがなければ真下に落ちる.
一番下のある場所に落とす確率を最大化するためには,一番上のどの場所から落とせば良いか,また最大値を求める問題.
グリッドのサイズは100*100ぐらい以下.

座標がちょっとめんどいけど.DPでやるだけ.
取り敢えず,図を書いて座標に落とすまで出来てるかチェック.
ん,これ,どこから落とすと最適化は曖昧性をなくすためにテストケースには同じ確率にならないようになっている,って書いてるけど,おなじになるテストケースがサンプルにある.
どういうこと….問題理解間違えてるの?
問題読み直しても間違えてるとは思えない.
取り敢えず,タイがあったら,できるだけ左から落とすようにしてみよう.
書いた.
後,出力の時丸めるのに,0.5を切り落とさないように最後にEPSを足して出力…と.
(と自分はしてたけど,最終的にはクレームが来て,切り捨てても切り上げても正解になったみたい)
サブミット.

問題C - Studious Student

10文字以下の文字列がN個 (9以下) 与えられる.
それらを繋げてできる文字列のうち辞書順で最小のものを求める問題.

UVaで見たことある問題だなぁ….
今回はNが9以下なので全パターン探索でいいや.
書いた.
サブミット. (意外と実行時間かかったなぁ)

Results

取り敢えず,問題なく全部通ったらしい.

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

Source

A National Bangladeshi Contest (2011-01-09) (blog)
UVa 11908

問題概要

広告を掲載することで得られる利益の最大値を求める問題.
広告のオファーはN件 (30000以下) あってそれぞれ
 場所a[i] (10^6以下) から長さb[i] (10^6以下) だけ使わせてもらうとc[i] (1000以下) 払う
という形.

解法

Segment tree (RMQ)を使いながらDPする.

UVa 11907 - Collision of Bacteria (この記事を編集する[管理者用])

Source

A National Bangladeshi Contest (2011-01-09) (blog)
UVa 11907

問題概要

2次元平面上にn個 (50以下) の長方形が与えられる.長方形はx軸y軸に平行.
各長方形は,単位時間あたりrのスピードで,各辺が中心から離れていくように大きくなる.
最も近い長方形間の距離がd以下になるまでにかかる時間を求める問題.

解法

各長方形間の距離がd以下になるまでの時間を全部求める.
2分探索しれも良いのだろうけど,距離を表す線分が斜めの場合は2次方程式を,そうればければ1次方程式を解けば良い.

UVa 11906 - Knight in a War Grid (この記事を編集する[管理者用])

Source

A National Bangladeshi Contest (2011-01-09) (blog)
UVa 11906

問題概要

R*C (100*100以下) のチェス盤の上で,とあるナイトが左上のマスにいる.
チェス盤はいくつか移動できないマスが指定されている.
このナイトは1回の移動で水平方向か垂直方向にN (50以下) だけ動いて,別の方向にM (50以下) だけ動く.
通常のナイトはN=1,M=2.
ナイトは自由に移動でき,このナイトが訪れた各マスを色分けしていく.
そのマスに直接移動可能なマスの数が偶数なら白,奇数なら黒く塗る.
辿りつけない場所は色を塗らない.
最終的に白と黒のマスの数を求める問題.

解法

DFSとかして実際に探索しながら数えるだけ.
N=Mのとき,縦にN,横にMと縦にM,横にNを重複して数えないように注意.

UVa 11905 - Map Coloring (この記事を編集する[管理者用])

Source

A National Bangladeshi Contest (2011-01-09) (blog)
UVa 11905

問題概要

50*50以下のグリッドにA~Zまでの文字が書かれている領域 (最大26個) がある.
領域は,上下左右が繋がってると思って連結である.
まず領域の内部を塗りつぶし,そのグリッドを求める.
その後,隣り合う領域は違う色で塗らないといけないとして,最小で何色で塗れるかを求める問題.

解法

まずは塗りつぶすのを頑張る.
対象の文字を壁として外から塗りつぶして,塗れない部分が中身.
後は最小色数を枝刈りしながら全探索する.

UVa 11904 - One Unit Machine (この記事を編集する[管理者用])

Source

A National Bangladeshi Contest (2011-01-09) (blog)
UVa 11904

問題概要

J[m]をそれぞれk[m]個,一列に並べる.(Σk[m]は10^6以下, m=1,2,...,n, nは1000以下)
一番右のJ[i-1]より右にJ[i]がなければならない.
並べ方の総数をmod 1000000007で求める問題.

解法

最初にJ[1]を並べて,その後でJ[2]を挿入して,その後でJ[3]を挿入して,と考える.
挿入する場所は,すでに並べた数をsumとして,最後に1個置いて,H(sum+1, k[m]-1)だけあるのでこれをかけていく.
Hは重複組合せ.H(a,b) = C(a+b-1,b).

Appendix

Recent Articles

ブログ内検索

Ads


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