問題 Editorial 問題 床屋がある。 この床屋はAM 9:00に開店し、PM 5:00に閉店する。 床屋では常に1人までしかカットすることができない。 誰かのカットの最中に他の人が入ってきた場合、そのカッティングが終わるまで待たされる。キューの動作をする。 客が…

問題 Editorial 問題 "Antichess"と呼ばれるゲームをする。 このゲームの目的は自分の駒を全て取られることである。 また、取れる駒があるならそのどれかを必ず取らなければならない。 今、white(自分, 先手)はポーンが何個かだけが残っていて、black(相手, …

問題 Editorial 問題 トランプのカード(ジョーカー無し)が"重複有り"で何枚か与えられる(decks)。 ここから5枚取った時に、ポーカーの役のそれぞれになる確率を求める。 確率が0より大きい役だけを、確率の低い順・同じなら辞書順順にvectorで返せ。 役は以…

参照 ウェーブレット木の世界 http://code.google.com/p/wat-array/ コメント ウェーブレット木のほうも実装してみたが、ウェーブレット木の世界のスライドに「(ウェーブレット木よりウェーブレット行列を)"常にこちらを利用すべき？"」とあるように、ウェー…

参照 Matrix Reference Manual "Special Matrices" Autumn Fest 2012 解説スライド "Ninja of Train" あとwikipedia。(wikipediaをreferenceにするのって…) このエントリについて 行列累乗の高速化としての問題が作れる、行列の特殊形を3つメモする。 実際の…

http://codeforces.com/contest/261 Problems A 一番数の少ないdiscountだけをgreedyに使う B わかんなかった C コードの行列は、これはパスカルの三角形の偶奇を生成する。まあコードの通りに読めばわかるし表示してみればわかりやすい。 そのある行での1の…

問題 Editorial 問題 何人かとそれぞれのロボットとグリッドのマップがある。ロボットでレースをする。 マップは空白・壁・"token"・ロボットの開始地点マークからなる。 壁は'*'で表される。 各ロボットの開始位置は一意な、ロボットを表すアルファベット小…

問題 Editorial フォーラム 問題 x*yのグリッドに1〜nのサイズの正方形を互いに重ならないように置きたい。最大のnを求めよ 1 解答 枝刈り全探索。 まず、(sum (map (^2) [1..14]) > 30 * 30)なのでnは13以下。 探索を少なくするために、大きいものから置い…

問題 Editorial 問題 重さweightと許容重量capacityが設定された箱がNつある。 箱は他の箱の上にいくつでも積み上げられるが、どの箱も上に乗っている箱の重量の総和が許容重量以下でなければいけない。 積み上げられる最大個数を求めよ 1 1 1 解答 Editoria…

問題 Editorial 問題 3文字のアルファベット大文字が書かれたカードが何枚かある(cards)。 隣接する3つのカードの左右を選び、それらに共通する文字が2つ以上あるならば真ん中のカードを消すことができる。 カードを消せる最大枚数を求めよ 2 解答 Editorial…

問題 Editorial 問題 0〜99のマスがあるボードで複数人のプレイヤーでゲームをする。 各プレイヤーiは最初にplayers[i]のマスに居る。 各プレイヤーは各ターン、6面のサイコロを2つふり、出た目の合計だけ進む。このとき、99のマスに止まったりそこを通過し…

問題 Editorial 問題 サイズamountの数値のmultisetであって、総和がnで、全ての要素がminInComp以上で、全ての要素の最大と最小の差がminDif以下であるようなものの場合の数を求めよ 5 1 解答 Editorialを参考にした。あまりよくわかっていない。 DP。 まず…

問題 Editorial 問題 最大50*50の画像が2つ(imageA, imageB)ある。 両方の画像で共通する正方形の最大サイズを求めよ 解答 (サイズ*Aの左上座標*Bの左上座標)全探索。 両方の領域が等しいかの判定にハッシュを使った。 O(n^5)だが、サイズ毎に座標の範囲が制…

問題 Editorial 問題 十進表示をした時に全ての数字が奇数である数を"odd-digitable number"と呼ぶ。 (x ≡ M (mod N))であるような最小のodd-digitable numberを求めよ。ただし存在しない場合は"-1"を返せ 解答 Editorialを参考にした。 BFS。 最初に0から始…

問題 Editorial 問題 「この文の中にxつのy(数字)が出てくる、またzつのw(数字)が出てくる」というような文であって、 文の中に現れるすべての数字に対して言及していて、 真であるような文を"self-catalogue"と言う。 数字はx,zの部分とy,wの部分が数えられ…

問題文は見つけられなかった(Editorial, Match OverviewsからのStaticsが無い) 問題 4*4のボードがある。 まずここに、"位置も向きもランダムに"16つのキューブcubesを全てはめる。 各キューブのそれぞれの面は違う文字である。 その後辞書dictに登録されて…

問題 Editorial 問題 アーティストの名前とその人の曲の数artistsがいくつか与えられる。 各アーティストがその人の曲の数だけ出てくるリストであって、 let d v = sum. map (maybe 0 succ. uncurry elemIndex). zip v. tail. tails$ v と定義されるd(x)を最…

問題 Editorial 問題 2つの凸多角形の共通部分の面積を求めよ 解答 ライブラリゲー Spaghetti Sourceさんhttp://www.prefield.com/algorithm/index.html のコードを使った コードはほぼSpaghetti Sourceさんのコードそのままなので、ここに貼るまでも無いの…

問題 Editorial 問題 初期状態として、整数座標上の点がいくつか与えられる(xs, ys)。 いつでも、任意の点2つ(p, q)に対して((p.x + q.x) / 2.0, (q.x + q.y) / 2.0)の点を作ることができる。 この操作を無限にどんなふうにでも繰り返せるとき、全ての点を被…

問題 Editorial 問題 略 解答 (ターン * 残り時間 * スコア)でゲームDPするだけ コード #include <vector> #include <cstring> #define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i)) #define mset(m,v) memset(m,v,sizeof(m)) using namespace std; typedef vector<int> </int></cstring></vector>…

問題 Editorial 問題 輪になったネックレスがある。 ネックレスの各宝石の価値gemsが与えられる。 このネックレスをn回カットしてnつに分けたい。 カット後の各部分は1つ以上の宝石が含まれていなければいけない。 カット後の各部分の価値の総和の(最大-最小…

問題 Editorial 問題 abs(sqrt(N) - a/b)が最小となる正整数a, b (b 1 1 解答 long doubleでやるだけ。 最小との比較は整数演算だけでもできるらしい(Editorial参照) コメント 簡単回。 最小との比較の誤差を何も気にせずに書いてた。それ駄目だろ！まあlong…

問題 Editorial 問題 それぞれ一定の時間だけを測れる砂時計timersが与えられる。 砂時計は最初か他のどれかの砂時計の砂が落ち終わった時にのみひっくり返すことができる。 砂時計をひっくり返すタイミングで、"Start"や"Stop"と言うことができて、"Start"…

問題 Editorial 問題 6*7の盤面での"Connect Four"の局面が与えられる。 その局面に到達することが可能かかどうか、もし到達可能なら次はどのプレイヤーか、もしくはどのプレイヤーが既に勝っているか、あるいはもう打つ手はない(引き分け)か、を返せ 解答 …

問題 Editorial 問題 略 解答 Editorial参照。 最大でも4回でいけるので、全探索できる コメント この問題はおもいっきりそれっぽい感じで。書けないといけないな… 今もその4回のやり方わかってないけど コード #include <string> #include <sstream> #define rep(i,n) for(in</sstream></string>…

問題 Editorial 問題 width*heightの紙がある。 ここからk-polyominoのどれかを1つだけ切り取りたい。グリッドセルに区切られているその境界線上のみを切ることができる。 ただし切り取った後の紙が連結でなければいけない。 k-polyominoとは、kつのセルで出…

問題 Editorial 問題 width*heightの長方形の紙がある。 ここから与えられたパターンpatternを何枚か切り取りたい。 パターンは90°刻みで回転してもいいが、反転してはいけない。 最大で何枚切り取れるかを求めよ 1 1 解答 左上が紙の半分に収まる切り方を全…

問題 Editorial 問題 座標軸に平行か45°斜めかのどちらかの線分が複数与えられる。 この中作ることができる三角形を数えろ 0 線分はオーバーラップすることもある 解答 まず、重複しないように辺をマージする。 次に、線分同士で交差する点を全部列挙する。 …

問題 Editorial 問題 let s = map (concatMap (uncurry replicate). flip zip "abcd"). mapM (\[l, u]-> [l..u])$ [abounds, bbounds, cbounds, dbounds] in length. nub $(++) <$> s <*> s を求めよ 解答 まず左と右の全ての文字が0文字かどうかを全探索し…

問題 Editorial 問題 H*Wのマップが与えられる。 マップはそれぞれ '.': 空白, '#': 壁, '/': "／"の形の鏡, '`': "＼"の形の鏡 マップの周囲は壁に囲われており、ちょうど2つだけ穴があいている。 一方の穴からもう一方の穴へ光を通したい。 光は壁に当たる…