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