サボった A[RG]C の under 2600diff が 18 問にまで上ってしまったため、潰します
https://kenkoooo.com/atcoder#/contest/show/4151fce3-bd45-485f-8373-74ec924d182e
1-6問目はこちら : 自戒ばちゃ(1-6問目) - physics0523's 精進ログ
7. D - -1+2-1 (ばちゃ中7問目, 2300diff, 自力AC)
めちゃくちゃ迷走してしまった…
とりあえず「逆から見る」で $(1,-2,1)$ 加算に言い換える。
また、 $\sum A \neq 0$ のケースは明らかに -1 を吐くべき。
更に、全ての $1 \le i \le N$ に対し $(A_i,A_{i+1},A_{i+2})$ に $(1,-2,1)$ を足す操作をかけても $A$ は不変である。
↑ この話から、 $i=1$ に対する操作を $0$ 回と決め打っても問題ない。(この発想は、cyclic性を消したいというお気持ちからやってくる)
そうすると、ざっと画像のような考察が行われる。
なんと、可能なら操作の回数を (全体に対する定数加算の自由度を除いて) 一意に定めることができて、しかもこの紙の考察を見るとそんなに難しくない。
「操作の回数って非負だよなぁ…」という懸念があったが、一旦負の回数の操作を許したうえで最後に全体にある定数を加算する方針が筋がいい(ことが解けてから分かる)。)
反省点 : 詰まりすぎ！もっと連立方程式に見えるべきだった でも最終的に解けたのはえらいね
Submission #50119257 - AtCoder Regular Contest 129
8. E - Christmas Wreath (ばちゃ中8問目, 2314diff, 自力AC)
詰まったけど切り抜けてからは秒だった。方針選択問題。
ひとまず全探索で $n=6,7$ の解を見つける。 $n \le 5$ は無理なことが問題文 or 辺の総数から読み取れる。
実験コード : Submission #50122038 - AtCoder Regular Contest 131
まず考えた方針は $n=6 \rightarrow 9, n=7 \rightarrow 10$ のように $n$ に $3$ ずつ加算するような方針。しかし、これでは上手く解けず ( $3$ 頂点ずつ足すときに色を偏らせてスターグラフを貼り付けるみたいなことをしたかったが失敗)
しかし、思わぬ副産物があった。
偶然にも一行全部が同じ文字の出力を得た。
ここからよく考えてみると、三角形の $3$ 辺のうち $2$ 辺はこの出力上で同じ行に来ることに気づく。
すると、問題は $(1,2,\dots,N-1)$ を総和が等しいように $3$ 色に塗り分けるというものになった。この塗分け方に従ってその行の色を決めればよい。
帰着した問題について、要素を $6$ つ増やすのは簡単 (012210 の形で後ろにくっつければよい) なので、 $N=6,7,9,10$ の場合について帰着した問題を解けばよく、これは手動でも十分解ける範疇。
Submission #50122236 - AtCoder Regular Contest 131
反省点 : 当初の方針を捨てるのに時間をそこそこ食ってしまった。
9. D - Halftree (ばちゃ中9問目, 2381diff, 自力AC)
解説の図を見たのを2mmだけ覚えていたが、その記憶はそんなに使ってないので自力ということにさせて頂いて…
辺の個数が偶数である必要があるため、 $N$ が偶数のケースは無理。そうでないケースについて作りにかかる。
とりあえず $(x,x+K,x+2K,\dots)$ という数列を書き下してみる。この列が $g=\gcd(N,K)$ 個あったら全要素を尽くせる。図にすると以下のような感じ。
$N=15,K=3$
__0__3__6__9_12__1__4__7_10_13__2__5__8_11_14
この図上で、辺の追加の操作は、「元々の辺」を一列右に動かした辺が「追加される辺」となる…というふうに記述される。
まず考えたのは縦に $\lfloor N/(2*g) \rfloor$ 列結んで余った $1$ 列を処理する方針。頑張ると $2*g-1 \le N/g$ のとき作れるがそれより列数が少ない場合うまくいかない。
なので、縦長を決め打って考察してみる。いろいろ試行錯誤して、遂に図の構成に到達 (あまりに見つからなかったので不可能性を示しにかかるか迷いました…)
列数が大きくてもワルイージの模様状の図形をどんどん足していけば行ける (行数も列数も奇数であることを念頭に置いて構成する)ので、場合分けも減ります
Submission #50123787 - AtCoder Regular Contest 152
反省 : 最初の方針を捨てるのに時間がかかりすぎた(列数が大きいことを利用していたが、小さな場合にもなんとか適用できないか考えすぎた)
「列数が小さい場合」から、その極端なケースである「 $3$ 列を作りにかかる」になかなか至れなかった。とりあえず最小を作りにかかれば迷走避けられたのに何故か $3 \times 5$ から入ってしまったのは(結果論だが)よくなかったかも
10. C - MST on Line++ (ばちゃ中10問目, 2388diff, 自力AC)
頭寝てる状態で通した。なんならまだ頭寝てる。
MSTのアルゴリズムをぼんやり睨む + $A_i$ の値の小さい順に追加していく処理。
$A_i$ の小さい順に追加していく時、繋げる時に繋げるだけ繋げなければ損することに留意。
発想としては「その重みから誰かに繋がねばならぬ」なら寄与は1、更に「その重みで2つの成分を連結せねばならぬ」なら寄与は2。(割と大胆予想)
前者はその重みがある場所を固定して「自分より軽い重みと繋げない」場合を引く余事象、後者は「2つの連結成分がどれだけ離れているか」を固定して積の法則を気合いでやる。
どのように $P$ を取っても寄与が高々2で済む証明は、寄与が3以上かかるケースはさらに改善できるみたいな背理法をすれば良い。
クッソ雑なのであとはコード見てくれ。
Submission #50286034 - AtCoder Regular Contest 167
11. D - L (ばちゃ中10問目, 2394diff, 自力AC)
これ日本語タイトル「く」なんですけど埋めるとLになるんですね
めっちゃ場合分けっぽい見た目だが、とりあえずありうる移動を列挙してみる。
更に、三角形→ひとつのパラメータにしたいという直感が働くので、三角形をその重心で管理できると思い込んで整理してみる(実際これは正しい)。
こんな感じになる。
別の格子に座標変換できそう(まぁ明らかにできる)のでそっちで議論する。よく睨むとだいたいキングの動きだが、線を2本同時に跨ぐことはできない。(とすると都合が良い)
だいたいキングの移動距離を吐けば正解になるが、直線 $x=y$ 上にだけ例外がある。
絶対捨て問枠だと(本番でも今でも)思ったんだけど最小実装考えて書いてみたらかなり軽くて驚き。全然AC可能枠やんけ
Submission #50303408 - AtCoder Regular Contest 109
これ実験想定だったのか、普通に理詰めできちゃったな
12. C - Product Modulo (ばちゃ中13問目, 2496diff, 自力AC)
初めて問題順とAC順が異なる問題。
原始根やるだけってのは覚えてたけど、理解してみると本当に原始根やるだけじゃん
当時の俺マジで物事知らなすぎだろ
