part1 フィボナッチ数の小ささ fib(n)は指数オーダーで結構大きいが、2^nよりは全然小さい。 "SRM 451 DIV1 Hard BrickPuzzle"は列DPを特定の形のブロックでするもの。ブロックの形が、下側が絶対2つ単位で隣接しているため、そのような形の状態しか覚えなく…

SRM400代のHardで使ったものを見てみる。最初は全部記事書こうかと思ったがめんどくさくてやめた。 桁落ち誤差回避 ほとんど等しい2つの数を引き算すると、有効桁数が減少する。 式変形をして引き算をなくしたりする必要がある。 SRM 400 DIV1 Hard Collecti…

問題 Editorial 問題 あるグラフに対して頂点集合Sがk-stableであるとは、S中のそれぞれの頂点に対して、隣接する頂点の中でSに含まれる頂点の数がk個以下であるものをいう。 木graphが与えられる。i∈[0..|graph|-1]のそれぞれでi-stable setの数をmod 11290…

問題 Editorial 問題 整数座標x,yで単純多角形が与えられる。整数denomが与えられる。 全ての整数a,bに対して座標(denom*a,denom*b)を考える。この座標のうち与えられる多角形に含まれる座標すべてにwifiを置きたい(wifi点と呼ぼう)。wifi点はいくつあるか求…

問題 Editorial 問題 rows×colsのグリッドがある。以下の操作をK回する： ランダムにセルを選び、それをAとする。 ランダムにセルを選び、それをBとする。 AとBを頂点とする矩形上に色を塗る AとBは独立に選ばれる。セルは全て等確率で選ばれる。色は上書き…

問題 Editorial 問題 無向重み付きグラフで以下の条件を満たすものgraphが与えられる： それぞれの頂点に対して、たかだか1つの単純閉路に含まれる それぞれの頂点v,uに対して、vからuへのsimple pathはたかだか1つ 頂点start,finishと正整数kが与えられる。…

問題 Editorial 問題 いくつかの企業がある。それぞれの企業はデータを処理して独自形式のデータにする。 企業はそれぞれデータの処理数に上限がある。また、処理できるデータの形式にも制限がある。もちろん、データ処理の仕事の依頼にはコストがかかる。こ…

問題 Editorial 問題 lucky numberとは、それを10進数で表記したときに4と7しか現れない正整数である。 整数nが与えられる。nを複数のlucky numberの総和で表す。lucky numberの数を最小化したい。そのような解のうち、辞書順最小のlucky numberの列を求めよ…

問題 Editorial 問題 '0'〜'9'からなる文字列digitsが与えられる。 この文字列をいくつかに分割し、それぞれを整数として読む(leading zeroは許可され、単に無視される)。ただし、列はstrictly increasingでなければならない。 このような列の中で、最後の整…

問題 Editorial 問題 凸多角形(x,y)が与えられる。 ある整数点がN-coolであるとは、多角形の中(辺上も含む)にあって、少なくとも1つのN-coolな線分の端点となっていることである。 ある線分がN-coolであるとは、多角形の中にある整数点を少なくともN個含むこ…

問題 Editorial 問題 飲料メーカーがキャンペーン中。 ジュースのボトル1つと引き換えに、nつの異なるコードのうちランダムな1つが等確率で得られる。 kつの異なるコードを得たい。 それが達成されるのに必要なボトルの数の期待値を求めよ 1 ≦ k ≦ n ≦ 10^18…

見た問題の表 - antaの競技プログラミング練習日記 解けてないものや、Editorialがないので解法がわからないものなどもあるが、77問は解法を見る見ないにかかわらず自分でコードを書いた。 Hardは新たなテクニックを知ることのできるからいいね。 とりえあず…

http://maximum-cup-2013.contest.atcoder.jp/ Problems A 最初関節点？？？二重連結成分？？？とかよくわからなかった。 その後「まず最小の本数」なことをきちんと考え、「3頂点以上あれば、Hamiltonian cycleだな」と気づいた。 これは普通にbitDPすれば…

数を長さNで循環シフトさせて、その後の偶奇を知りたかった。 if((x - shift + N) % N % 2 == 0) ... としなければいけないところを if((x - shift) % 2 == 0) ... とかしていた。 当たり前だが、((x mod m) mod n = x mod n)は一般には成り立たない。 例え…

少し調子が悪かった。 Coding Easy (250) 最初全くわからず、焦った。 なんていうか2倍の操作は共有されるけどそれ以外は独立だから全部独立に求めた後上手く合成すればいけるのでは？と考える。 とりあえずDPで(数 * 2倍を使った回数 -> 最小のインクリメン…