Entries

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

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

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

2010年07月29日00時02分から.

Assignment

日本最強の人と同じ部屋.
最近にしては珍しく250-500-1000の普通のセット.

EASY

六角形座標で陸と海からなる50*50以下のグリッドが与えられる.
浜辺(陸と海の境界線)の長さを求める問題.

六角座標だ,うげー.
えーと,図がある,図を見る.問題文の最後を見る.ビーチの長さを求めるらしい.
入力が正方形格子っぽいのはどういうふうになってるのか,だけ,問題文をちゃんと読む.
やるだけ.
隣り合うのを見て,一致してなければ足していく.
書いた.サンプル合った.サブミット.

MEDIUM

200個以下の整数が与えられる.
その中から,2つの整数を選んで,互いに素で,2乗の和が平方数になっているなら取り除ける.
最大で何回取り除けるかを求める問題.

マッチング…っぽい,ってかマッチング.
最大流になる…?
DPで解ける…?
うーん.
わからない.
2部グラフにでもなるんかいな?
ならんだろう…. (なるよ!)
うーん,てか,上位陣が瞬殺してる,何に気づいてないのだ?
わからない.
みんな瞬殺してるので,今から時間かけて解いても,順位的にダメな気がする.
ランダムで嘘解法を提出しておいて,HARDをやろう.
きっと,死亡フラグだけど….
ランダム解法提出.

HARD

ノード数200以下の木が与えられる.各枝には距離が定義されている.
枝がない場所の移動は,K回まで距離Lで移動できるとき,各枝を最低でも1回通る閉路で最短のものの長さを求める問題.

問題を読む.ふむふむ.(木であることを読み飛ばしている)
次数が奇数同士のところで適当につなげれば良い.
つなげるときに,あまりに長いと,ショートカットして長さLの枝をgreedyに付け加える.
えっと,グラフが連結じゃないと困るな…,連結なの?
グラフは木らしい.連結だ.
….
適当につなげればよい.って適当ってどうやるのさ?
次数が奇数のノードの数って,最大で…200.
全探索とかビットDPとか,そういうの無理.
えーっと,木に限定されているのだから,木であることを有効活用しないとダメなはず.
うーん,わからない.
木だと,次数が奇数同士のノードのうち,もっとも近い場所から繋げていけばいいのではないか…?
嘘っぽい,たぶん嘘.
でも,時間がもうない.
嘘解法書いたらサンプルが全部通る.
もっと解が良くならないか,ランダムに1.75秒間,探索して,よくなるならそれを採用する.
また,ランダム使った嘘解法.
提出.

Challenge

500と1000は落ちると仮定して,250はそこそこ早いほうだから,チャレンジ失敗したら大変なことに….
で,250は落ちないし,他は解けてないので,取り敢えず500と1000の解法を理解することから始まる.
500は2部グラフになるのか!
偶数同士はGCDによってない.
あれ?奇数同士は?ないの?
わからないけど,ないのだろうか….(無いと知ってる状態で証明考えたら1分ぐらいで証明できたけど,無いことは思いつけない気がする)
1000は…DPぽいのかな,よくわからない.
これは,どの問題もみんな落ちない予感….
と思ってたら,500がぼろぼろ落ちてる.なんで落ちてるのか不明.
チャレンジはずっと静観してました.

System tests

EASYのみ通って,あと落ちる.
グラフ問題セットだと仕方ないかなぁという気もするけど,考える力というか考える気力がたりてない.
500は,これは2部グラフになるはずだ,そうじゃなきゃ解けないもん,っていう考え方をしないと思いつけないなぁ.そして,そういう考え方をするべきだった.

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

2010年07月26日22時から2時間,5問.
[ Link ]

A. Ring road

全てのノードの入次数 + 出次数が2で,弱連結な有向グラフが与えられる.
(無向グラフに直したら,1つの大きなサイクルになっているグラフ)
それぞれの枝の向きを変えるコストが与えられたとき,全ノード間を移動できるようにする最小コストを求める問題.

問題の意味を理解するのに少し手間取る.
全てのノードに対して,次数が0になればいいので….
次数2のノードに対して,コストの小さい方をひっくり返せば良い!
サンプル合わない.
ひっくり返したことで,隣のノードが次数2になるかもしれない….
普通にDFSで,1周回って,反転してる枝のコストを数えればいいのでは….
書いた.サンプル合った.サブミット.Accept.

B. F1 Champions

F1のレース結果が与えられる.
1位は25pt,2位は18pt, … というふうにレースごとにスコアが加算される.
優先度が,
 スコア順,1位を取った回数順,2位を取った回数順,…
でソートした時の1位の選手名と
 1位を取った回数順,スコア順,2位を取った回数順,…
でソートした時の1位の選手名を出力する問題.

ソートするだけっぽい.
vector<int>に優先度順に突っ込んでsortする.
サンプルは通った.サブミット.Accept.

C. Sequence of points

2次元上の,奇数個の点A[0], A[1], ..., A[n]が与えられる.
初期点が与えられて,tステップ目にその点を
 A[t%n]に対して対称に移動する
という操作をjステップ行った後の点の座標を求める問題.
nは10^5以下,jは10^18以下.

うーん,10^18回素直に計算することはできない.
でも,x座標と,y座標は分けて計算すればいいよね.
うーん,いや,まてまて.
これって,答え,long longで収まるのか?
収まらない気がするけど,mod pで出力するとか書いてないし…,多倍長?
ちょっと,紙の上でシミュレーションしてみよう….
n=4の場合…,どうみても発散していく気がする….
無理っぽ.
いや,なんか,nは奇数とか書いてある.
奇数の場合は…,もしかして発散しなさそう?
しかも,途中で最初に戻ってくる気がする.
周期的な部分を検出して,周期的な部分は適当に飛ばせば良いのでは.
周期を検出して書いてみる.
大きいランダムケースもすぐ終わった.
周期調べると,全部2n周期になる?
まぁ,良さそう,サブミット.WA.
あれ,long longにしないと答えがオーバーフローするのかな? (しなかった)
long longに直す.WA.
うーん,あ,long longに直し忘れてる箇所が1箇所あった.WA.
あれー.
自分でテストケース幾つか作って確かめる.
あ,jがちょうど周期で割り切れる場合,breakし忘れで,1個余分に移しちゃう….
直した.サブミット.Accept.

D. Broken robot

1000*1000以下のグリッドのある場所に最初ロボットがいる.
時間1後,
 今の場所,ひとつ下,ひとつ右,ひとつ左
のうち,盤面の外に飛び出さない方向を1つ選んで当確率に移動する.
一番下の行についたら止まる.
止まるまでの時間の期待値を求める問題.

うーん.サイズが大きい.
連立一次方程式を解いてたら間に合わない.
収束するまで回しても,多分そんなに収束しない.
わからないので,先にEを読む.
Eが瞬殺問題だったので,終わらせて戻ってくる.
dp[i][j]を(i,j)にロボットが居るとき,一番下の行に辿りつくまでの期待値としよう….
k行目の期待値は,k+1行目の期待値のみに依存する.
なので,行ごとに分けて考えれば良い.
でも,1000回,1000変数の連立一次方程式を解くはめに….
対称性を使うと500変数ぐらい.
無理.
ぴかーん.
k+1行目が全部分かっていて,k行目の一番端の値を決めつけたら,k行目の残りの値はわかる.
一番端の値で2分探索すればいいのではない?
逆の端の値が,本来の値より大きいなら,小さくして,小さいなら大きくする.
書いてみる.
いや,端の値から,次の値を求める式が,単調性が成り立たない,2分探索無理.
うーん.
うーんうーん,制限時間の限り,回してみてdp[i][j]が収束しないか調べてみる.
なんか,求める桁数も小数点以下4桁までで良くて,精度荒くていいっぽいし.
あれ,なんか,1000*1000でも,小数点以下5桁まであうっぽいぞ….
提出.WA.
やっぱり駄目かー.
一応,制限時間ギリギリを狙って,ループ回数を調整.
同じところでWA.
あれ,ちょっと,これって,もしかして….
グリッドのサイズの幅が1のとき,普通に間違える….
修正.サブミット.Accept.

E. Berland collider

1次元で,等速直線運動してる粒子が500000以下与えられる.
逆向きに動く粒子が初めて衝突するまでの時間を求める問題.
同じ向きの粒子は,あたってもすり抜ける.
衝突しないならそれを指摘する.

うーん,なんかよくわからないけど2分探索の匂い.
2分探索で行ける!
時間tまでに衝突するかどうかは
 ある左向きの粒子より,初期位置が左にある粒子のうち,時間tで最も右にある粒子の位置と,左向きの粒子の時間tでの位置が最初と反転していたらぶつかる
というふうな判定をすればいい.
書いた.サブミット.通った.

Result

一応5問解いて,赤復帰.
でも,ケアレスミスが多すぎる.

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

2010年07月25日01時02分から.

Assignment

全体の参加者で赤が半分以上.
うさぎさんと空さんと一緒の部屋.

EASY

50人以下の銀行の残高が与えられる.
毎週,残高の額に比例する確率で,1人当選して,賞金が配られる.
N週後の0番目の人の残高の期待値を求める問題.
Nは1000以下.

Round 4はEasyは難しい.
Mediumはもっと難しい.
Easyを正確にそれなりの速さで解けば通る.
落ち着いて解け,と言い聞かせる.
問題読む.
ちょっと,問題長い.
大丈夫,落とさないように,ゆっくり読む.
うーん,期待値…,読んだ.
え,ちょっと,これすごい簡単.普段のDIV1 EASYより簡単.のんびりしてたらダメだよ!
適当に,線形性使って,毎週,割り振っていくだけ.(当たる確率は毎週不変であることは気づいてなくてN回ループ)
書く.通らない.
初期化忘れてる.
サンプル通った.サブミット.

MEDIUM

P(n) = nの各桁の積とする.
S = (P(1), P(2), ... )という無限列とする.
長さ50以下の列が与えられたとき,Sの連続部分列としてそれが現れる最初の場所を求める問題.
与えられる列は,Sの中に存在することは保証されている.
与えられる列の各要素は1000000000以下.

嫌らしそうな問題きた.これはいかにも落ちそう.
さて,方針が全く立たない.
うーん.
最初の要素と次の要素を比べて,(n+1)/n倍になっていたら,最初の要素の場所の下1桁はn.
後は,全部,場所の下1桁の数で割って,再帰的にやれば行ける?
0で割ることはできないが….
いや,最初から0しかないとかあり得るわけだし.
そもそも,要素数が1のとき困るではないか.
要素数1のときはどうするの?
うーん….
もしかして:全探索
与えられた列に0だけしかない場合は,適当に例外処理してやる.
そうじゃなかったら,0じゃない要素を1個見つけてきてあげて,それが満たす場所を全列挙して確かめる.
いけそうな気がする.書いてみよう.
….
え,いけるのか?
1を使うと無限に長いのまでできちゃうぞ?
全列挙って言っても無限に可能性がある.
でも,あんまり上の桁で1を使う意味ないことないか?
だって,全部で1を使っていたら,それを取り除けば,より早い場所に存在することになる.
与えられる要素の数が50までだから,100の位より上に1って出てくる事ない.
だから,有限通りしか可能性はない!
よし,書く.
書いた.
通らない.
何バグってたか忘れたけど,バグを取り除く.
サンプル通った.
サブミット.
さて,これって間に合うのか….
ランダムケース生成.
間に合わないorz
これだから,焦るなよ! でもやってしまったものは仕方ない….
うーん.
例えば,87650って答になるか?
67850の方が良いよね….
百の位以上で1を使わないのと同じように,上の桁は,小さい順にソートされてるはず.
これで探索スペース劇的に減るはず枝刈り.
色々ランダムケースを食わせても,200msぐらいで終わる.
自分で,最悪ケースっぽいの作っても400msで終わる.
いける!
リサブミット.

HARD

2次元平面上の1200点以下が与えられる.
どの3点も一直線上にはない.
4点選んで,線分を引いて,交わるようにする方法の数を求める問題.

どうせRound 4のHARDとか無理ゲー.
一応開いてみたけど,わからない.
30分ぐらい残ってるけど,EASYとMEDIUMの見直しをする.
MEDIUMの撃墜ケースを考えておこう.

Intermission

MEDIUMの撃墜ケースは何だ?
TLEする人多そうな気がするが…,でも,Round 4だしなぁ,みんな凄い人ばかりだしなぁ.
チャレンジ失敗して,MEDIUM落ちると,通過できなくなるので,絶対成功するの以外手を出さないことにする.
チャレンジせずに,MEDIUM落ちても,通過できる可能性は…微妙だけどありそう.
EASYはさすがに今回の問題だと落ちないよなぁ…,落ちないよなぁ…,たぶん…,怖い….

Challenge

MEDIUMで全部0なら,って例外処理してる人で,0の個数の場合分けの境界間違ってる人がいる.
これは落ちる.落とせる.落とした.
後はのんびり眺めてるだけ.

System tests

EASYとMEDIUM通った.
MEDIUMは自分が最悪ケースだと思ってたのは全然最悪じゃなくて,システムテストの最悪ケースだと1.7秒かかってた.
怖い…,ってか,本当なら落ちてて良いレベル….
ちょっと,枝刈りに手を抜きすぎてた,でも通ったら正義.
通過ラインは,EASY早解きだったみたい.

Aizu 2200 - Mr. Rito Post Office (この記事を編集する[管理者用])

Source

ACM/ICPC OB/OGの会 模擬国内予選 2010 (2010-06-27)
Aizu 2200

問題概要

ノード数200以下,枝数10000以下のグラフが与えられる.
順番に移動すべき目的地が1000個以下与えられる.
最初,リトさんと船は最初の目的地に居る.
枝は2種類あって,陸路と海路がある.また,枝には通る必要時間が定められている.
陸路はリトさんが単独で動かなければならず,海路はリトさんと船が同時に動かなければいけない.
全ての目的地を回るまでの最小時間を求める問題.

解法

全節点間の陸路のみ,海路のみで移動できる最小時間をワーシャルフロイドで求めておく.
後は,
 dp[i][j] = リトさんがi番目の目的地にいて,船がノードjにいる状態になるための最小時間
でDPする.
 陸路で船を拾いに行って,船を移動させて,陸路で目的地まで移動
 陸路のみで移動
の2パターンの移動方法があることに注意する.

Aizu 2198 - Moonlight Farm (この記事を編集する[管理者用])

Source

ACM/ICPC OB/OGの会 模擬国内予選 2010 (2010-06-27)
Aizu 2198

問題概要

50種類以下の作物がある. 作物の名前,種1個の値段,それぞれのある段階からある段階まで育つ時間,できる実の数,実の値段,何回実がなるか,が与えられる.
2回以上実が成るときは,実がなった後,葉の段階まで戻る.
時間あたりの金銭効率が高い作物から順番に出力する問題.
同じ金銭効率の作物があれば,名前が辞書順で早いものから出力する.

解法

ソートするだけ.

Aizu 2197 - Sum of Consecutive Integers (この記事を編集する[管理者用])

Source

ACM/ICPC OB/OGの会 模擬国内予選 2010 (2010-06-27)
Aizu 2197

問題概要

1000以下の自然数Nが与えられるので,Nを連続する2つ以上の正の整数の和で各方法は何通りあるかを求める問題.

解法

やるだけ.

Aizu 1171 - Laser Beam Reflections (レーザー光の反射) (この記事を編集する[管理者用])

Source

ACM/ICPC Japan 2010 Domestic
Aizu 1171

問題概要

レーザーの始点と終点,鏡の位置が与えられたとき,レーザーを終点に当てるようなパスで最短のものの長さを求める問題.
鏡の数は5個以下で,最短路は最大で5回までしか反射しないもので,それが存在することも保証されている.

解法

鏡にあたってレーザーが跳ね返る代わりに,レーザーは直進していて,鏡と終点が全部,ぶつかった鏡に線対称な一に移動すると考える.
そうすれば,当たる鏡の順番が与えられたら,どちらの方向にレーザーを放てば終点に辿りつける可能性があるか,が一意に定まる.
なので,当たり鏡の順番を全列挙して,それで実際に終点にあたるか確かめる.

Aizu 1170 - Old Memories (古い記憶) (この記事を編集する[管理者用])

Source

ACM/ICPC Japan 2010 Domestic
Aizu 1170

問題概要

この問題は文字列といえば,アルファベットとピリオドの27文字からなるとする.
40文字以下の文字列Aと,30個以下だけ13文字以上20文字以下の文字列B[i]が与えられる.
 どの文字についても,その文字を含む部分文字列の中で,Bの要素を一致するものが存在する
 d回以下の,文字の挿入,文字の置き換え,文字の削除の操作でAにできる (編集距離がd以下)
を満たすような文字列の数を求める問題.
もし,答えが5以下なら,ついでに列挙する.
dは2以下.

解法

Bを繋ぎあわせてできる,Aの文字数と高々d違う文字列を列挙して,編集距離がd以下かどうかDPで判定した.
途中までの編集距離から枝刈りも行った.
(ニコニコ生放送で書いた時のコードから,同じ文字列を生成してしまったときに,枝を刈る前に,新しい文字列で編集距離のDPを計算しているという無駄なことをやめたら2倍ぐらい速くなった)

UVa 11817 - Tunnelling the Earth (この記事を編集する[管理者用])

Source

Waterloo Local Summer 2010 (2010-07-11)
UVa 11817

問題概要

地球上の2点の経度と緯度が与えられる.
その2点間を移動するにあたって,直線で移動した場合と,球の側面に沿って移動した場合の移動距離の差を求める問題.

解法

幾何.やるだけ.

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

Source

Waterloo Local Summer 2010 (2010-07-11)
UVa 11816

問題概要

従来2種類の消費税がかかっていたのを,消費税のシステムを一本化しました.
各品物について,消費税は定められていて,従来は,税率A%とB%,新しいシステムでは税率C%です.
それぞれの税金の計算方法は,セント以下を四捨五入して丸めて,計算します.
買ったもののログ(品物の名前と買った額)が与えられるので,旧システムと新システムで得られる税収の差額を計算する問題.
品物の種類は100000種類以下,ログは100000個以下.

解法

やるだけ.ちゃんと税額を計算する.

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

Source

Waterloo Local Summer 2010 (2010-07-11)
UVa 11815

問題概要

ノード数1000以下,枝数1000以下の有向グラフが与えられる.
ノードは,必要とするアイデア,作れるアイデアが定められている.アイデアの種類は1000以下.
枝は,その枝を通過したときに,パケットが覚えておけるアイデアの集合を定められる.
パケットは,ノード0を出発して,色々なノードをめぐる.
ノードを通ると,そのノードが作れるアイデアを全部覚える.また,枝を通ったときに,覚えておけないアイデアは忘れる.
その際,どの経路を通って,ノードPにたどり着いたとしても,ノードPが必要とするアイデアを全部覚えておく必要がある.
そのような条件を満たす,枝を通過したときに覚えておけるアイデアの集合のうち,最小のものを求める問題.

解法

ある枝がアイデアIを覚えておけないと駄目な条件は,その枝の終点のノードから,アイデアKを作れないノードのみを通って,アイデアKを必要とするノードに辿りつけること.
なので,アイデアIごとに,枝の向きを逆向きにして,アイデアIを必要とするノードを始点としてDFSした.

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

Source

Waterloo Local Summer 2010 (2010-07-11)
UVa 11814

問題概要

ノード数100以下,枝数100000以下の有向グラフが与えられる.
枝には絶対値が40以上220以下の整数のラベルが付けられている.
クエリが100000個以下与えられて,あるノードからあるノードに移動する,以下の条件を満たす,正の長さのパスのうちもっとも短いものの長さを求める問題.
最初と最後はスタックが空で,ラベルが正の枝を通過したとき,スタックにその数字を積む.ラベルが負の枝が,ラベルの絶対値がスタックの最後に積まれてないと移動できず,移動するとスタックの最後の要素を消す.
枝の長さは全部1.

解法

(開始ノード, 終了ノード)の組を状態としてBFSする.
例えば,A→Bまで長さKで行けるなら,+Lの枝と-Lの枝を使って,
 A→B→C→D (A→Dは長さK+2でいける)
 C→D→A→B (C→Bは長さK+2でいける)
 C→A→B→D (C→Dは長さK+2でいける)
という感じに更新していく.
ラベルがlong long 3個に押し込めるので,bit演算などを使った.それでもO(100^4)だと思うのだけど,実行時間は大してかからず通った.

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

Source

Waterloo Local Summer 2010 (2010-07-11)
UVa 11813

問題概要

ノード数100000以下,枝数100000以下の無向グラフが与えられる.
枝には距離が付与されている.
自分の家(ノード0)と,行きたい店のノード番号(10個以下)が与えられる.
自分の家を出発して,行きたい店を全部訪れて,自分の家に戻る最短距離を求める問題.

解法

行きたい店をそれぞれ始点として,店の数の回数だけダイクストラして,関係するノード間だけのグラフを作る.
後は,巡回セールスマン問題をビットDPで解く.

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

2010年07月18日01時02分から.

Assignment

250-550-1000の微変則セット.
数分遅れぐらいで参加して,あんまり部屋の様子見てなかったけど,個人的に有名な日本人2人と同じ部屋.
そして,自分以外の赤が居ないという珍しい状況.

EASY

ペットがN種類いて,その中でK匹選んで飼う.
かかるコストは,それぞれa[i]+b[i]*(K-1)で与えられる.
aとbと,支払える最大コストが与えられたとき,最大のKを求める問題.
Nは50以下.

んー.
問題文が分かりにくい.
焦るな,焦るなよ…,僕.
意味理解.(嘘)
K種類飼えるかどうかは,greedyに判定できるから2分探索.
ん,greedyに判定する?
同じ種類のは1匹までしか飼えないの?
飼えない.
じゃ,答えの上限50だから,全部試そう….
がりがり.
書いた.サンプル通った.サブミット.

MEDIUM

ソーシャルネットワークで,各個人のページには,友だち登録してるうちの中からランダムにK人へのリンクが表示される.
K人以下しか友達がいなければ,全員表示される.
N人の友達関係(友達関係はその中で閉じている)が与えられたとき,自分のページから初めて,自分の友達を全部ちょうど1回ずつリンクをたどって辿りつける確率を求める問題.
次に行く友達のページは,達成確率を最大にするように選ぶ.
Nは36以下.おのおのの人の友達の数は高々15.

問題文長い….
取り敢えず,制約を読む.
Nの最大値が36??
2つに分割して全探索みたいなのみたいに2^(N/2)とかになるの?
問題を読む.
DPっぽいけど,普通にやると2^N….
いや,自分の友達だけを考えれば良いのだから,2^自分の友達の数.
でも,50文字の半分ぐらいで最大で25とかありそう.
うーん.
ん?
50ってみなかった気がする.
制約を見直す.
文字列の長さは36以下!
え,それだと,自分の友達の数は最大でも18.
もっと少ないはず,最大でいくらだ?
15.
DPでいける….
書こう.
えっと,複数の人に行けるなら,greedyに行けばいい.
コンビネーションを使って,上位2人は表示されてなくて,3人目が表示される確率とか,そういうのを使う….
書いた.合わない.てか,確率なのに,答えが1超えてる.
うーん.
表示される確率の計算間違えてた.
直した.サンプル通った.サブミット.

HARD

n個の部屋があって,m個の通路があって,通路は船で移動する.
船で移動すると,移動した方向に船が1個移るため,もともと設置された船の数の人数分しか移動できない.
船は,通路の両側にそれぞれ何個設置されてるか与えられる.
部屋0に脱出ポットがある.k人の職員がいる.
職員が何処にいても,部屋0に全員がたどり着けなければいけない.
通路に,最小で何個の船を付け加えれば,全員が0に辿りつけるようになるか求める問題.
不可能ならそれを指摘する.
nとmは50以下.
それぞれの部屋は,高々1個のカノニカルサイクルに属す.
カノニカルサイクルとは,C[0]-C[1]-C[2]-…C[N]がサイクル(C[0]=C[N])だとして,C[0]が最も部屋番号が小さく,C[1]よりC[N-1]が大きい.

うーん,これも問題が読みにくい….
読んだ.
わからない….
カノニカルサイクルとか何だ….
わからない.
うーん,職員の配置の最悪の場合って何.
同じ場所に全員いる場合の気がする.
職員の配置がわかったら,付け加える最小の船の数ってわかるの?
最小費用流!
職員の配置を,どこかに固まっているとして,最小費用流流して,全配置のうち,最悪ケースを返せばいい.
書く.
合わない.
違うよ…,何処にいても脱出できないと駄目なので…,全てのケースを同時に満たさないといけない….
うーん.
このカノニカルサイクルって何だ?
長さ4以上のサイクルは全部これ満たすのでは…?
なるほど,取り敢えず,グラフが木だったらすぐできる.
それは,適当に,0の部屋方向に,kより少なかったら船を配置するだけ.
後は,サイクルの部分は,各サイクルに含まれるノードに職員を集中させて最小費用流流して,最悪ケースを足していけばいいのでは.
本当にいいのか?
わからないし,そもそも実装するような時間が残ってなかった.

Challenge

まぁ,静観するつもりで….
うーん,この250って,答えがNのとき,止まらないのでは…,というか,答えが際限なく大きくなるかRuntime Errorになりそう.
殴ってみる.落ちなかった.
うーん,あれぇ,落ちそうなのになぁ,もうちょっと眺めてみる.
あ,チャレンジが得意なお方に落とされた.
しょんぼり.

System tests

やっぱり自分はチャレンジには向いてないことを再認識するべき.
レートはなんかちょっと上がった.これでも上がるのね….

Open 2010 Round 3 HARD - Passwords (この記事を編集する[管理者用])

Source

TopCoder Open 2010 Algorithm Round 3 HARD (1000pt)
Problem Statement
Open 2010 Algorithm Round 3 自分の参加記録

問題概要

アルファベットと数字からなるN文字の文字列のうち以下の条件を満たす物の数をmod 1000000009で求める問題.
 小文字アルファベットを少なくてもL文字含む
 大文字アルファベットを少なくてもU文字含む
 数字を少なくてもD文字含む
Nは200000以下.

解法

使う数字の数が大きい方からループして計算する.
適当に組み合わせの数を掛けるのを除外すると,ループの中で計算しないといけないのは
 E(n) = C(n,st) + C(n,st+1) + ... + C(n,ed)
といったものになる.これを毎回計算するとTLE.
次のループで計算しないといけないのは
 E(n-1) = C(n-1,st) + C(n-1,st+1) + ... + C(n-1,ed-1)
となって,二項係数の漸化式を用いて
 E(n-1) = 2*E(n) + C(n-1,st-1) + C(C-1,ed)
という形の漸化式で計算すれば間に合う.

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

続きを読む

Open 2010 Round 3 MEDIUM - TheChroniclesOfAmber (この記事を編集する[管理者用])

Source

TopCoder Open 2010 Algorithm Round 3 MEDIUM (500pt)
Problem Statement
Open 2010 Algorithm Round 3 自分の参加記録

問題概要

50人以下の人の初期位置と,それぞれの目的位置が与えられる.
それぞれはワープできて,別の人と同じ位置に一瞬で移動できる.
ただし,ワープは,順番にやらないと駄目で,2人の位置を入れ替えることは出来ない.
ただ,ワープする間隔はどんなに短くても良い.
全員歩く速度は1.
全員が目的地につくまでの最小時間を求める問題.

解法

テレポートすることによって,何処か初期位置の1箇所を使わないのであれば,すべての人が自由に初期位置を選べる.
なので,使わない場所を1箇所選んで,後はgreedyにテレポートさせれば良い.
誰もテレポートしない場合も忘れない.

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

続きを読む

Open 2010 Round 3 EASY - SieveOfEratosthenes (この記事を編集する[管理者用])

Source

TopCoder Open 2010 Algorithm Round 3 EASY (250pt)
Problem Statement
Open 2010 Algorithm Round 3 自分の参加記録

問題概要

2~maxNumの間にある素数をエラトステネスの篩で求めようとしたとき,一番最後に消される合成数を求める問題.
maxNumは20億以下.

解法

要するに,素因数分解したとき,含まれる最小の素数が最も大きい物の中で,最も大きい数字を返せば良い.
最小の素数は,二乗してmaxNumを超えない最大の素数に固定できて,後は全部チェックする.
2^3を除けば,答えは2つの素数の積で掛けることを利用すれば計算量の削減ができる.(が2^3に気づかず落ちる可能性のほうが高いと思う)

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

続きを読む

Aizu 2199 - Differential Pulse Code Modulation (この記事を編集する[管理者用])

Source

ACM/ICPC OB/OGの会 模擬国内予選 2010 (2010-06-27)
Aizu 2199

問題概要

N要素の0以上255以下の整数からなる数列x[1..N]と,16個以下の-255以上255以下の整数からなる数列Cが与えられる.
y[0]=128として,y[n+1] = round(y[n] + C[k])という形で数列yを定める.kは自由に選べる.
ただし,round(a) = max(0,min(255,a)).つまり負なら0にして,255を超えると255にする関数.
∑ (x[k] - y[k])^2の最小値を求める問題.∑はk=1..Nについての和.

解法

DP.今数列の何個目か,前回使った数字はいくらか,を状態とする.

Aizu 1169 - The Most Powerful Spell (最強の呪文) (この記事を編集する[管理者用])

Source

ACM/ICPC Japan 2010 Domestic
Aizu 1169

問題概要

ノード数40以下,枝数400以下の有向グラフが与えられる.
枝には,文字列が付与されている.
始点と終点が与えられたとき,パスの重み(通った枝の文字列を連結したもの)が辞書順で最小のものを求める問題.
辿り着けない場合,いくらでも小さくなるパスが存在する場合はそれを指摘する.

解法

普通にDPしようとすると,ループの判定が難しい.結局ベルマンフォードみたいな感じで通した.
cafelier先生のblogに解法がいくつか紹介されています.

Aizu 1168 - Off Balance (ぐらぐら) (この記事を編集する[管理者用])

Source

ACM/ICPC Japan 2010 Domestic
Aizu 1168

問題概要

日本語の問題文が存在するので簡潔に書く.
積まれているブロックが安定化どうかを判定する問題.
安定とは,全てのブロックが安定であること.
ブロックが安定とは,ブロックとその上に乗っているブロックの重心が,ブロックの下に触れてる部分の範囲の厳密に中にあること.
盤面のサイズは60*10以下.

解法

実装問題,やるだけ.
まず全部のブロックに番号をつけなおしてあげて,それぞれのブロックのサイズ,重心の位置を求めておいた.
後は,ブロックの上にブロックがある(支えている)という関係でグラフを作って,全てのブロックに対して,DFSして,支えているブロックの集合を求めて,重心を求めて判定していった.

Aizu 1167 - Pollock's conjecture (ポロック予想) (この記事を編集する[管理者用])

Source

ACM/ICPC Japan 2010 Domestic
Aizu 1167

問題概要

日本語の問題文が存在するので簡潔に書く.
四面体数はn(n+1)(n+2)/6で表される数.
10^6以下の正整数が与えられるので,それを四面体数の和で書くとき,最小で何個の和になるかを求める.
また,奇数の四面体数のみしか使用できない場合についても,同様に求める.
同じ四面体数を何回使っても良い.

解法

典型的DP.

Aizu 1166 - Amazing Mazes (迷図と命ず) (この記事を編集する[管理者用])

Source

ACM/ICPC Japan 2010 Domestic
Aizu 1166

問題概要

日本語の問題文が存在するので簡潔に書く.
30*30以下の迷路が与えられるので,左上から右下にたどり着く最短ステップ数を求める問題.

解法

BFSする.
アスキーアートのまま扱って,2マス上下左右に移動するとき,その間が0なら移動できるとした.

Aizu 1165 - Pablo Squarson's Headache (角角画伯,かく悩みき) (この記事を編集する[管理者用])

Source

ACM/ICPC Japan 2010 Domestic
Aizu 1165

問題概要

日本語の問題文が存在するので簡潔に書く.
k番目に置く正方形は,j (jはkより小さい)番目に置かれた正方形の,上下左右どこに置かれるか(隣接するように置く),という情報が与えられるので,x軸y軸に平行なバウンディングボックスのサイズを求める問題.
置く正方形の数は200未満で,正方形のサイズは1.

解法

やるだけ.それぞれの正方形をおいた座標を覚えておいて,x座標,y座標ともに,最大値 - 最小値 + 1を返せば良い.

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

2010年07月11日01時02分から.

Assignment

Round 3にもなると,赤と黄色しかいない部屋になったりするのかぁ.
でも,まだ,赤の比率の方が低い.

EASY

2~maxNumの間にある素数をエラトステネスの篩で求めようとしたとき,一番最後に消される合成数を求める問題.
maxNumは20億以下.

うーん,Round 3とか,普段より難しいはずだし,慎重にじっくりやれ.
合成数だけど,素因数分解したとき,最小の素数が最も大きいもの.
その中で,相方の素数が最も大きいものを返せば良い.(!?)
エラトステネスの篩で,√20億ぐらいまで素数作って,2乗がmaxNumを超えない最大の素数を持ってきて,
もう1個の素数は,適当に,かけてmaxNumを超えないように最大のを取ってくる.
サンプル合う.サブミット.
ちょっと,見直す…,サンプルに境界ケースがない.
怖いなぁ…,等号忘れてないかなぁ….
いろいろテストする,大丈夫そう.
summaryみると,resubmitしてる人がいる.サンプルに境界無いからなぁ.
ん…,petrがresubmitしてる?…,え,そういう問題じゃなくてなんかへんなケースあるのか?
うーん,わからない,でも,多分合ってるでしょ,次の問題行こう.

MEDIUM

50人以下の人の初期位置と,それぞれの目的位置が与えられる.
それぞれはワープできて,別の人と同じ位置に一瞬で移動できる.
ただし,ワープは,順番にやらないと駄目で,2人の位置を入れ替えることは出来ない.
ただ,ワープする間隔はどんなに短くても良い.
全員歩く速度は1.
全員が目的地につくまでの最小時間を求める問題.

EASYはシンプルだったのに,こっちは問題文長いよ….
うーん,わからんけど,二分探索の香り.
テレポートは取り敢えず,一番最初にすれば良いよね.その後,移動できるんだから….
時間Tが与えられて,その時間で全員が目的地に付けるかどうかを判定する方法を考えよう.
テレポートせずに移動できる人の集合を決めて,その他の人は,動かなかった人の場所にテレポートして移動できるようになるか調べる.
これでいいのでは….
書いてみる.
サンプルが合わない.
あー,そうか.
テレポートせずに辿りつける人の集合から初めて,その他の人は,すでに辿り着くことが出来る人の初期位置にテレポートして,辿りつけるなら,辿りつける人の集合に入れる.
これを繰り返せば良いのでは.
うー,1個だけサンプル合わない.
ちゃんとサンプルの例を紙に書いて検証してみる.
なんと!
テレポートしなくてもいい人がテレポートしないと上手くいかない!
こんな感じもあるのか….
うーん?
もしかして,これって….
全員の初期位置が移動してないか,どこか1箇所以上,初期位置を使わない場所があれば,全員自由な位置から出発できるのでは….
証明できるか?
証明できた.
書く.
使わない場所でループ回して,各々の人が,一番近い場所からスタートすれば良い.
(後で思えば,それだと2分探索要らなかったのでは…)
サンプル通った.サブミット.

HARD

アルファベットと数字からなるN文字の文字列のうち以下の条件を満たす物の数をmod 1000000009で求める問題.
 小文字アルファベットを少なくてもL文字含む
 大文字アルファベットを少なくてもU文字含む
 数字を少なくてもD文字含む
Nは200000以下.

あれ?簡単じゃないの?こんなのすぐ計算できそうだけど.
しかも,O(N)でもOK.
あ,コンビネーション計算したいから,N小さめなのかな….
えーと,O(N)が許されるんだから,小文字アルファベットの文字数で場合分けしよう….
いや,対称性考えると,数字の文字数で場合分けしようか….
えっと,後は,
 E = C(n,st) + C(n,st+1) + ... + C(n,ed)
みたいなのをO(1)で計算できれば良い….
できないじゃん….
うわー.
いや,前の結果が使えるのでは…?
前計算したのは,
 D = C(n-1,st) + C(n-1,st+1) + ... + C(n-1,ed-1)
だから,コンビネーションの漸化式使うと…
 E = 2*D + C(n-1,st-1) + C(C-1,ed)
となる!
できた.
書く.
合わない….
あれぇ….
添字が1個違った….
サンプル合った.
サブミット.

Intermission

そういえば,250って,素数の積でいいの?
良さそうだけど….
証明してみよう….
あれ,….証明できなくないか….
ってか,8のとき,答え8だよ…!?
自分のコードを試してみる,6が返ってくる,死んだ.
あー,結構良い順位だったのに….

Challenge

250で他に素数の積に限定してる人いないかな…?
いた!撃墜.
この人も,素数×素数を返している.と思ったら素数判定が妙な素数判定でちゃんとしていた.失敗.
素数×素数っぽい.撃墜.
以下略.
9成功1失敗で+425点…,ぇ.

System tests

MEDIUMとHARDは通った.
部屋の人は,ちゃんと判定してる人も,素数×素数に限定してる人がいると思ってなかったらしく,チャレンジして無かった.
部屋割りが良かったなぁ….
ってことで,人生2度目の勝利.

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

Source

TopCoder SRM475 DIV2 HARD (1000pt)
Problem Statement

問題概要

無限に長い一直線上のグリッドをウサギが移動する.
最初ウサギは0にいて,1000000001に移動したい.
2通りの移動手段があって,
 small jump: 今いる場所から2マス前,2マス先のどちらかに移動できる.
 jarge jump: 今いる場所からxマス前,xマス先のどちらかに移動できる.
xは与えられる定数で3以上1000000000以下.
また,穴の開いている区間も与えられて,その区間内に移動することは出来ない.飛び越えることは可能.
区間の数は25以下.
目的地にたどり着くための,large jumpの最小回数を求める問題.
辿り着けないならそれを指摘する.

解法

穴の開いてない区間に分割を考えて,その区間の偶奇が一致するグリッドはsmall jumpで移動できるので同一視してグラフを作る.
グラフのノードは高々52で,large jumpで移動できる場所に枝を張って,最短路を求めれば良い.

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

続きを読む

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

Source

TopCoder SRM475 DIV2 EASY (250pt)
Problem Statement

問題概要

ウサギ50匹以下いる.
それぞれ,いるウサギの名前を書いて投票する.
最も獲得票の多いうさぎの名前を求める問題.
ただし.自分自身に投票したら無効票となり,1位が複数いるなら空文字列を返す.

解法

やるだけ.

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

続きを読む

SRM475 DIV1 HARD - RabbitProgramming (この記事を編集する[管理者用])

Source

TopCoder SRM475 DIV1 HARD (900pt)
Problem Statement

問題概要

コンテストの問題の配点と,各問題がシステムテストが終わったかどうかの情報が与えられる.
 システムテストが終わった問題に関しては,正解者のリスト,
 システムテストが終わってない問題に関しては,提出者のリスト(正解かどうか不明)
が与えられる.
参加者中,上位n人の中から,m人選んでチームをつくる場合,作れる可能性のあるチームの数をmod いくらかで求める問題.
問題数は50以下,参加者数は50以下,各問題の点数は100000以下.
同点の場合は,番号の若い参加者の方が順位が高いとみなす.

解法

m人が選ばれたとした場合,そのm人は不確定だった問題は全て正答していて,その他の人は不確定だった問題に全て間違えたと仮定する.
その時,それぞれのウサギに着目して,そのウサギは,m人の中で最下位になるようなm人の選び方が何通りあるかを考える.
それは,着目したウサギよりも,常に順位が上になるウサギがa人いて,順位が上に慣れるウサギがb人いたら,そのa+b人の中から,m-1匹選べば良い.
ただし,着目したウサギは,順位がmより下になることはできないので,bから選べる人数は限りがあることに注意して,コンビネーションの数を足していく.

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

続きを読む

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

Source

TopCoder SRM475 DIV1 MEDIUM (600pt)
Problem Statement
SRM475 DIV1 自分の参加記録

問題概要

ウサギのカップルは,生まれて2年目から,1つのカップルを生成し続ける.
k (kは10000000以下) 年目のうさぎのカップルの数を mod 1000000009 で求める問題.
ただし,50個以下の年が与えられて,その時に,カップルの数を半分どこかに移動させて居なくなる.
半分というのは,古いウサギから優先的に選ばれて,奇数なら,切り上げで移動させるカップルの方が多い.

解法

1年目に半減させる場合は,コーナーケースで即座に0を返す.
そうでなければ,半減させるときに,いなくなるウサギは,全部2年以上生きてるウサギ.
1年目以外は,常に,2年以上生きてるウサギの方が1年生きてるウサギよりも多いことが簡単に分かるため.
kはそんなに大きくないので,1年ずつループを回して,漸化式立ててmod 1000000009で計算して問題ない.
ただし,半減させるときに,n/2だけ減らすのか,(n+1)/2を減らすのかというのは重要.
例えば,mod 1000000009の他に,mod 2で計算した結果も保持しておくと,最初はどっちなのかわかる.が2回目以降分からなくなる.
よって,mod 1000000009の他に,mod 2^50で計算した結果も保持しておく.
また,k回ループを回すのが強ければ,行列べき乗に落とせば良い.
mod 2^50は,かけ算すると,オーバーフローするが,unsigned long longで計算しておけば,mod 2^64は保存されるのでオーバーフローしても問題ない.

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

続きを読む

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

Source

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

問題概要

最初,17マス以下のセルが直線上にある.
ランダムにウサギが,r匹いる.
端のウサギは真ん中よりに,W色のセルにいるウサギは右へ,B色のセルにいるウサギは左へ,R色のセルにいるウサギは前いたセルに戻る(最初だったら左へ行く).
同じマスに2匹の兎が集まると居なくなる.
毎ターン,右端のマス目が消える.
残り2マスになったとき,うさぎの残りの数の期待値を求める問題.
細かい条件は問題文参照.

解法

初期パターンを全部列挙して,全部シミュレーションすれば良い.
実は,シミュレーションしなくても,偶奇に着目すれば解ける.
初期値で,偶数番目のセルにいるウサギの集合と,奇数番目のセルのいるウサギの集合に分割して考えると,
それぞれ衝突せず,衝突するときは必ず2匹が衝突して消え,最終的に辿りつける可能性のあるセルは,それぞれ1個なので,
それぞれ,奇数だけのうさぎがいると,それぞれ最後に1匹生き残る.

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

続きを読む

Beta Round #23 C問題 - Oranges and Apples (この記事を編集する[管理者用])

Source

Codeforces Beta Round #23 C問題
Problem description

問題概要

2N-1個の箱に,オレンジとリンゴがそれぞれ10^9以下だけ入っている.箱ごとに入ってる数は違う.
そこからN個の箱を選んで,オレンジもリンゴも総数の半分以上が含まれているようにしたい.
そのような選び方を1個求める問題.存在しないならそれを指摘する.
Nは100000以下.

解法

まず,存在しないケースはない.
最初にオレンジの数でソートしておいて,
 o[1] <= o[2] <=… <= o[2N-1]
を満たすようにしておく.
すると,
 1番目の箱,3番目の箱,…,2N-3番目の箱,2N-1番目の箱
 2番目の箱,4番目の箱,…,2N-2番目の箱,2N-1番目の箱
という両方の選び方において,オレンジの数は半分より多いことが示せる.
また,どちらかの選び方においては,リンゴも半分より多いはずで,それを出力すれば良い.

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

続きを読む

Appendix

Recent Articles

ブログ内検索

Ads


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