https://db.tt/KixudqAX ライセンスはCC0です。何でも自由に使って・コピペ・改変・再配布してよいです。これを使用した場合のいかなることにも責任を持ちません。 '#'で始まるファイルは未検証、'!'で始まるファイルは検証済みであることを表していましたが…
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倍を使った回数 -> 最小のインクリメン…
rep(j, a.size()) aa[a[j]] = 1; とすべきところを rep(j, a.size()) aa[j] = 1; としていた。 解法がMaximumFlowであって、そっちがバグってるんじゃないかと思っていたが単純なミスだった。解法・ライブラリ・変な所が間違ってるんじゃないかと思って確認…
朝のSRM。少し眠くて心配だったが緊張で眠気は吹き飛んだ。 Coding 900がMedより簡単なこと稀にあるよなーとか考え、Medより前に900を開こうと考えた。 Easy (250) 最初に、「2^(他の[L[j],R[j] ]に被覆されないiの数)？」と考えた。実際にはこれは合ってい…
見た問題の表 - antaの競技プログラミング練習日記 最近練習してなくて惨敗し続けていたのでむしゃくしゃしてやった。 さらにSRM400〜のHardをやろう。
(p - str)とかしてインデックスを求めることはそれなりにある。 しかしこれ(p - str)を(str - p)としても何の警告も出ない！(もしかしたらstrが配列の時は何かあるかも？) (node - nodes)とか紛らわしい名前を使っていると、(nodes - node)としてしまっても…
一番自明なことに気づかないとかChallengeしない主義者！とか Coding Easy (250) なんか変な解法を思いついて、それはExampleを通るものの、まあ嘘だなと思い考えなおす。 考えてみた：「文字aを文字bに変え、その後に文字bを文字cに変えることは意味がない…
久しぶりにSRM。実際に死んだ Coding Easy (250) ほぼ全部を'∧'の形で回る数え方を考えて、1つの車では(平均的に)3つしか回れないかな、と思いceil(頂点数/3)をMODで計算した。 色々考えたり少し手間取ったりして遅すぎた Medium (500) 数え上げ嫌い。順列嫌…
http://db.tt/vepDPsYK ライセンスはCC0です。 '#'で始まるファイルは未検証、'!'で始まるファイルは検証済みであることを表しています。 これを使用した場合のいかなることにも責任を持ちません。 "~template.cpp"はTopCoder以外用のテンプレートです。 "a.…
非常に雑多。しばらく作問もしないので、吐き出しておきます。 単純でない辞書順greedy 辞書順最大の経路履歴みたいに極小・極大であることを利用するとか？ 永続データ構造使いたい meldable-Priority-queue DPしたい 既存の計算結果を埋め込んでどうにかで…
非常に雑多かつ自分用です。 TopCoderというものを知る 2011/05/23 TopCoder部のカレンダーを見ていた。 2011/05/27、 ttp://d.hatena.ne.jp/cou929_la/20091005/1254725798 を見ていた。 2011/06/22 にはTopCoderのArenaをダウンロードしていた。 Practice…
1文字バグ＋別のバグが、巧妙に問題なかったぱたーん Coding Easy (250) 「ガチョウならその周囲もガチョウ」「周囲dist以内の鳥と『同じ種類』」が言える(鳥は2種類なので)。 推移的な「同じ」といえばUnionFind。 そこでUnionFindでグループ分けをする。 …
実況風 Coding Easy (250) とりあえずkiwiとgrapeのオフセットを全探索。 さて、ループ内では最小のところをどうにか高速に求めなければいけないわけだが… なんていうか、なんとなくなのだけれども、 xとyの最小の差は(±xとyのオフセット差 mod gcd(x, y)) …
問題 Editorial 問題 単語列wordsが与えられる。それらを全て含む、長さ最小の文字列の辞書順最小を求めよ 1 1 解答 まず、他の文字列に含まれている関係にある文字列たちを除去する。 この除去された文字列は他の文字列に含まれるので、考えなくても問題の…
int a[5]={1,2,2,2,4}; multiset<int> s(a,a+5); s.erase(2); //s = {1,4} C++STLはきちんと体系的に学んでいないから勘違いが多くて悪い</int>
神回だった Coding Easy (250) こういう系の問題苦手すぎる。 とりあえず(K (K さて、問題は(K>n-K)の時。 これは考えると(n-K)ごとのブロックに分かれて、(i Medium (500) (サイズ これは半分全列挙できる。 半分の桁までを全列挙し、(各guessesでヒットの…
