はてブロmarkdown対応始めたってマジ？数式書けるの最高だね 今月解いた青Diff以上について書く
ARC145-C Split and Maximize (Diff: 1697)
よく見るとカタラン数
Submission #57587994 - AtCoder Regular Contest 145
ARC145-D Non Arithmetic Progression Set (Diff: 2297)
2進数を3進数として読んだ数列は等差数列を含まない
適当に $N$ 個取ったとき総和が $\mod N$ で $M$ と等しければあとは全体加算で何とかなる 総和を何とかするのは乱択で辻褄合うまでやる（インチキ）
Submission #57588757 - AtCoder Regular Contest 145
ARC134-D Concatenate Subsequences (Diff: 1998)
基本的に前から貪欲でいいが、細かい条件を合わせるのが大変すぎる
$1 \sim N$ を上段、 $N+1 \sim 2N$ を下段と呼ぶことにする。上段の最小値を$X$とする。$X$とペアである下段の要素のうち、$X$以下のものがあればその最小だけ取って終わりにする。そうでないとき、上段が$X$のペアは全て採用してしまう。このときの下段の先頭要素を$L$とし、上段の残りについて考える。$L$ より小さければ全て採用してしまう。 $L$ と同じとき、下段の要素で初めて現れる $L$ 以外のものを $Y$ としたとき、$L<Y$ なら全部採用、そうでないなら全部無視する。
Submission #58114969 - AtCoder Regular Contest 134
ARC136-C Circular Addition (Diff: 2137)
- 自明な上界1: 要素のmax
- 自明な上界2: $\sum \max (0, a[i+1]-a[i])$
実はこれのきつい方が常にいけます マジ？
Submission #58117605 - AtCoder Regular Contest 136
ARC136-D Without Carry (Diff: 1908)
6次元累積和
Submission #58131075 - AtCoder Regular Contest 136
よく考えると6次元の添字は6個の数字を連結した数とみなしてよく、そうすると高速ゼータ変換と一緒
ARC139-B Make N (Diff: 1719)
解説は平方分割だったけどmax:1000で場合分けした
Submission #58138560 - AtCoder Regular Contest 139
ARC139-C One Three Nine (Diff: 2406)
$(x,y) \mapsto (x+3y, 3x+y)$ と変換した後の座標系で考える。元の長方形領域は変換後の平行四辺形であり、 元の制約は変換後の $(X,Y)$ について$X$ [resp. $Y$ ] 成分が相異なるように選ぶという制約に変換される。 各点は $\mod 8$ で独立なので $\mod 8$ で別々に解いてよい。$X$ の小さい方から見ていき、$Y$ はそこで取れる最小のものを選んでいけばよい。
Submission #58148318 - AtCoder Regular Contest 139
ARC131-E Christmas Wreath (Diff: 2314)
$x \to y, x \to z$ みたいな辺があれば、$y \to z$に何が来ようともその三角形が条件に抵触することがなくなる。 $i$ を固定して$i < j$ であるようなペア全てに同じ色を割り当てることを考える。これが成功すれば条件に抵触する三角形は存在しないことになる。実際これは $6 \leq N$ かつ $N \mod 3 \neq 2$ なら構成でき、部分和DPして復元すればよい。
$N \leq 50$ なのにTL3秒の謎を解くと解法まですぐだった
