Entries

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

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

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

2010年08月27日10時02分から.

Assignment

Petr先生と,日本人2名(?)ぐらいと同じ部屋.
点数が250-450-1100の変則セットで怖い.

EASY

50個以下のwebサイトのアドレスと含まれてる単語のリストが与えられる.
また,NGワードのリストが与えられる.
与えられた閾値の数より以上の数のNGワードを含まれてるwebサイトは危険サイトとして,また危険サイトに含まれてる単語はすべてNGリストに追加される.
危険なwebサイトのリストを求める問題.

引数多い!文字列!めんどそう….
問題読む.
えっと,与えられたリスト順か…,ちょっと読みにくい.
書くだけ.文字列めんどー.
がりがり.
がりがり.
書いた.通った.取り敢えず提出.
コードとサンプル眺める.
うーん,これ,サンプルあんまり親切じゃないぞ?
ちゃんと,書けてるよな…,一通りチェックして次に行く.

MEDIUM

50個以下のクライアントと50個以下のサーバをノードとした,閉路のない有向グラフが与えられる.
いくつかの枝にセキュリティウェアをインストールしたい.
クライアントからサーバにパスがある組み全部に対して,セキュリティウェアをインストールしたノードを通るパスが最低1個は存在するようにしたい.
インストールする数の最小値を求める問題.

問題見る前にグラフが書いてある,うげー.なんか最大流っぽい?
ふむふむ,パスとは同じノードを通ってはいけないものだけを言うのか.(ではなくて,グラフが閉路無いというのを読み間違えた)
問題読んだ.
最小カットかと一瞬思ったけど,違うなー.最大流じゃないっぽい.
うーん….
枝は,クライアントとサーバとが繋がってる枝以外にもインストールできるのかな…,問題確認.できそう.
でも,クライアント間にセキュリティいれるの意味なさそうな気もする.
だって,クライアント間を結んでも,その先の人が行ける場所には,セキュリティインストールした枝を通ってすべての場所に行けるはずだから,意味ない.
ってことは….
クライアントの中で,一番深いクライアントから順番にサーバにつながっている枝にインストールしていくだけ.
じゃない,ループがあったらどうするのよ.
DAGだったら簡単なのになー,さすがにDIV1 MEDIUMでそれはないか… ←
でも,後はループを解決するだけ.
強連結成分分解してもいいが,面倒.
うーん,何やっても面倒な気がする.
ループに属するものは適当に繋げれば良い…,その適当が難しいんだってば.
うーん.
そのノードから辿りつけるノード数を調べてあげて,それが小さい方からインストールしていっても大丈夫じゃないか?
ちょっと怪しい.
証明できるかどうか考えよう.
んー.
できそうな気がしてきた.
これならまだ少し書くのが楽.
書く!
書いた.サンプル一致.提出.
コードが間違ってないか,一通り眺めて次の問題へ.

HARD

 1112213333 → 31221143
のように,ランレングスっぽく,「数字が続いた数+続いた数字」に置き換える関数F: 文字列→文字列 を考える.
500文字以下の文字列Xが与えられるのでF(F(Y))=XとなるYの数をmod 1000000009で求める問題.

うーん,時間も微妙だし,1100だから解ける気がしないけど一応考えてみる.
2回じゃなくて,1回だったら?
 F(Y)=XなるYの個数
うーんと….
何が何個か,ってのを解釈の仕方の数で終了.簡単なDP.
じゃあ,2回ならば….DPでいけそうな気もするけど.
2回分一気に考えるだけ.
….
いや,文字列の長さとか色々かけながら処理しないと駄目.
うーん….
いやいやいや,凄い面倒だ…,計算量は…,色々メモっておけば大丈夫そうな気はするけど…?
駄目.これは残り15分で解けるような問題じゃない.見直しする.
MEDIUMは…,あれ,問題読み直したら閉路がないって書いてあるぞ?orz
EASYは,returnのvectorの順番を間違えるかもしれないし,ループせずに増えたNGワードをさかのぼって適用しない人もいるかもしれない.
それでサンプル通るから.チャレンジケース作っておこう.

Intermission

Petr先生が450の撃墜準備をしてるように見える.
あれ,今日って落し所そっちなの?
でも,わからないので,EASYを狙う.

Challenge

取り敢えず,よしみってことで日本人から開いてみる.
これが当たったみたいで,vectorの中身の順番間違えてるっぽいので落とす×2.
後ループしてない人がいたので落とす.
+150点.美味しいです.

System tests

EASYとMEDIUM通る.
問題読み間違え多分はチャレンジで取り返せてお釣りが来た.
でも,普通にcoding phaseで点数を稼ぎたい….

Aizu 0153 - Triangle and Circle (この記事を編集する[管理者用])

Source

PC Koshien 2007 (パソコン甲子園2007)
Aizu 0153

問題概要

日本語の問題文があるので簡単に書く.
2次元平面上の三角形と円が与えられたとき,その関係が
 包含関係になっているか,共通部分を持つか,共通部分がないか
判定する問題.

解法

二次元幾何,頑張る.
接する場合は,面積0でも共通部分を持つことに注意.

Aizu 0109 - Smart Calculator (この記事を編集する[管理者用])

Source

PC Koshien 2005 (パソコン甲子園2005)
Aizu 0109

問題概要

日本語の問題文があるので簡単に書く.
数字と四則演算とカッコからなる数式が与えられるので,評価する問題.割り算は整数の割り算.
文字数は100文字以下.

解法

書くだけ.オーバーフローするかと思ったらしなかった.

SPOJ 4672 - Yanu in Movie theatre [FUNPROB] (この記事を編集する[管理者用])

Source

SPOJ 4672 [FUNPROB]

問題概要

N人(タイプX)とM人(タイプY)がランダムに1列に並ぶ.
全てのkに対して,最初からk人取ってきたとき,タイプYの人の数がタイプXの人以上の数になっていなければいけない.
そのようになっている確率を求める問題.

解法

解析的に求まる.
カタラン数の全単射を用いた証明で,C(2n,n) - C(2n,n+1)になることを示せる方を考えて拡張すれば,答えが計算しやすい.

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

Source

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

問題概要

N人(タイプX)とM人(タイプY)がランダムに1列に並ぶ.
全てのkに対して,最初からk人取ってきたとき,
 タイプYの人の数 が タイプXの人+k 以上の数
になっていなければいけない.
そのようになっている確率を求める問題.

解法

解析的に求める.計算量はO(k)ぐらいになる.
カタラン数の全単射を用いた証明で,C(2n,n) - C(2n,n+1)になることを示せる方を考えて拡張すれば,答えが計算しやすい.

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

続きを読む

Beta Round #26 E問題 - Multithreading (この記事を編集する[管理者用])

Source

Codeforces Beta Round #26 E問題
Problem description
Beta Round #26の自分の参加記録

問題概要

N個のプロセスがあって,プロセスiがn[i]回
 y[i] := y
 y := y[i]+1
という操作を行う.メモリは共通.
最初yの値が0で最終的にWになる方法を1つ求める問題.
方法とは,全部のプロセスは1行ずつ実行する(その間は他のプロセスは邪魔しない)として,実行順番のこと.
Nは100以下,n[i]は1000以下.

解法

adhoc.
n=1のときは,n[1]しか作れない.
n[k]=1なるkが存在したら1を作れる.そうでなければ作れる範囲は2~∑n[k]まで.
作り方のやり方は色々あるとおもう.

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

続きを読む

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

Source

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

問題概要

n*mの箱に,1*2のピースと,2*1のピースと,2*2のピースを使って敷き詰める.
それぞれのピースの使える数が与えられたとき,敷き詰め方を1つ求める問題.
不可能ならそれを指摘する.
n,mは100以下.

解法

2行ごと,2列ごとに線を引いて,2*2のマス目に分けて,余った1*2,2*1の部分を最初に詰める.
後は,2*2のマスごとに,詰めていく.

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

続きを読む

Beta Round #26 B問題 - Regular Bracket Sequence (この記事を編集する[管理者用])

Source

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

問題概要

()からなる1000000文字以下の文字列が与えられる.
その部分列(部分文字列じゃない)でカッコがちゃんと対応付けられていて,最も長いものの長さを求める問題.

解法

左から眺めていって,(が現れた数を覚えて,)が出てきた時,(が余ってるなら一番右のとgreedyに対応させたことにして,(の現れた数を1減らす.

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

続きを読む

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

Source

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

問題概要

Almost Primeとは,素数の約数の数が厳密に2個のもの.
1~NまでにAlmost Primeが何個あるか求める問題.
Nは3000以下.

解法

実際に1~NまでのそれぞれがAlmost Primeかどうかを愚直に判定する.

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

続きを読む

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

Source

TopCoder SRM479 DIV1 MEDIUM (500pt)
Problem Statement
SRM479 DIV1 自分の参加記録

問題概要

飛行機のスケジュールが与えられる.
目的地に時間T以下で辿りつけるルートのうち,乗り換え時間(到着から出発までの時間の差)の最小値を最大化したとき,最大値を求める問題.
ノード数は477以下,飛行機は,各路線ごとに,
 始点ノード,終点ノード,最初に飛び立つ時間,飛び立つ周期(無限にたくさんの飛行機が飛び立つ),所要時間
が与えられる.
辿り着けない,最大値が1以上にならないなら,それを指摘する.
時間は10億まで,直通便はないことが保証されている.

解法

答えに対して,2分探索する.
答えがk以上にできる のと 到着した後,時間kだけ乗れない状態で,時間T以内に目的地に着く のは同値.
後は,ダイクストラなり何なりで,最短路を求める問題になる.

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

続きを読む

SRM479 DIV1 EASY - TheCoffeeTimeDivOne (この記事を編集する[管理者用])

Source

TopCoder SRM479 DIV1 EASY (250pt)
Problem Statement
SRM479 DIV1 自分の参加記録

問題概要

飛行機.n人が1列に座っていて,コーヒーかお茶を配るのにかかる時間の最小値を求める問題.
47人以下にお茶を淹れて,その人の座標が与えられる.それ以外はコーヒー.
お茶かコーヒーのどちらか片方のみ,7個以下をトレーにのせることができる.
汲む場所は最初の席の前にあり,1マス移動するのに1秒,支給するのに4秒,汲むのに47秒かかる.
nは44777777以下.

解法

後ろから順番に配っていくのが最適.
O(n)でも間に合うので,実際に後ろから眺めていって,7人に達するか,一番前まで来たグループに分けて配る時間を足していく.

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

続きを読む

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

Source

TopCoder SRM478 DIV1 MEDIUM (500pt)
Problem Statement
SRM478 DIV1 自分の参加記録

問題概要

容量CのN個のビンに,それぞれ整数量のいくらかKiwiさんジュースが入っている.
あるビンの中身をあるビンに,空になるかあふれるギリギリまで注ぐことが何回でもできる.
また,0以上C以下の整数に対して,それだけKiwiさんジュースが入っているビンを売り払ったときに得られるお金の量も与えられる.
最大の収益を求める問題.
Cは49以下,Nは15以下.

解法

いくつかの集合に分けて,それぞれの集合ごとに1つに纏める(0のボトルとCのボトルとそれ以外のボトルが1つ)全てのパターンを考えれば良い.
ので,ビットDPする.
以下のコードはO(n*n^3)だが,集合の列挙を上手くやるとO(n^3)にできる.

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

続きを読む

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

Source

TopCoder SRM478 DIV1 EASY (250pt)
TopCoder SRM478 DIV2 MEDIUM (500pt)
Problem Statement
SRM478 DIV1 自分の参加記録

問題概要

ウサギが座標xに居るとき,時間1後に4x+3か8x+7に移動できる.
1000000007の倍数の座標に移動するまでの最短時間を求める問題.
ただし,時間100000以下で辿り着けなければ,求めなくてよくて,それを指摘する.

解法

mod 1000000007の世界で考えれば良い.
f(x) = 2x+1とすると,f^2(x) = 4x+3, f^3(x) = 8x+7なので,
初期値からfを何回かますと0になるかを調べれば良くて,後はgreedyに8x+7から使っていく.
実際には,BFSしても,状態数が増えないことがわかるので,普通にBFSしても良い.

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

続きを読む

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

Source

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

問題概要

50ノード以下の無向グラフが与えられる.
それぞれのノードで燃料1あたりいくらで買えるかも与えられる.
ノード0からノード1に辿りつくまでの最小コストを求める問題.
燃料タンクの上限値は1000000.

解法

残り燃料の量でノードを拡大してダイクストラする.
ただし,残り燃料を1刻みで燃料タンクの上限値まで考えるとノード数が50*1000000になって間に合わない.
残り燃料は,0,燃料タンク満タンと,他のノードまでの最短距離だけ考えれば十分なので,これならノード数が50*51になる.

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

続きを読む

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

2010年08月17日00時から2時間,5問.
[ Link ]

Codeforces formatについて

今回からCodeforcesオリジナルの新ルール.
TopCoderと同じように得点方式となり,コンテスト開始時から1分おきに,各問題の点数が減っていく.
また,提出したときは簡易テストしか行われず,精密なシステムテストはコンテスト終了後に行われる.
提出して,簡易テスト通過したコードはロックすることができ,ロックすると再提出ができなくなる.
(再提出の場合は,TopCoderと同じように5%の減点があり,問題ごとの最低点も決められている)
ロックした問題については,(コンテスト中に)他人のコードを見ることができるようになり,撃墜することができるようになる.
撃墜に成功したら100点,失敗したら-50点.

A. Almost Prime

Almost Primeとは,素数の約数の数が厳密に2個のもの.
1~NまでにAlmost Primeが何個あるか求める問題.
Nは3000以下.

C問題からやろうとして,問題だけ読んだけど,嫌な感じだったので普通にA問題からやる.
1個1個判定しても十分間に合うサイズ.
なので,そうする.
サブミット.簡易テスト通過.

B. Regular Bracket Sequence

()からなる1000000文字以下の文字列が与えられる.
その部分列(部分文字列じゃない)でカッコがちゃんと対応付けられていて,最も長いものの長さを求める問題.

あれ,これ,同じ問題が昔なかったか?
あるような,コピペサブミット.WA.
あ,昔のは,部分文字列で,今回は部分列なのか.
だったら簡単じゃないの?
左から眺めていて,(の出てきた数を数えて,)が出てきたらgreedyに対応させる.
サブミット.簡易テスト通過.

C. Parquet

n*mの箱に,1*2のピースと,2*1のピースと,2*2のピースを使って敷き詰める.
それぞれのピースの使える数が与えられたとき,敷き詰め方を1つ求める問題.
不可能ならそれを指摘する.
n,mは100以下.

端から,置けるのをでっかいのからgreedyにおいていけばいいのでは?
いや,中途半端に余った部分をちゃんと処理できなくなる可能性がある.
n,mが奇数なら中途半端に残るので,そこから処理してあげたらいいのでは….
良さそう.書く.意外と面倒.
これはコーナーケースが怖そう.
いくらか自前でテストする.
良さそう.サブミット.簡易テスト通過.

D. Tickets

+の玉n個と-の玉がm個が箱に入っている.
初期値はkで,玉を1個ずつ引いていって,+を引いたら1足す,-を引いたら1引く.
最後までマイナスにならない確率を求める問題.
n,mは100000以下,kは10以下.

解析的に求まる気もするし,そうじゃない気もする.
妙に値が小さいので解析的に求まるんじゃないのではないか….
適当に,現在の値が200を超えるとか,沢山になったらもうマイナスにならないと仮定して状態数減らしてDPすればいいのではないか.
要求精度も高くないし.
書く.
大きなテストケースを適当に入れてみる.あんまり値がブレない.いけるんじゃない?
サブミット.簡易テスト通過.

A, B, Cはロックする.
で,他の人のコードを眺める.
BでO(n^2)の人がいたので,落とそう.
撃墜方法がわからない.長さ1000000の文字列を上手く貼り付けてない疑惑.
その文字列を生成するコードでもいいらしいので,コードを提出.落とせた.

E. Multithreading

N個のプロセスがあって,プロセスiがn[i]回
 y[i] := y
 y := y[i]+1
という操作を行う.メモリは共通.
最初yの値が0で最終的にWになる方法を1つ求める問題.
方法とは,全部のプロセスは1行ずつ実行する(その間は他のプロセスは邪魔しない)として,実行順番のこと.

うーん.
n=1はコーナーケース.別処理するべき.
Wがn[i]の中で一番小さいの以上は作れそう.
最初にiを使って,いくつか無駄に使って,iを使って,後は順番に使う.
それ未満には出来ない?
いや,できる.
2段階無駄なのを処理させると,2にできそう.
そして,そもそもn[i]=1のものがあれば,それを使うことで1にできる.
後はadhocに処理を書くだけ.
意外と面倒.
書いた.サブミット.簡易テスト通過.

DとEをロックする.
Dは他の人のコード見ると解析的に求まってるなぁ….
Eのコード読み間違えて,1回ハック失敗.

Result

DがWAで落ちて,他は通った.

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

2010年08月15日01時02分から.

Assignment

参加記録 の形式をぱくった を書き始めるきっかけになったと同じ部屋.
MEDIUMからやってみる.

MEDIUM

飛行機のスケジュールが与えられる.
目的地に時間T以下で辿りつけるルートのうち,乗り換え時間(到着から出発までの時間の差)の最小値を最大化したとき,最大値を求める問題.
ノード数は477以下,飛行機は,各路線ごとに,
 始点ノード,終点ノード,最初に飛び立つ時間,飛び立つ周期(無限にたくさんの飛行機が飛び立つ),所要時間
が与えられる.
辿り着けない,最大値が1以上にならないなら,それを指摘する.
時間は10億まで,直通便はないことが保証されている.

問題文が長いー.頑張って読んだ.
どうみても,2分探索+ダイクストラ.
書くだけだ.がりがりがり.
実行.
答えが全部2分探索の設定の最大値になった….
無限ループに陥った.
答えが全然合わない.
あれ….
挙句の果てには,2分探索すら間違えてる.
頑張って修正.
答えあったのでサブミット.

EASY

飛行機.n人が1列に座っていて,コーヒーかお茶を配るのにかかる時間の最小値を求める問題.
47人以下にお茶を淹れて,その人の座標が与えられる.それ以外はコーヒー.
お茶かコーヒーのどちらか片方のみ,7個以下をトレーにのせることができる.
汲む場所は最初の席の前にあり,1マス移動するのに1秒,支給するのに4秒,汲むのに47秒かかる.
nは44777777以下.

サマリー見ると苦戦してる人が多い.
そして,問題文が長い…,うげー.
えっと,どうするのだ….
44777777以下って,1人ずつ配るのをループしても間に合うな.
勝った.
最小化って,あんまり行ったり来たりしなければ良いので,前から適当に配ればいいだろう.
書く.
書いた.
あれ,答え合ってない….
あ!
前からじゃなくて,後ろからじゃないとダメだよね?
そうだそうだ….
書き直す.
サンプルあった.
提出.
あれ,結構時間たってる….

HARD

2*nマスが一列に並んでいる.
左側のnマスにそれぞれ1人ずつ人がいる.
右側のnマスに椅子が1個ずつある.
適当に皆,1秒に1マスだけ右に移動していって,自分の椅子の前に来ると,74秒まって座る.
その間,その人を追い越すことは出来ない.
最初xにいる人が,y番目の椅子に座るという制約がいくつか与えられたとき,時間T以下で皆が座るような,目的地の組の数を求める問題.
nは18以下,Tは222以下.

終始問題の意味がわからなかった.
まぁ,難しいっぽかったし,時間もあんまりなかったし,EASYとMEDIUMを見直す.

Challenge

のんびり眺めてるだけ.

System tests

EASYとMEDIUM通る.
両方共,致命的に遅かったと思うのだけど,そんなに順位的には悪くなかったみたい.

Aizu 2214 - Warp Hall (ワープホール) (この記事を編集する[管理者用])

Source

UTPC 2010 (東京大学プログラミングコンテスト2010)
Aizu 2214

問題概要

日本語の問題文があるので簡単に書く.
(1,1)から(N,M)まで,1歩ずつ右または上に進むことでたどり着くパターンの数をmod 1000000007で求める問題.
ただし,1000ヶ所以下,ワープホールがあって,そこに辿りつくと,強制的に,そこより左上にある出口に飛ばされる.

解法

コンビネーションの計算+包除原理っぽくDPする.
各ワープゾーンの入り口までの経路の数をメモする.

Aizu 2212 - Stolen Jewel (盗まれた宝石) (この記事を編集する[管理者用])

Source

UTPC 2010 (東京大学プログラミングコンテスト2010)
Aizu 2212

問題概要

日本語の問題文があるので簡単に書く.
50*50以下のグリッドで迷路が与えられる.
スタートからゴールまでたどり着く最小ステップ数を求める問題.
ただし,10個以下の長さ10以下のパターンが与えられて,そのパターンを含むような移動はできない.

解法

今何処にいるか,どのパターンにどこまで一致しているかを状態としてBFSする.

Aizu 2211 - Stray Cats, Run... (迷い猫、走った) (この記事を編集する[管理者用])

Source

UTPC 2010 (東京大学プログラミングコンテスト2010)
Aizu 2211

問題概要

日本語の問題文があるので簡単に書く.
1次元の世界で猫は一番近い餌に移動する.
餌置き場がいくつか与えられて,餌を置くおかないを選択して,もっとも多くの猫が集まる餌置き場の猫の数の最小値を求める問題.

解法

2分探索+DP.
DPは,ある餌置き場より右だけ考えて,一番左の餌置き場に来る猫の数の最小値をメモしておく.

Aizu 2210 - Star Watching (天体観測) (この記事を編集する[管理者用])

Source

UTPC 2010 (東京大学プログラミングコンテスト2010)
Aizu 2210

問題概要

日本語の問題文があるので略.

解法

まず日付と時間から適当にどれだけ回転してるかを求める.
後は,北極星がxy平面とかに来るように回転してから,別の軸で回転して,また北極星を元の位置に戻すように回転して,すべての星のz座標が正かどうか調べる.

Aizu 2209 - UTF-8 (この記事を編集する[管理者用])

Source

UTPC 2010 (東京大学プログラミングコンテスト2010)
Aizu 2209

問題概要

日本語の問題文があるので簡単に書く.
1000バイト以下のビット列で,いくつかは0か1か定まっていない.
それをUFT-8の文章として解釈する方法は何通りあるかをmod 1000000で求める問題.

解法

Xバイト目以降から復元できる文字列の数をdp[X]としてDPする.

Aizu 2208 - The Melancholy of Thomas Right (トーマス・ライトの憂鬱) (この記事を編集する[管理者用])

Source

UTPC 2010 (東京大学プログラミングコンテスト2010)
Aizu 2208

問題概要

日本語の問題文があるので簡単に書く.
縦横Nマスの盤面の各マスにたかだか1個のビー玉が置いてある. 各行のビー玉の数,各列のビー玉の数が与えられたとき,盤面が一意に復元できるかどうかを求める問題.

解法

greedyにビー玉がない,全部ビー玉を置かないと駄目な行とか列に着目しておいていく.
それで全部決まらなければ一意に定まらない.

Aizu 2207 - Consistet Unit System (無矛盾な単位系) (この記事を編集する[管理者用])

Source

UTPC 2010 (東京大学プログラミングコンテスト2010)
Aizu 2207

問題概要

日本語の問題文があるので簡単に書く.
単位系の等式が与えられたとき,矛盾があるかどうかを調べる問題.

解法

指数を枝の重みとしたグラフを考えて,長さが0でない閉路が存在したら矛盾する.
ワーシャルフロイドなどで長さが負の閉路が存在するかどうか判定すれば良い.

Aizu 2206 - Compile (コンパイル) (この記事を編集する[管理者用])

Source

UTPC 2010 (東京大学プログラミングコンテスト2010)
Aizu 2206

問題概要

日本語の問題文があるので簡単に書く.
ぷよぷよの盤面が与えられるので,そこから何連鎖するか求める問題.

解法

やるだけ.
DFSして連結成分のサイズが4以上なら消していくという作業を繰り返す.

Aizu 2205 - Lottery Checker (宝くじチェッカー) (この記事を編集する[管理者用])

Source

UTPC 2010 (東京大学プログラミングコンテスト2010)
Aizu 2205

問題概要

日本語の問題文があるので簡単に書く.
宝くじの当選番号(ときどき任意の数字が入って良い場所がある)と当選金額,自分の持ってる宝くじの番号が与えられるので,合計当選金額を求める問題.

解法

やるだけ.

Aizu 2204 - Final Examination! (期末試験!) (この記事を編集する[管理者用])

Source

UTPC 2010 (東京大学プログラミングコンテスト2010)
Aizu 2204

問題概要

日本語の問題文があるので簡単に書く.
5科目のテスト結果が何回分か与えられるので,最高合計点数と最低合計点数を求める問題.

解法

やるだけ.

Aizu 2201 - Immortal Jewels (この記事を編集する[管理者用])

Source

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

問題概要

日本語の問題文があるので簡単に書く.
2次元平面上のN個の円とそれぞれの磁力の強さが与えられる.
直線を1本引いて,円と離れていて,円との距離が磁力以下になる円の数を最大化したい.
最大値を求める問題.

解法

円が1つの時は答えは1.
2つの円を選んでその共通接線を全部調べる.

Aizu 0548 - Reindeer with no sense of direction (方向音痴のトナカイ) (この記事を編集する[管理者用])

Source

第9回日本情報オリンピック 予選1 (2009年12月13日)
Aizu 0548

問題概要

日本語の問題文があるので簡単に書く.
10*10以下のマップの中に,1個の教会と23個以下の家がある.
教会からスタートして,全ての家を訪れて,教会に戻ってくるパターンの数を求める問題.
ただし,移動するときには,上下左右のどこかに向かって直線に移動することしか出来ない.
一度訪れた家の上は通ることが出来ない.
答えは2000000以下であることが保証されている.

解法

逆向きに考えると,最初に出会った家で曲がらないと駄目で,一度たどり着いた家を消していく感じになる.
逆向きに考えたほうが枝分かれが少なく探索が早く終る.

Aizu 0547 - Commute routes (通勤経路) (この記事を編集する[管理者用])

Source

第9回日本情報オリンピック 予選1 (2009年12月13日)
Aizu 0547

問題概要

日本語の問題文があるので簡単に書く.
100*100以下のグリッドの道路を左下から右上まで移動する経路のパターンの数を求める問題.
ただし,上か右にしか進むことはできず,曲がった次の交差点でまた曲がることは出来ない.

解法

DP.今何処にいるか,前回,前々回どっち向きに進んだかを状態とする.

Aizu 0546 - Lining up the cards (カード並べ) (この記事を編集する[管理者用])

Source

第9回日本情報オリンピック 予選1 (2009年12月13日)
Aizu 0546

問題概要

日本語の問題文があるので簡単に書く.
1から99までの数字が書かれたカードが10枚以下与えられる.
その中からちょうどk枚並べてできる数字のパターンの数を求める問題.
kは4以下.

解法

全部の並べ方を試して,実際に作ってみて,setなどに放り込んで,最後にサイズを返す.

Appendix

Recent Articles

ブログ内検索

Ads


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