Latest Entries
ICPC OB/OGの会 2009 夏合宿 3日目
Aizu 2168
勇者と戦士と僧侶と魔法使いがそれぞれ50人以下いる．
同じパーティー内の勇者と戦士，戦士と僧侶，僧侶と魔法使いはそれぞれ仲が良くないとダメ．
僧侶がいないパーティーは戦士と魔法使いはいなければいけない．
全てのパーティーに勇者はいなくてはいけない．
戦士のいないパーティー，僧侶のいないパーティー，魔法使いのいないパーティーはそれぞれ，N_W, N_C, N_M以下でなければならない．
仲が良い人のリストが与えられたとき，最大で何個のパーティーが作れるか求める問題．
まず，N_W人の戦士などを追加して考える．
追加した人は全て仲が良いが，追加した僧侶は，追加した戦士，魔法使いと仲が悪いとすれば良い．
後は，
(ソース) - 勇者 - 戦士 - 僧侶 - 魔法使い - (シンク)
といったグラフを作って最大流を流せば良い．
ICPC OB/OGの会 2009 夏合宿 3日目
Aizu 2166
毎晩深夜0時に寝る．
睡眠時間は決められていて，その周期T日．
ただし，カフェインを取ることによって，周期をリセットして，睡眠時間を調整できる．
与えられた，仕事を全部こなすために必要なカフェインの量の最小値を求める問題．
Tは30以下，仕事は100日先程度まで与えられている．
現在何日目か，現在の睡眠時間の周期を状態としたDP．
ICPC OB/OGの会 2009 夏合宿 3日目
Aizu 2165
最適な線形合同法のパラメータを求める問題．
入力数列に，順番に線形合同法で得られた疑似乱数を足しこんで(そしてmodをとって)いく．
そうして得られた数列に登場する数字たちのエントロピーを最小にしたい．
いじれる線形合同法のパラメータは3つで，それぞれ16通りの値しか取れない．
数列の長さは256以下．
複数答えが存在する場合，辞書順最小のパラメータを答える．
実際に全部試してみて，エントロピーを計算する．
ICPC OB/OGの会 2009 夏合宿 2日目
Aizu 2164
2つのグループのどちらかに属するn人の人が円形のテーブルに座る．
それぞれのグループの人が何人ずついるかは不明．
同じグループの人がk人より多く連続して座ってはいけない．
何通りの座り方があるかをmod 1000003で求める問題．
回転して同じに見えるのは1つと数える．
nとkは1000以下．
まず，DPで回転して同じように見えるものも全部重複して計算する．
後は包除原理っぽく計算できる．
DPは，愚直に書くとO(n^3)でTLEになるけど，ちょっと工夫すればO(n^2)で書ける．
包除原理っぽいのをするときは，n人全員が同じグループの場合は除外して考えると良いかも．
後は，1000003が素数なので，割り算できることに注意．
ICPC OB/OGの会 2009 夏合宿 2日目
Aizu 2163
20*20以下のマップを1*2のタイルで敷き詰める方法の数を求める問題．
ただし，タイルの外周が交わってはいけない．
つまり，任意の2*2の正方形は3個以下のタイルしか含まれてはいけない．
制約が厳しいので全探索で間に合う．
実際，答えはとても小さい．
ICPC OB/OGの会 2009 夏合宿 2日目
Aizu 2161
N人の人の現在位置とスピード，M個の施設の位置が与えられる．
M個の施設全部に最低1人以上到着するための必要最小時間を求める問題．
NとMは100以下．
2分探索 + 最大流．
それぞれの人がそれぞれの施設に辿り着くのに必要な時間を求めておく．答えはその中にある．
ICPC OB/OGの会 2009 夏合宿 2日目
Aizu 2160
凸多角形と，M個の城の座標が与えられる．
凸多角形内の点は，一番近い城の領域となる．
それぞれの城が支配する面積を求める問題．
多角形の頂点数Nは10以下，Mも10以下．
2次元幾何．
M個独立に求める．
自分以外の城との垂直二等分線を求めて，凸多角形をカットして，面積を求めるだけ．
ICPC OB/OGの会 2009 夏合宿 2日目
Aizu 2157
ダイヤルの初期値と，目標値が与えられたとき，最小手数を求める問題．
隣接する幾つかの桁は一度に同じだけ回すことができる．
10桁まで．
最初の桁から揃えていく．
桁を揃えるとき，どれだけ一緒に回すかで全探索する．
大体O(桁数!*桁数)．
ICPC OB/OGの会 2009 夏合宿 2日目
Aizu 2156
N匹のモンスターのHPが与えられる．
魔法がM種類あって，単体魔法か全体魔法か，消費MPと与えるダメージが与えられる．
モンスターを全滅させるのに必要な最小MPを求める問題．
NとMは100以下．HPは100000以下．
単体魔法，全体魔法で，それぞれ，あるダメージ以上を与える最小MPをDPで最初に計算する．
後は，全体魔法でいくらのダメージを与えて，残りのモンスターを倒すか，全探索して，必要最小MPを求める．
O(N+M+HPの最大値)ぐらい．
ICPC OB/OGの会 2009 夏合宿 2日目
Aizu 2155
最初0番のPCのみウイルスに感染している．
感染してるPCからメールを送られたPCは感染する．
メールのやり取りが，行われた時間，誰から誰にメールが送られたか，という情報が与えられるので，最終的にウイルスに感染してるPCの数を求める問題．
時間でソートして，最初からシミュレーションするだけ．
パソコン甲子園2009 Warm-Up (2009-08-22)
Aizu 1050
問題文が日本語なので省略．
ボロノイ図を書いて，その辺上を移動できるとしてダイクストラする．
点の数がとても小さいので，愚直に，非効率的なアルゴリズムでも良い．
Advancement Autumn 2009
SPOJ 5196 [MONONUM]
n桁の正整数で，
各桁の数が非増加なものの数 / 各桁の数が非減少なものの数
を求める問題．
5544320は非増加，12788は非減少，7は非増加かつ非減少，0とか027は許されない．
nは1000000以下．
10*1000000ぐらいの状態数かつ計算量のDPで求めて割るだけ．
10は数字の種類，1000000はnの最大値．
Advancement Autumn 2009
SPOJ 5161 [FACVSPOW]
2以上1000000以下の自然数aが与えられたとき，
n! > a^n
となる最小のnを求める問題．
答えは高々3000000ぐらい．
なので，それぐらいまで，最初にlog(n!)を全部計算しておいて，2分探索する．
15色以下のペンキがそれぞれ5個以下ずつあって，ブロックがちょうどペンキを使いきるだけある．
ブロックを一色線に並べて，隣り合うブロックは違う色でぬる時，塗り方は何通りあるか，mod 1000000007で求める問題．
何個ブロックを塗れるペンキが何色残っているか，15^6程度の状態数のDP．
University of Ulm Local Contest 2008
SPOJ 2852 [BROKEN]
1000000文字以下の文字列が与えられるので，高々m個の異なる文字しか含まない区間の最長の長さを求める問題．
尺取りメソッド．
2009年11月05日21時から．
これは酷い…．
ターゲット3人とか．
今日こそは500通すんだ，と意気込む．
ちょっと悩む．
きっとグリーディーで良さそうな気がする．
サブミット．
ちゃんと考える．やっぱり良さそう．次．
うーん…．
IOIにならないのが少ない気がするから，そっちを数えれば良さそうだ．
全探索でいけるんじゃね？
書いてみた．
無理でした．
取り敢えず，IOIにならないパターンを全部出力してみる．
OOOOO*OOOOO
ただし，*はIOOIOOIOOIみたいに，IとIの間に同じ数だけ，そして偶数個だけOが入ってるパターン
これだけしかないっぽい．
適当に書く．始まる場所，終わる場所，間隔，あとはなぞってO(長さ^4)．TLEだよねぇ…．
混乱中．
取り敢えず，見てみる．
うん，わからん…．誰も解いてないし難しいに違いない．
Iの数が0個の場合と1個の場合，2個以上の場合で場合分けして，適当に組み合わせの数とか計算して高速化．
間に合うようになった．
提出．
mod取るの忘れてた，再提出．
途中で，自分のMEDIUMが，Iの個数が0個のとき，OまでもIに置き換えれるようになってることに気づいた…．
頭の中では全部?だった…．今日も通らずか．
とか思ってたらChallengeされた．
後はかわいそうなミスを1個つついたりして，1成功1失敗．
EASYは普通に通る．まぁ，今日のシステムテストは平和な感じ．
しかし，チャレンジ含めて，250って結構落としてる人いるなー…．
良く考えれば，自分のMEDIUM，Iの数が1個の場合の式違う．てか，Iの数が1個と2個以上とか分ける必要ないじゃん…．頭悪い．
そして，Challengeで人の解答見て，普通にループ回すだけでも，ちゃんと考えて回せば普通に解けることに気づく．
次回こそは500を通せるように頑張ろう…．てかいい加減なんとかしないとまずい…．
しかし，毎度のことながらTopCoderは解けるはずなのに解けない問題出してくるなぁ…．楽しい．
Rateは微増…．
writterはrng_58さんだったのかー．流石面白い問題作ってくれる．
ACM/ICPC Asia - Wuhan - 2009/2010
Wuhan Regional Semilive (2009-11-02) (blog)
LiveArchive 4492
2本の線分が与えられる．
ある点から，角度90度で2つのレーザービームを発したところ，それぞれのビームがそれぞれの線に当たった．
そのようなことがあり得る点の集合の面積を求める問題．
別の線分の端点を直径とする4つの円を考える．
答えるべき面積は，
どれかの円に覆われている部分の面積 - 全ての円に覆われている部分の面積．
SPOJ 3863と包除原理を用いて計算する．
ACM/ICPC Asia - Wuhan - 2009/2010
Wuhan Regional Semilive (2009-11-02) (blog)
LiveArchive 4490
本棚に高さ25〜32までの本が100個以下並んでいる．
k個まで取り出して，入れなおすことができる．
隣り合う部分で，高さが違う場所の数を，最小化する問題．最小値のみを答える．
今見てる本の場所，自分の1つ左の本，自分の左にはどの高さの本が存在しているか，現在何個本を取り出したか，などを状態としたDP．
状態数は，最大で101*8*2^8*101ぐらい．
ACM/ICPC Asia - Wuhan - 2009/2010
Wuhan Regional Semilive (2009-11-02) (blog)
LiveArchive 4489
2つのクーポンが与えられる．それぞれ50以下，500以下の価格．
それぞれのクーポンは合計金額がそのクーポンの額以下となる場合に使用可能．
また，1つだけ，無料で商品をもらえる．
商品にそれぞれスコアがあって，また絶対手に入れないといけない商品も幾つか存在する．
買える商品のスコアの最大値を求める問題．
絶対買わないとダメな商品をそろえられないならそれを指摘する．
DPするだけ．
ACM/ICPC Asia - Wuhan - 2009/2010
Wuhan Regional Semilive (2009-11-02) (blog)
LiveArchive 4487
20000個以下の2^20の非負整数がある．
以下のクエリを答える問題．クエリの数は40000個以下．
ある数字が何かという情報を手に入れる．
ある2つの数字のXORが何かという情報を手に入れる
15個以下の数字のXORを求める
途中で矛盾するならそれを指摘する．
超絶実装．
まず，ビットごとに独立に考えれば良い．
2つの数字のXORが与えられたとき，1なら別のグループに属す，0なら同じグループに属す，などとやってグループ分けしていく．
ACM/ICPC Asia - Wuhan - 2009/2010
Wuhan Regional Semilive (2009-11-02) (blog)
LiveArchive 4486
ある規則でダウンロードする．
全部のファイルがダウンロード終了するまでの時間を求める問題．
結局規則は関係なくて，ファイル容量合計/転送スピード．
ACM/ICPC Asia - Wuhan - 2009/2010
Wuhan Regional Semilive (2009-11-02) (blog)
LiveArchive 4485
ある地点からある地点に辿り着く時間の期待値を求める問題．
歩くスピードは1で，間に川があって，その川にはボートが行ったり来たりしている．
川の幅と，ボートのスピードは与えられる．
川を渡るのに必要な時間の期待値は 川の幅/ボートのスピード の2倍．
後は計算するだけ．
ACM/ICPC Asia - Wuhan - 2009/2010
Wuhan Regional Semilive (2009-11-02) (blog)
LiveArchive 4484
3次元上に1000個以下の直方体が，x軸y軸z軸に平行に置かれている．
直方体同士の関係が以下の形式で100000個以下与えられる．
直方体AとBは交わっている
直方体Aは直方体Bよりx座標が小さいところにある
直方体Aは直方体Bよりy座標が小さいところにある
直方体Aは直方体Bよりz座標が小さいところにある
それを実現する直方体の配置を1個求める問題．
x座標，y座標，z座標それぞれ独立に考えれば良い．
関係を条件式に落とすと，結局トポロジカルソートになる．
ACM/ICPC Asia - Wuhan - 2009/2010
Wuhan Regional Semilive (2009-11-02) (blog)
LiveArchive 4483
プログラムの数は500個以下，データの数は500個以下．
あるプログラムを実行するのに，必要な時間，必要なデータが与えられ，出力のデータも与えられる．
プログラムはいくらでも並列に実行できる．
最初に手に入るデータが与えられたとき，あるデータを手に入れるまでの最短時間と，それを実現するプログラムの実行方法を1個与える問題．
不可能ならそれを指摘する．
ベルマンフォードっぽく収束するまで，各データの手に入る最小時間，各プログラムが実行できるようになるまでの最短時間を求める．
後は，各プログラムがその時間に実行されるように適当に実行方法をでっちあげる．
ACM/ICPC Latin America - South America - 2009/2010
ACM ICPC South America Regional Contest (2009-10-24) (blog)
LiveArchive 4482
N個のクラスがあって，それぞれ何人か生徒がいて，それぞれの成績が0〜1000までつけられている．
一定の閾値Tを用いて，各クラスを2個に分割するんだけど，それぞれ成績がT以上のものとT未満のものにわける．
それぞれのクラスがa人とb人に分かれたら人数の差は|a-b|で，その和を最小にする問題．
合計の生徒の数は10^5を超えない．
各クラス独立に，閾値ごとに|a-b|の値を求める．
後は，足して，最小になるものを探す．
ACM/ICPC Latin America - South America - 2009/2010
ACM ICPC South America Regional Contest (2009-10-24) (blog)
LiveArchive 4480
2次元の格子状の点が1000個以下与えられる．
それから3点選んでできる2等辺三角形の数を求める問題．
正三角形はできないっぽいので，各点に対して，
他の点までの自分からの距離を全部求めて，できる2等辺三角形の数を求めて足す．
ACM/ICPC Latin America - South America - 2009/2010
ACM ICPC South America Regional Contest (2009-10-24) (blog)
LiveArchive 4479
サッカーの大会で，既に何試合か終わっている．
勝つと2ポイント，引き分けで1ポイント，負けで0ポイント．
あるチームが単独優勝できる可能性が残されているかどうかを判定する問題．
考えるチームは残り全勝と決めつける．
後は，適当にバランスされるまで，勝ち負けを変更していく．
ACM/ICPC Latin America - South America - 2009/2010
ACM ICPC South America Regional Contest (2009-10-24) (blog)
LiveArchive 4478
500*500の盤面に数字が書かれている．
右に単調非減少，下にも単調非減少．
10^4以下のクエリが与えられて，それぞれ，書かれている数字の範囲が全部[A,B]に含まれる最大の正方形のサイズを求める問題．
考える正方形のサイズが決められたとき，チェックしなければいけない正方形は高々行の数ぐらい．
何故なら，左上のマスがAを下回らない中で，一番左を調べれば良い．
後は，正方形のサイズに対して2分探索すれば良い．
ACM/ICPC Latin America - South America - 2009/2010
ACM ICPC South America Regional Contest (2009-10-24) (blog)
LiveArchive 4477
長さ10^5以下の文字列が与えられる．
その部分文字列で相異なるものの数を求める問題．
suffix tree．
ACM/ICPC Latin America - South America - 2009/2010
ACM ICPC South America Regional Contest (2009-10-24) (blog)
LiveArchive 4476
電気代が問題文に書かれた料金体系になっている．
自分が使った電気量+隣の人が使って電気量，を1世帯で使った場合の料金と，
自分の料金と隣の人の料金の差が与えられるので，自分の電気料金を求める問題．
自分と隣の人が使った電気量の合計を2分探索で求める．
後は，自分の電気量を2分探索で求める．