問題 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つだけ穴があいている。 一方の穴からもう一方の穴へ光を通したい。 光は壁に当たる…

問題 Editorial 問題 H*Wのマップparkが与えられる。 parkはそれぞれ '.': 空白, 'X': 壁, 'C': 車, 'P': 駐車場。 車を全て駐車場に駐車させたい。1つの駐車場に1台までしか駐車できない。 車は同じマスを複数通ることができる(駐車場のマスでも、そこを通…

問題 Editorial 問題 水平の境目で分割された領域がいくつかある。 それぞれの領域は幅がwidth[i]で、speed[i]の速度を出すことができる。 (0, 0)から(offset, sum width)まで行くとき、時間を最小化せよ 解答 それぞれの領域ではspeed[i]に比例する傾き(cos…

問題 Editorial 問題 "unsortedness point"とは、(数列a, 0 a[j])となるインデックスの組である。 m,bが与えられるので、(a[0] = 1; a[i] = (m * a[i-1] + c) mod 2^31-1)というように数列を長さnまで生成する。 その数列の"unsortedness point"の数を求めよ…

問題 Editorial 問題 ディスクに対して、中心と外周上の1点を結ぶ線分でカットすることが出来る。 カットした時に切り分けられたならばそれぞれもディスクとしてカットできる。その場合の中心・外周は最初のディスクのもの。 カットするたびにそのディスクの…

問題 Editorial 問題 商品がいくつかある。 商品にはそれぞれ"pointValue"と値段がある。 ポイントをその商品のpointValueだけ使ってその商品を無料で買うことができる。 また、半額ポイントというものもあって、それを1つ使って1つの商品を半額で買える。 …

問題 Editorial 問題 化合物がM種類ある。 化合物はavailableMixturesによって表され、N種類の薬品の重み付き和として表される。また、それぞれ値段もついている。 その中からそれぞれいくらかずつ混ぜて別の化合物mixtureを作りたい。 それぞれの混ぜる量は…

http://codeforces.com/contest/258 Problems A 一番最初に出てきた0を除去する。1しか無いときは場合分け B 最初"lucky digit"をラッキーな数、的に読んでて4か7だけだと思っててWAった。 あるlucky digitの個数の数の個数を桁DPで数えてパーティーの組み合…

問題 Editorial 問題 (f: string -> string)は、全ての出現するaをarepに置き換え、bをbrepに置き換え、cをcrepに置き換える(同時に)。 (length (f^iter("a")) mod m)を求めよ。ただし(f^n)はfをn回適用する関数とする。 arep, brep, crepはa,b,cからなる1か…

問題 Editorial 問題 まず最初にランダムな単語がwordsの中から選ばれる。 最初はその単語のそれぞれの文字は隠されている。 各ターン、プレイヤーは文字を一文字言うことができる。最初に選ばれた単語の中にその文字があるなら、その部分がわかり、もう一度…

問題 Editorial 問題 略。あまりわかってない 解答 Practice Roomのiwiさんの解答を参考にした。 "entry"ステートメントとループの末尾を全探索する。 そしてうまい感じでdfsする感じの感じ。わかってない。 末尾からグラフを逆にentryに達するまで見ていき…

問題 Editorial 問題 直径dの円周上のcつの点を与えられる。 この点のどれか4つを選んで四角形を作るとき、面積を最大化せよ 1 4 解答 四角形は2つの三角形に分けられる。 対角線上の頂点を2つ全探索したら、その左右で3,4つ目の点を独立に選べる。 3,4つ目…

問題 Editorial 問題 いくつかの質問の回答率が与えられる。 このテストの平均点と標準偏差を求めて、回答数から"standardized score"を求めよ "standardized score" = 1000 + 300 * (回答数 - 平均) / 標準偏差 解答 あまりよくわかってない。 自分は標準偏…

問題 Editorial 問題 (凸とは限らない)単純多角形の三角形分割を、辞書順最小でしろ。 引かれた対角線と多角形は、始点・終点以外で交差や触れてはならない 解答 まず、適当に対角線をひいても、三角形分割ができなくなることはない。つまり単純な辞書順gree…