SRM
問題 Editorial 問題 略 解答 二分探索*二部マッチング。 mid以下の時間でたどり着ける位置同士に辺を張って、完全マッチングが出来るかどうかで判定する コード #include <string> #include <vector> #include <sstream> #include <cmath> #define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i</cmath></sstream></vector></string>…
問題 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のグリッドがある。 この任意…
問題 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で返せ。 役は以…
問題 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"の局面が与えられる。 その局面に到達することが可能かかどうか、もし到達可能なら次はどのプレイヤーか、もしくはどのプレイヤーが既に勝っているか、あるいはもう打つ手はない(引き分け)か、を返せ 解答 …