問題 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…

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

朝のSRM。少し眠くて心配だったが緊張で眠気は吹き飛んだ。 Coding 900がMedより簡単なこと稀にあるよなーとか考え、Medより前に900を開こうと考えた。 Easy (250) 最初に、「2^(他の[L[j],R[j] ]に被覆されないiの数)？」と考えた。実際にはこれは合ってい…

一番自明なことに気づかないとかChallengeしない主義者！とか Coding Easy (250) なんか変な解法を思いついて、それはExampleを通るものの、まあ嘘だなと思い考えなおす。 考えてみた：「文字aを文字bに変え、その後に文字bを文字cに変えることは意味がない…

久しぶりにSRM。実際に死んだ Coding Easy (250) ほぼ全部を'∧'の形で回る数え方を考えて、1つの車では(平均的に)3つしか回れないかな、と思いceil(頂点数/3)をMODで計算した。 色々考えたり少し手間取ったりして遅すぎた Medium (500) 数え上げ嫌い。順列嫌…

1文字バグ＋別のバグが、巧妙に問題なかったぱたーん Coding Easy (250) 「ガチョウならその周囲もガチョウ」「周囲dist以内の鳥と『同じ種類』」が言える(鳥は2種類なので)。 推移的な「同じ」といえばUnionFind。 そこでUnionFindでグループ分けをする。 …

問題 Editorial 問題 単語列wordsが与えられる。それらを全て含む、長さ最小の文字列の辞書順最小を求めよ 1 1 解答 まず、他の文字列に含まれている関係にある文字列たちを除去する。 この除去された文字列は他の文字列に含まれるので、考えなくても問題の…

神回だった Coding Easy (250) こういう系の問題苦手すぎる。 とりあえず(K (K さて、問題は(K>n-K)の時。 これは考えると(n-K)ごとのブロックに分かれて、(i Medium (500) (サイズ これは半分全列挙できる。 半分の桁までを全列挙し、(各guessesでヒットの…

問題 Editorial 問題 ある文字列のサブシークエンスとは、その文字列から任意の個数の文字を消したものである(連続している必要はない)。 3つの文字列a,b,cが与えられる。この3つの文字列に共通する空でないサブシークエンスの数(同じ文字列は重複して数えな…

問題 Editorial 問題 箱を2*2*heightに積む。 それぞれの箱は独立に、0.5の確率でダイナマイトが入っていて、そうでなければ空である。 「ダイナマイトクラスター」とはダイナマイトの入った箱の集合で、連結なものである(面でのみ接しているとみなす)。 サ…

問題 Editorial 問題 立方体であって、6面がそれぞれ[0..6]の色で塗り分けられているレンガがいくつかある。 2つのレンガが同じであるとは、ある回転をしたときに全ての面が同じ色で塗られていることである。 bricksが与えられる。それらの面を塗り替えて全…

問題 Editorial 問題 略 解答 状態を圧縮する。 スタート・Wの場所のそれぞれ4方向分の状態と止まった状態を考えればいい。 その関係式を行列累乗でやる。 ガウスの消去法で解いても出来ると思う。http://d.hatena.ne.jp/anta1/20130217/1361087344のように …

問題 Editorial 問題 digits つの数字が入る所がある。今入っている数字はdigitsで与えられる。'_'の所は空であることを表す。 '_'の数だけ独立にランダムに順番に数字が選ばれる。 1つの数字が選ばれた時、次の数字が選ばれる前に、どこに数字を入れるかを…

問題 Editorial 問題 xSize*ySizeの矩形領域がある。 領域内のいくつかの場所(x[i], y[i])に「膨張する」円がある。それは、時間tのとき半径tになる。今(時間0)では限りなく小さい。 自分は今(時間0)(px, py)にいる。自分はどんな方向にも1の速さで移動する…

問題 Editorial 問題 略 解答 グラフを作って全点対最短路出して対は全探索。 ダイクストラとか01-bfsしてもいいが、Floyd-Warshall法は十分に速いようだ。 あと、グラフの作り方として辺のコスト = 終点のコストにして最後に始点のコストを足す奴が使える。…

問題 Editorial 問題 辞書dictが与えられる。 この辞書dictに含まれる単語を使ってしりとりをする。 ただし、同じ単語を複数使っても良い。 しりとりをして文字列を作ることが出来る。例えば"abc"と"cd"と"efgh"でしりとりすると"abcdefgh"という文字列にな…

問題 Editorial 問題 2人でゲームをする。 シークエンスの集合sequencesが与えられる。 最初のプレイヤーはsequencesから1つ選ぶ。 相手のプレイヤーは最初のプレイヤーが選んだものとは違うシークエンスをsequencesから1つ選ぶ。 その後ランダムなコインを…

問題 Editorial 問題 無限のグリッドにそれぞれ小文字アルファベットが書かれている。 (i,j)に書かれている文字は(g[i mod R][j mod C] where gはR*Cのサイズ)である。 (0,0)から(x,y) (x,yは非負整数)を通る半直線上の(厳密にその座標を通った)文字を繋げる…

問題 Editorial 問題 数列sequenceが与えられる。 「どれかを1増加させる」「どれかを1減少させる」という操作ができる。なお、マイナスにすることもできる。 最低K個の相違なる数を含ませるようにするとき、操作回数を最小化せよ 1 1 1 解答 Editorialを見…

問題 Editorial 問題 文字列の集合dictionaryが与えられる。 長さnの文字列のうち、dictionaryに含まれる単語を部分文字列として含むものの数をmod 10000で求めよ 1 1 1 解答 行列累乗。 単語へのマッチング状態を状態として持って、次の文字で行く所に+1す…

問題 Editorial 問題 数列initialが与えられる。 これの各々を移動させて、等差数列の並び替えにしたい。ただしそれぞれの数値は重複があってはいけない。 移動させるのに移動させた分だけコストがかかる。 コストを最小化せよ 2 -2*10^9 解答 Editorialを見…

問題 Editorial 問題 任意の平面グラフは交差しない線分だけで描けることが知られている。 平面グラフgraphが与えられる。整数座標上で交差しない線分で描くとき、それを収める(座標軸に平行な)矩形の面積を最小化せよ 1 解答 Editorialを見た。 基本的な方…