問題 Editorial 問題 大きいマップに縦の道路と横の道路が最大600個くらいあるから道路を渡る回数を最小化して 解答 座標圧縮してBFS。 自分は道路の前後も座標に含めたらメモリがギリギリになってしまった。 含めるのは道路の座標そのものだけでいいらしい…

問題 Editorial 問題 n人の人とプレゼントがn個ある。それぞれの人の各プレゼントのスコアvalueが与えられる。 今、人iはプレゼントiに割り当てられている。 ここから、何人かでプレゼントを交換したとき、新たな各人のスコアの総和がそれをする前より増加す…

問題 Editorial 問題 数列seqが与えられる。この数列に"imposition"という操作をN回行った後の数列を求めよ。 "imposition": 各要素にその次(最後の要素の次は最初の要素)の要素をmod100で足す 2 0 1 解答 行列累乗するだけ。 (A[i][i] = 1; A[(i+1)%n][i] =…

問題 Editorial 問題 指定されたプログラムcommandsRobbie,commandsSpeedyに従って動くロボット2台がある。 プログラムはU,D,L,Rからなり、それぞれ右・左・上・下に動く。壁の方向に動こうとする場合は動かない。 今xSize*ySizeのグリッドがある。 この任意…

解答書きました: http://d.hatena.ne.jp/anta1/20130201/1359651597 ※一瞬このブログに別の問題文を載せてましたが、問題変えました ※少しの発想で作っただけで、よく考えたりしていないので、質は良いとはいえないです。 問題 サイズN(≦10^3)の、段yの幅はy…

問題 Editorial 問題 画像が上手く表現できないので略 解答 (交差点の(x * y * (真ん中, 四隅)))でDPするだけ。 (width コメント これは一瞬で解けるべき コード #include <string> #include <algorithm> #include <cstring> #include <complex> #define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i</complex></cstring></algorithm></string>…

問題 Editorial 問題 (問題の肝の部分のみ) width*heightの長方形の中にx*yの長方形が回転してでも入るかどうかを判定せよ 全ての数値は整数, [1,1000] 解答 回転後の幅と高さは(x cosθ + y sinθ, x sinθ + y cosθ)。 それを適当にいろんな感じで二分探索し…

問題 Editorial 問題 Nつに分割されたパイがある。Nは3の倍数である。そのそれぞれの部分の面積piecesが与えられる。 これを自分と相手で交互に食べ、自分が食べる面積を最大化したい。 自分は、任意の部分を1つ選び、それを食べることができる。 次に、相手…

問題 Editorial 問題 複数行コメントを削除したい。それはネストできる。 複数行コメント"MLC"は以下の構文で定義される: MLC := "/*" <Nester> "*/" Nester := ("/*"も"*/"も含まない文字列) | <Nester> <MLC> <Nester>プログラムlinesがvectorで与えられる。これは各行を表していて、文</nester></mlc></nester></nester>…

問題 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)だが、サイズ毎に座標の範囲が制…