実に5ヶ月ぶり、今年最後のSRM。 8月はSWoPPといろいろ、9月は旅行いったりなんだり、後半から12月頭まではSCとその後処理 としばらく参加できていなかった… 結果 o--(+0/-0) 228.60pts 219th 1959->1965(+6)維持できてよかった。 250 MonstersValley 典型的…

練習です。 250 ColorfulChocolates 文字列が与えられて、隣接する2つをmaxSwap回swapしたときの 連続する同じ文字の最大の長さを求める。方針は2つ 同じ文字に注目して、中央にあるものに寄せるときのコストといくつくっつけられるかを計算 区間を決めて、…

結果 o--(+0/-0) 224.08pts 60th 1782->1886(+104)Highest更新して初の1800台到達！ 600 Magical Hats Medも解けるようになっていかないといけないのでMed Openしてみた。 英文が読みづらい…要はコインが入っている場所を絞り込んでいくみたいだけど コイン…

結果 o--(+2/-1) 318.87pts 53rd 朝SRMで人が少ないけど、最高順位更新。レートは1594->1731で1700台復帰。 250 Pillers 問題 2本の棒が距離wで立っている。 棒の高さはそれぞれ[1,x],[1,y](1 棒の先端同士の距離の期待値を求める。 解法 高さが等しければ距…

結果 ---(+0/-0) 0pts 353th 1768->1660 (-108) 大敗北 275 よくわからない…総票数kと仮定すると得票数vは k*(p[i]-0.5) 500 Greedyにやっていけばよい。こっちのほうが簡単じゃないか！訴訟！ 感想 人権less

結果 o--(+0/-0) 232.13pts(192nd) 1705->1768(+63) またもやhighest更新です。Petrとはじめて同部屋でした。 250 各bitごとに調べていった。 下から[a,b]のxorを取ったときの下からkbit(0-indexed)目は (([0,b]の下からkbit目が1の個数)-([0,a-1]の下からkb…

結果 不参加でした。 250 xy平面上(0 a->b->c->aの道のり(移動は軸に並行のみ)がminT以上maxT以下になる a,b,cの置き方の総数を求めよ。という問題。a,b,cの道のりはa,b,cを内包(辺上を含む)する最小の長方形の周の長さに等しい。 ┌--A--┐ │ | B | └-----Cイ…

結果 o--(+0/-0) 149.02pts 310th(Div.1) 1629->1671(+42)またもやhighest更新！ 250 n匹(n アリ同士が衝突すると消える。最終的に残るアリの数を答えよ。はじめは任意の異なる2匹のアリがぶつかるかどうかが解るので時系列順に出して 云々かなぁと思ったも…

結果 o--(+4/-0) 282.82pts 58th(Div.1) 1481->1665(+184)Highest更新 && 黄色到達 && Div.1初2ケタ！ 250 A[0]を決め打ちすればBを満たすAは一意に決まる。 またA[0]を1増やした時にA[k]が増加するか減少するかは 符号列によって決まる。例えば B: + - + 3 …

随分空いてしまった。 結果 oo- 381.48pts 1344->1436(+92)Highest更新&&初midpassed(450だけど) 250 xy平面上にある点の集合に対し、(0,0)を出発点として全ての点 を任意の順で訪問するとき、歩数のparity(偶奇)が与えられたものと 一致するような訪問順が…

300-450-1000という変則セット。 結果 o--(+0/-0) 142.27pts 314th(Div.1) 1224->1320(+96) 300 DengklekMakingChains 300は怖いなぁと思いつつ問題読む。3つの{.|0-9}からなる文字列が与えられ、それを任意の順番でconcatしたときに できる連続する数字の和…

問題 xy平面上の(i,0)に高さh_i(i=1,2,...,n)のn本のビルがあるとき、あるビルから見える他のビルの屋上の最大数を求めよ 方針 あるビルに注目したときそのビルから左右方向に別々にループを回すのはめんどいので ビルiからビルjの屋上が見える場合その逆も…

方針 N本のボトルを運ぶときの最小の本数==Nの立っているビットの数 なので、ビットカウントをしてそれがKより少なければ運ぶことができる。これを1本ずつ足していって調べてみればよい。 足す本数は、多く見積もっても2^k ビットカウントにO(logn)掛かると…

問題 整数nが与えられる。 0,1,...,n-1行にそれぞれn-1,n-2,...1個のスペースがあるとし、左詰めで箱を詰める。 ただし、i行目の箱の数a_はa_i>a_j(i 方針 要は下に行くほど少なくなっていけばよい。 n-1行は0個か1個なので dp[0][0] = 1; dp[0][1] = 1; と…

結果 o--(+0/-0) 157.5pts 461st(Div.1)レートは 1221->1256(+35) 何とか年越しを青で迎えることができました。 250 うなぎ切るよ！ 10nな長さのうなぎはn-1回切ると長さ10のうなぎがn本取れるのでお得、なので 長さが10の倍数のものを小さい順に、そうでな…

結果 oo- (+0/-0) 478.37pts 105th(Div.2) 1190->1221(+31)Div1復帰しました。 250 MagicStonesStore ゴールドバッハ予想を使うとちょっと楽になるらしい。 sieveしてから全探索、引数nに対して2*n個というのを初め忘れていて提出が遅れた。Passed System Te…

結果 ---(+0/-0) 0pts 1251->1191次回はDiv.2。 300 外側から切っていくということは残せるのは長方形なので、 任意の部分長方形についてその内側をカウントすればいいのだが、そこからそれを残すために移動する回数を求める方法を考えて迷走した。 任意の部…