Block Game(AGC050-C)

C - Block Game (問題概要は省略) 実装してて頭ぐちゃぐちゃになったので思考整理。この問題において、 \(B\) がざっくり \(20\) 個強あれば必ずすぬけ君を敗北させられる。(何故なら、すぬけくんの移動可能範囲を \(1/2\) ずつ減らしていけるから) なので…

2020-12-26

Make It One(CFR519-F)

Problem - F - Codeforces \(N\) 要素からなる数列 \(A\) がある。この要素からいくつか選んでその \(\gcd\) を \(1\) とする時、選ぶ要素数は最小でいくつになるだろうか。また、そのように選ぶことが不可能な場合 \(-1\) を出力せよ。 \( 1 \le N,A_i \le…

2020-12-23

TopCoderで、RedCoderになりました

TopCoderで赤くなりました。ここまで5年半、競技プログラミングを始めて2032日目の出来事でした。正直まだ現実を飲み込めてない部分もありますが、この5年半、長かった… AOJに入り浸ったり、JOIで楽しいことたくさんしたり、AtCoderで地獄の停滞を経験した…

2020-12-22

Mysterious Sequence(CC:MYSAR)

Mysterious Sequence \(N\) 要素からなる、数列 \(A\) があります。あなたは、この数列に以下のクエリを尋ねることができます。 Q l1 r1 l2 r2 \( \max(A_{l1},A_{l1+1},...,A_{r1}) - \min(A_{l2},A_{l2+1},...,A_{r2})\) の値を求める。 \( A_1 , A_N \) …

2020-09-14

集合 \({1,2,...,N}\) (\(N\) は巨大) から数を消していきながら、現在 \(k\) 番目の数を求めるテク

突然ですが、次の問題を解きたいです。(これは Move the Coins - Creating Tests の部分問題です。全部やるとむつごいので次の問題だけ取り出します。) \(1,2,...,N\) をそれぞれ \(1\) 個ずつ含む集合があります。以下の \(Q\) 個のクエリを処理してくださ…

2020-08-18

木から頂点を削除しながら連結成分を考える時に、別の木を構成して考えるテク(CC:CHEFCOMP)

Chefina and Strange Tree <問題概要> \( N \)頂点からなる木と、数列 \( P_i , A_i , B_i \) が与えられる。木の各頂点には、カウンターがひとつずつ設置されている。全てのカウンターの初期値は \( 0 \) である。この木に対して、以下のような操作を \( …

2020-07-03

こどふぉWriter体験記 ~ 競プロ公式コンのつくりかた

先日、私がいわゆる公式な(Ratedな)コンテストとしては初めて、Writerを務めさせて頂いた Codeforces Round #654 (Div. 2) 、お楽しみいただけたでしょうか? 参加できなかったという方も問題に挑戦していただけると嬉しい気持ちになります。さて、今回はコ…

2020-04-08

Complexity(AGC033-D)

D - Complexity 解説と少しだけ方針が違ったのでメモ。ある縦の行の区間 \([i,j]\) と、左端をとる列 \(k\) を固定して、(複雑さ \(x\) を考慮するときに)とれる右端の最大値を dp[行の区間 \([i,j]\) ][左端をとる列 \(k\) ]={可能な右端の最大値(存在しな…