AtCoder:橙
Joined February 2019
- Tweets 5,957
- Following 400
- Followers 386
- Likes 332
31 Photos and videos
15h
CodeChef START243A
STRSEAT:2乗で間に合う
OROPS:貪欲
GCDARR2:「[0,n-1)のgcdが2以上」かつ「[1,n)のgcdが2以上」であるものの個数から「[0,n)のgcdが2以上」であるものの個数を引いたものが答え。前者は[1,n-1)のgcdを全探索し、両端に1個独立に付け加えるようにして数え上げ。
BINFLIP3:差分で考え
1
1
124
15h
ると00<->11という変換であり、奇数番目を反転すると1を隣へ動かす操作と見なせるので、1の配置を考えることで数え上げられ、1の個数にのみ依存。1の個数ごとの場合の数が求まればよい。左端右端を定数に固定しておくと、-1からなる極大区間は必ず左右を定数で挟まれる。区間の長さごとに1の個数の分布
1
109
Jun 15
OMCB082
A:ACとBDの交点をEとすると∠AEB=30°で、これとAC,BDだけで面積が決まる
B:3,4,5の回数は(15,0,1),(14,2,0),(12,1,2)の3通りだけ。3の間に4,5を挿入する要領で数え上げ。
C:2n/199-3n/299>=1⇔n>=199*299では不適だから0<n<199*299で考える。余事象を数え上げ。3x/299<=y<=2x/199内の格子点が
1
111
Jun 15
不適なnに対応で、この領域の格子点の個数は、直角三角形内の格子点の個数の差で求まる。
D:下4桁が2025のとき5で割り切れる回数は2回なので、k=1 or 2。k=1の場合は簡単。k=2の場合、n=5m (m<2000)と置くとn^2≡2025 (mod 10000)⇔m^2≡1 (mod 16)かつm^2≡6 (mod 25)に落ちる。
71
Jun 14
任意のクソデカ頻度列で解く方法があるのかと思ってたらそこを使う問題だったのか
xor convみたいなことは絶対必要だからFWTした状態で時系列順にうまくセグ木を管理（？）してとか考えていて不可能になっていた
1
93
Jun 14
ARC222
A:max_i ri-li 1 が自明な下界で達成可能
B:0人の手が存在する場合は簡単。そうでないとき、グーがx(>0)人勝つにはチョキはx 1人使う必要があり、これらのチョキは勝者になりえない。これを、「最初チョキ1人分使ったら、(グー,チョキ)を1ペア使うごとにスコアを 1できる」と見なす。グー、チョ
1
2
112
Jun 14
キ、パーそれぞれ最初に1人分使うかで場合分け。
C:Bobのターンで駒の隣接マスは全部白である必要があるので、Alice操作後隣接マスが全部白に変わると見なせる。各行少なくとも1マスはAlice操作後に到達することになるマスで、その左右マスは白になる。各行どのマスに到達させることにするかを決めたと
1
1
96
Jun 13
ABC462
A,B:はい
C:x座標昇順に見ていくと、y座標の累積minを更新する点が条件を満たす
D:ti-si<dであるような人iは無視。そうでない各人について、犯行開始時刻としてあり得るのは[si,ti-d]の区間。この区間の重なりを考える。イベントソート。
E:お気持ち貪欲。(X Y)%2が奇数なら初手全探索すること
1
1
2
160
Jun 13
持ったDPを考えた時、「何も操作しない場合のABCの個数」未満の箇所は無視してよい。また、K 1個分多くなっていたら以後は操作しなくてもK個以上勝るので、その個数より上は見なくてよい。
G:ABL-Fと大体同じ。条件を満たすCとGの完全マッチングの個数が分かればよい。Ci=Gjなる各(i,j)について
1
118
Jun 10
CodeChef START242A
EQMNG:答えは高々3だから0,1,2にできるか判定
SPLDIF:a[i]の分解は(1,a[i]-1),(a[i]-1,1),(a[i])の3通りだけ考えればよい。DP 復元。
BINBSR:操作によって一番左の1が末尾に移動するとみなせる。区間set。
TWRUP:時間切れ。dp[i][t]=「i wave終了後にT=tたり得るか」でDP。
1
1
139
Jun 10
⌈H/t⌉⌈A/p⌉<=Sは、X:=⌈H/t⌉,Y:=⌈H/t⌉とするとXY<=Sなので(X,Y)としてO(√S)点だけ考えればよい。bitsetで高速化したいが、区間をコピーしたいので自力で書く。
114
Jun 7
Codeforces Round 1102
A:降順ソートしてチェック
B:aをなるべく小さくする。mod 12ごとに最小の回文数を求めておけばよい。
C,F:各値を位置とpairにするなどしてdistinctにしておく。時計回り・反時計回りへの、最大値に到達するまでの累積maxの総和が答え。
D:ありうる値は4通り。
1
1
208
Jun 7
dp[k][左側の値][右側の値]でDP。
E:Cartesian Treeが一意に作れるので挿入DPで数え上げ。
G:解けず。状態は(位置, power)の2次元で表せ、負け状態の個数はO(nlog(n))個だから、負け状態を高速に全列挙できれば良さそう。位置を降順に見ていくことにすると、x軸方向への移動によって状態に辿り着けない
1
159
Jun 6
(1,i)->(2,j)に向き付け、黒ならば逆に向き付けされているとみなす。各クエリで自身に向き付けされている辺の本数が分かれば答えを差分更新できる。これは、前回の自身へのクエリから今回のクエリまでの間に、何種類反対側の頂点が選ばれたかが分かればよい。更新最新の位置だけ 1するようにすれば種類
1
95
Jun 6
数は部分和として得られる。
F:各長さLについて、長さLの単調増加列に対するスコアを*L!して足せばよい。dp[d][v]=「現在の総積がd、最後に選んだ値がvであるときの(個数, 総和)」でDP。Lは20程度まで見れば十分。
75