2021/02/18
Battle with E869120!
unrated
好き。(H-1,W)か(H,W-1)に最初に置いた人の負け。全体のマスから(1,1),(H-1,W),(H,W-1),(H,W)を除いたマスの数が奇数なら先攻、偶数なら後攻を選ぶと、(H-1,W)か(H,W-1)に置くことをを相手に押し付けることができる。
リスのお仕事
unrated
(今いる木の番号、直前に飛んだ隙間の長さ)を頂点とした拡張ダイクストラ。計算量が不安。頂点数は高々2*M。辺の数は(M/2)*(M)になる場合がありそう(木が3本あって①-②、②-③にそれぞれM/2本の枝がある場合)。ACがでたし、他の人もこの解法で通してるから間違ってるのかも。すぬけくんの地下鉄旅行が似てるらしい？
ヌクレオチド
unrated
N%2==0のとき、塩基列はa b c d d c b aのようになる。a b c dの中の0の数をxと置く。
転倒数は、(a b c dの転倒数)+(d c b aの転倒数)+x*(4-x)=x*(4-x)*2。
N%2==1の場合も同様に求めることができる。後は数式をこねる。二次方程式の解を求めるライブラリを書いた。詳しくは提出(
https://atcoder.jp/contests/iroha2019-day1/submissions/20243029)に書いた(かなり雑)。
ルーレット
unrated
まとめて計算するいつものやつ。
をあ ぷろぶれむ
unrated
「mid以上の数がK個以上ある」を満たす最大のmidが答え。セグ木上のにぶたんを実装した。上がにぶたん+セグ木(O(N*(logN)^3))で、下がセグ木上のにぶたん(O(N*(logN)^2))。
日記
競プロ楽しい。google hash codeに出ることになった。
