Latest Entries
2009年11月26日01時から．
普通っぽい部屋かな．
問題が250, 450, 1000の変則セット．
1000にじっくり時間をかけれそうなセットだ．
あからさまにBFSしてください，という問題…．
実装あるのみ．サブミット．
適当に使えるコスト列挙してDPにしか見えない．
瞬殺できるだろー．
平面グラフという条件を忘れていて，普通にエッジの数はn*(n-1)/2以下としてサブミットしてしまった．
平面グラフだった枝の数の最大値っていくらだ？
適当に絵を書いて考えてみる…．
n=5で考えて，3n-6っぽい気がする…．
n=4でもOK．n=6だと…自信ないけどあってるような…．
3n-6でいいや，サブミット．
うーん…？
取り敢えず，ラッキーナンバーを列挙してみる．
これからどうするんだろう…．
取り敢えず，ラッキーナンバーの中から，他の物の倍数になっているのは除外してみる．
でも，包除原理すると計算量2^1000を楽に越えるぞ．
いやいや，違う，数個使ったらB超えちゃうから，殆ど使えなくて，包除原理しても大した計算量にはならないはず！
書いてみた．よゆーで間に合う．サブミット．
他にも完全グラフでやってる人いるから知れないからチャレンジケース作っておこう．
…あれ，挙動がおかしい…．
条件で3*i-6と書くべきを3*n-6と書いてるorz
再々サブミット．最低点の135点…．
完全グラフだと思ったときに間違うテストケースとして385をゲット．
コーディング時間は後15分．
おなか減ったのでご飯食べよう．もぐもぐ．
MEDIUMを片っ端から開く．
結構，使える枝の数の式間違えている人がいるぞー？
でも，もっと使えないと勘違いしてる人が多い…，そりゃそうだ．
そんなテストケース作ってねー…．
急いで作る．206とか360とかでいけるのか？
とか思ってたうちに他の人に全部落とされちゃった…．
ノード数が2のとき，例外処理してて枝数0を忘れている人がいたのでそれだけつつく．
HARD落ちた…．あれ？
MEDIUM連敗記録は脱出したけど，いつもより駄目な感じな結果．MEDIUM最低点だし．
HARD落ちた元凶はラッキーナンバーのリストの最後に100000000000LLを追加したこと．
GCDとれば，普通にカウントされるぐらいに小さかった…．
通ってればHARD最速だったのになぁ…，とかまぁそういうのは良くありすぎるので，通すことが難しいのがよくわかる．
2009.11.23 21:50頃--2009.11.24 05:00頃 DAM
2部屋，滞在時平均人数7.2人ぐらい．(最高9人，最低7人)
ACM/ICPC Europe - Southeastern - 2009/2010
LiveArchive 4549
1〜nの数字が書かれた宝石箱がある．
数字kの書かれた宝石箱には，重さW_k，価格C_kの宝石がk個入っている．
合計重さW以下で価格が最高になるように宝石を選ぶと，最高価格はいくらになるか．
nは15以下．その他は10^9以下．
DPだと状態数が爆発するけど，良く考えれば全探索でも最高で16!通りしかない．
枝刈り探索で間に合った．
ACM/ICPC Europe - Northwestern - 2009/2010
Another Regional Contest (NWERC 2009, 2009-11-14) (blog)
LiveArchive 4617
2次元平面上のn点が与えられる．(nは2000以下)
それを頂点とするような単純な多角形を1つ構成する問題．
角度が180度の点があっても良い．
凸方を作る時みたいに，最も上の点を左から右になぞって，あとは使わなかった点を全部右から左に追加していった．
角度でソートして順番に使うなどでも良い．
ACM/ICPC Europe - Northwestern - 2009/2010
Another Regional Contest (NWERC 2009, 2009-11-14) (blog)
LiveArchive 4616
六角格子に1〜5までの数字を，ぐるぐると以下のように置いていく．
隣り合った場所にある数字はおかない
今まで置いた数の一番少ない数字を置く
複数あるなら，小さい数字を置く
n番目に置いた数字を求める問題．nは10000以下．
シミュレーション．実際においてみる．
ACM/ICPC Europe - Northwestern - 2009/2010
Another Regional Contest (NWERC 2009, 2009-11-14) (blog)
LiveArchive 4614
ノード数50000以下の木が与えられる．枝には距離が付与されている．
それぞれのノードkに訪れなくてはいけない回数d(k)が与えられて，
Σ[iは全てのノード] xとiとの距離 * d(i)
が最小となるノードxを全て列挙する問題．
DPする．O(n)．
ACM/ICPC Europe - Northwestern - 2009/2010
Another Regional Contest (NWERC 2009, 2009-11-14) (blog)
LiveArchive 4613
細い道がある．
左右から同時に車が進入するとぶつかるので，片方ずつしか進めない．
しかし，片方から2台進むときは，道の最中のどの点においても，10秒以上の間隔を空けなければいけない．
左右どちらに，時刻いつ辿り着いて，その車の最大スピードで道を進んだ場合の必要時間が与えられるので，全ての車が道を超えるまでの最小所要時間を求める問題．
車の数は200以下．
どちら向きの車を走らせるかが決まっているなら，到着順に，出発できるならすぐ出発するのが最適．
最後にどちら側の車が通ったか，右側からきている車は後何台残っているか，左側は後何台か，を状態にDPする．
領域量O(n^2)，計算量O(n^3)．
ACM/ICPC Europe - Northwestern - 2009/2010
Another Regional Contest (NWERC 2009, 2009-11-14) (blog)
LiveArchive 4612
2次元平面上の折れ線が与えられる．
深さ1のフラクタルはその折れ線自身．
深さdのフラクタルは，深さd-1のフラクタルの各線分を，適当に回転縮小して始点終点が合うようにして折れ線に置き換えたもの．
深さdのフラクタルで，始点から f*(深さdのフラクタルの長さ) の位置の座標を求める問題．
2次元幾何実装問題．
長さが増えていく割合は一緒なので，再帰で，どこの線分に属しているかを判定していく．
ACM/ICPC Europe - Northwestern - 2009/2010
Another Regional Contest (NWERC 2009, 2009-11-14) (blog)
LiveArchive 4611
長さnの正整数列が与えられるので，その連続する部分列で，和がdで割り切れるものの数を求める問題．
基本的な考え方はSPOJ 2150と同じでmod取るだけ．
ACM/ICPC Europe - Northwestern - 2009/2010
Another Regional Contest (NWERC 2009, 2009-11-14) (blog)
LiveArchive 4609
7個以下の数字が与えられるので，その数字を使ってできる素数の数を求める問題．
作れる数字を全部列挙して，素数であるかどうか判定するだけ．
ACM/ICPC Europe - Northwestern - 2009/2010
Another Regional Contest (NWERC 2009, 2009-11-14) (blog)
LiveArchive 4610
ノード数50000以下の完全2分木が与えられる．ノードには文字列が付与されている．
枝を張りかえて，ノード数をできるだけ減らす問題．問題文の図を参照．
どっちかいうと，文字列処理+実装問題．
グリーディーに減らせば良い．
MIT 1st Team Contest 2007
SPOJ 2320 [DISTANCE]
d次元上のn点の座標が与えられる．
マンハッタン距離で最も遠い2点間の距離を求める問題．
例えば，6次元座標の点(a1,b1,c1,d1,e1,f1)と(a2,b2,c2,d2,e2,f2)のマンハッタン距離は
x1 = a1 + b1 - c1 - d1 + e1 - f1
x2 = a2 + b2 - c2 - d2 + e2 - f2
として|x1-x2|と同じかそれより小さい．
符号の付け方2^(d-1)通り全て試して，「足したり引いたりした値の最大値-最小値」の最大値が答えになる．
NITT ACM ICPC Local Contest 2007
SPOJ 1881 [ICODER]
Xは最初は0から65535までのどれかの数．
以下の2種類ある命令をn個こなした後，取り得る数字の数を求める問題．
ADD k → Xを(X+k)%65536変える
MUL k → Xを(X*k)%65536変える
ADD 3, MUL 4, ADD 5ならX → 4*(X+3)+5 = 4X+17という風に結局aX+bって形で書けるので最初にaとbを計算する．
後は全部試してみる．
ちなみにbは関係ないので考えなくても良い．
ZCon 2007
SPOJ 1419 [NGM]
2人でゲームを行う．
最初20億以下の数字が書かれている．
順番に，その数字(の10進数表示)に使われている0以外の数字を1つ選んで引いていく．
最初に0にした人が勝ち．
先手必勝か，後手必勝かを判定して，先手必勝の場合は，最初，いくら引けば勝てるかを求める問題．
10の倍数で順番がまわってきたら負ける．
引く数字は1〜9だから相手は10の倍数にならないし，相手は，1の桁の数字を引いて10の倍数にして送ってくる．
Base on a problem in ByteCode06
SPOJ 705 [SUBST1]
長さ50000以下の文字列が与えられるので，その中に含まれる相異なる部分文字列の数を求める問題．
SuffixArray + LCPでLCPの分だけ重複しているので減らしてやればよい．
Folklore
SPOJ 530 [DIV2]
正整数Nの約数の個数をd(N)とかく．
1000000以下で，d(N)は3より大きくかつ
N mod M = 0 ならば d(N) mod d(M) = 0
となるようなNを全て列挙する問題．
普通に約数の個数を全部求めて，割り切れるMに対して全部チェックしてもローカルだと1.5秒ぐらいで答えが出るのでOKかと思ったらTLEだった．
よくよく考えれば，素因数分解したとき，指数に2以上の数字が出てこないもののうちでd(N)が3より大きいものを全部列挙すれば良かった．
University of Ulm Local Contest 2005
SPOJ 384 [FOOL]
集合ってのは文字列で，
{要素1,要素2,…,要素n}
って形のもの．要素数が0も許す．
要素は集合もしくは，1文字で{},のどれか．
200文字以下の文字列が与えられるので，それが集合かどうかを判定する問題．
典型的なDP．領域量O(n^2)，計算量O(n^3)．
ACM Central European Programming Contest, Prague 1998
SPOJ 48 [BEADS]
長さ10000以下の文字列が与えられる．
その文字列をサイクリックに最後の文字は最初の文字になっていると思った時，どこから読めば辞書順で最小になるかを答える問題．
サイクリックに長さを2倍にして，最後に番兵として大きな数字を入れて，SuffixArray作ってみれば良い．
数字からなる長さ22文字の文字列が100000個以下与えられるので，それを辞書順で何が何個あったかを出力する問題．
ソートするだけ．
制限時間が厳しいっぽいことが書いてあったのでTrieでも作ろうかと思ったけど，普通にint配列にしてソートするだけでAcceptされた．
2009年11月14日16時から5時間，10問．
[ Link ]
寝坊して45分遅れぐらいで参戦．
なんとかGとJ以外の8問解いた．
GはAcceptが0で，JはAcceptが1なので，まぁまぁかな．
GとJを除くと，簡単めな問題が多いかな．
Aは与えられた数字を使ってできる素数の数を求める問題．全部作ってチェックするだけ．
Bはノードに文字列が付与された完全2分木が与えられる．枝を張りかえてノード数を減らす問題．
適当にハッシュで判定しようとして上手くハッシュ作れなくてWAもらった．
愚直に判定やるとノード数最大50000でO(n^2)になっちゃうので駄目っぽいと思ってたんだけど，1秒台で通った．
Cは連続する部分列でdで割り切れるものの数を求める問題．前SPOJか何かで解いた記憶がある．たぶんこのブログの何処かに書いてる．
Dはフラクタル．2次元幾何+再帰．実装問題．
EはDP．どっち向きの車が次に進むかが決まっていたら，到着順に，進めるようになったら即座に進むのが最適．
最後にどちらの側の車が走ったか，両側の車があとどれぐらい残っているか，でDPすれば良い．
領域量O(n^2)，計算量O(n^3)．
FもDP．O(n)．適当にルートを決めてやると，ルートから計算すると上手くいく．
Gはわからん．
Hはシミュレーション．6角座標を問題文に書かれている通りに数字を埋めていけばよい．
てか，カタンって，数字は中心から並べていくけど，資源の配置は並べ方違うのではなかったっけ…？
Iは幾何．点が与えられるので，それを頂点となる単純な多角形を作ってくださいという問題．
上をなぞって，その後下をなぞって凸包を作る方法があるけど，それの上だけなぞって，後は右から使わなかった点を全て追加していく感じで解いた．
Jはヨーロッパリージョンではお馴染みのワームホールの問題．単純にダイクストラしてTLEもらった．
Europe - Southwestern - 2009/2010
SWERC 2009 (One more ICPC Regional Contest, 2009-11-07)
LiveArchive 4513
長さ40000以下の文字列が与えられる． その中で，部分文字列としてm個以上現れるものの最長の長さと，それが現れる一番右の場所を求める問題．
長さに対する2分探索．
長さを決めつけると，m個以上現れる部分文字列が存在するかどうかは，rolling hashを使うとO(文字列全体の長さ)で求めることができる．
Europe - Southwestern - 2009/2010
SWERC 2009 (One more ICPC Regional Contest, 2009-11-07)
LiveArchive 4512
電話を開始した時刻，通話の長さのログが与えられる．通話の数は10000個以下．
100個以下のクエリが与えられて，それぞれのクエリに対して，ある時刻の区間に対して，通話している数を求める問題．
全部チェックしても十分間に合うのでやるだけ．
Europe - Southwestern - 2009/2010
SWERC 2009 (One more ICPC Regional Contest, 2009-11-07)
LiveArchive 4510
初期地点と，x軸に平行な線分がn個与えられる．(nは1000以下)
初期地点は，もっともy座標の値が大きい．
初期地点から，その線分を全て通るような経路のうち，長さ最小のものの長さを求める問題．
それぞれの線分の端点に移動するのに必要な長さをDPで計算する．
上手く計算しないと，O(n^3)になっちゃうけど，点を角度でソートしたりして，O(n^2 log n)ぐらいで書いた．
ACもらえるけど，遅いので，もっと良い方法があるのかもしれない．
Europe - Southwestern - 2009/2010
SWERC 2009 (One more ICPC Regional Contest, 2009-11-07)
LiveArchive 4507
最初自分の持ち点はn．(nは501以下)
順番にダーツを投げて，当たった場所に書かれている数字だけ点数が引かれる．
ただし，マイナスになる場合は引かれない．
2人で交互に投げて，先に0点になったほうの勝ち．
的に書かれている得点は1〜20で，図に書かれた通り．
プレイヤーAは，ランダムに何処かに当たる．
プレイヤーBは，隣接3つのうちどれかに等確率当てることができるので，勝率が高くなるように選ぶ．
それぞれのプレイヤーに対して，そのプレイヤーが先行の場合の勝率を求める問題．
典型的なDP．
ループする場合は，ちゃんとそれを考慮して計算する．( x=ax+b → x=b/(1-a) )
Europe - Southwestern - 2009/2010
SWERC 2009 (One more ICPC Regional Contest, 2009-11-07)
LiveArchive 4505
机にお盆を置く場所は2か所しかない(重ねることは可能)．
机に1枚ずつ合計m枚お盆を置く
机から1枚ずつ合計m枚お盆を取る
という操作の列が与えられるので，机からお盆取られるとき，最も古いお盆から順番に渡すようにする方法を1個提示する問題．
机にあるお盆を1枚ずつ合計m枚移動する
という命令も付け加えて良い．
お盆が来たら，パイルBに取り敢えず全部積み重ねる．
お盆を渡すときはパイルAから渡して，パイルAが空になった瞬間，パイルBのお盆を全てパイルAに移動させる．
Europe - Southwestern - 2009/2010
SWERC 2009 (One more ICPC Regional Contest, 2009-11-07)
LiveArchive 4504
2次元平面上に50000個以下の点がある．
最も遠い点までの距離が最小となるような，x軸上の点のx座標と，最も遠い点までの距離を求める問題．
x座標の位置で3分探索．
最も遠い点までの距離で2分探索とかでも良いらしい．
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以下．
複数答えが存在する場合，辞書順最小のパラメータを答える．
実際に全部試してみて，エントロピーを計算する．