Sequence (BalticOI2004-3)

https://www.acmicpc.net/problem/13323

https://www.acmicpc.net/problem/13324

[BalticOI 2004] Sequence 数字序列 - 洛谷

長さ $N$ の整数列 $A=(A_1,A_2,\dots,A_N)$ が与えられる。

狭義単調増加整数列である $B$ であって、 $\displaystyle \sum_{i=1}^{N} |A_i-B_i|$ が最小となるものを求めよ。

$1 \le N \le 10^6$

考えやすいように、 $A_i = A_i-i$ と見做して議論する。このもとで、 $B$ は広義単調増加整数列という制約に変化する。

初手からわからなかったのでヒントを頂く。 

题解-BOI 2004 Sequence - oier_hzy - 博客园 に中央値というワードがあったので、それをもとに考察開始。

確かに、全体をひとつの値で揃えるべき状況であれば中央値に揃えるべきである。

しかし、このとき例えば $(5,5,5,5,8)$ みたいな状況で全体を $5$ 揃えてしまうとロスが出る。

このもとで、どこまでが中央値以下でどこからが中央値以上か… みたいな問題を考察しにかかる。

しかし、なんとこの時点で「中央値」という要素を捨てないとこの先の解法が頓挫してしまう。自分はこの後も「中央値」に拘り過ぎて迷走した。

本当に考察するべき問題は、「どこまでが $x$ 未満」「どこからどこまでがちょうど $x$ 」「どこからが $x$ 超過」の判定問題。

「どこまでが $x$ 未満」という判定問題を考察するにあたって、 $L < R$ なるふたつの整数に対して、接頭辞 $(A_1,A_2,\dots,A_L)$ と $(A_1,A_2,\dots,A_R)$ とを比較する。

区間 $S = (A_{L+1},A_{L+2},\dots,A_R)$ に含まれる $x$ 未満の要素の個数を $C_{<}$ 、 $x$ 以上の要素の個数を $C_{\ge}$ とする。

• $C_{<} < C_{\ge}$ であれば、 $S$ を「 $x$ 未満」に割り当てていたのを「ちょうど $x$ に割り当てることで解が改善する。」
• $C_{<} = C_{\ge}$ であっても、 $S$ を「ちょうど $x$ 」に割り当てるに比べて 「 $x$ 未満」が改善することはない。
• $C_{<} > C_{\ge}$ であれば、 $S$ を「ちょうど $x$ 」に割り当てていたのを「 $x$ 未満」に割り当てることで解が改善する(例えば、全部 $x-1$ にすればよい)。

よって、 $x$ 未満の要素を $+1$ 点、 $x$ 以上の要素を $-1$ 点として最高得点を叩き出す接頭辞のうち最も短いものを「 $x$ 未満」に割り当てることが最適である。

「 $x$ 以上」についても同様。また、「 $x$ 未満」の接頭辞と「 $x$ 以上」の接尾辞が交わることもない。

あとはこれを再帰的にやることで、 $O(N \log A_i)$ でこの問題に正解できる。

luogu の形式に従ったACコード: https://ideone.com/SYavXR

slope trick 使っても行けるらしい。考えもしなかったな…

行けました めんどいので復元抜き https://ideone.com/KfZU6X

AtCoder Regular Contest 174 Writer記

この世で最も愚かなレート遷移

AtCoder Regular Contest 174 - AtCoder

ARCの単独Writerができたので、くう疲みたいな怪文章をこの世にひとつ増やしたいと思います。

コンテスト観戦総括

Aはかなり素直なARC-Aなので、2080AC出て安心。
Bは予想以上に通された印象。ただBC間が大きく開いているので A=B は割と成功しているのか?
C は思ったよりもやや通されなかった印象。 CD逆転ルートはありうるケースの1つとして想定済み。
C は無限和の処理に困ったんだろうなと感じられる。ただDとひっくり返るのは人々の観察眼が冴えすぎてる?
D は実験やるだけなので、「実験やってよ～」と念を送ってあげたかった。
E は予想より少し多い AC count。やっぱ得意なんですね…
F は開始 101 分時点で FA と肝を冷やす事態に。これそんな難しかったのかな…

Fが>=20ACになるかと思いきや蓋を開けてみれば2AC、全完が1人というunexpected 劇的な展開に。

作問傾向について

今回は自然界から物凄く素直に作問した問題が多いので、「物理好きはこういう問題作る」の参考にならないと思いますw
正直に言うと、普段のARCらしくも、普段の僕(yukicoderのアドベコンのアルゴ問とかABC200とかで最も強く自分らしさが出てると思います)らしくもないセットが出てきたんじゃないかなと思っています。

セット組みの流れ

現DEFを含むセットをCDEFのうちCを含む3問埋まればいいかくらいの気持ちで投げると、まさかの最も上の難易度帯で通った。そのため最後まで「このセット簡単だろwww」を恐れる事態に。
その後、簡単枠として現Cを追加、新たにABを生やしてセット完成。

各問題のお気持ち部分について

A(予想200diff):
簡単枠、やること自体は ABC-CD 級です。とはいえ素直なARC-Aとしてかなり良いものが置けたのではないでしょうか。

B(予想900diff):
沼る人は沼りそう、ただカンでも当たりそうということで900diff予想。
難易度は恐らく400相当だが、全体のゲームバランスやtester体感などを参考に300に移動。

solved.ac の難易度投票システムって、現在のTierから5段階以上離れた評価を付ける際はコメントが必須になるんですよ。
という訳で、この「投票」と「手間」を「レビュー」と「賄賂」に言い換え、面白目な設定に持ち込んで完成。

C(予想1600diff):
立式と無限和を正しく処理出来れば3点枠、処理できなければ苦しいか。

YouTuberの動画を漁っていたところ、ルーレットを回して
・今まで出ていない目には褒美がある
・今まで出た目には罰がある
・全部出るまで終わらない
というまんまな設定があったので、そのまま問題になりました。

D(予想1600diff):
お　ま　た　せ
い　つ　も　の
春　の　一　発　ギ　ャ　グ　祭　り
本当は任意進数だったり $N$ の桁数がもっと大きかったりしたのですが、単純に訊きましょうということになり超一発ギャグに。
実験する発想に至れるかの一発勝負で、コンテスト進行によっては AC count が C<<D になるのではとも思っていました。

あるときふと「平方根をすっごいサボって接頭辞で近似したら爆速なんじゃないか」という愚かな考えが浮かびました。
その結果、近似精度は本当にダメダメだったのですが代わりに面白い挙動が得られたので問題に。
証明はめちゃくちゃ受験整数です。やる気があるなら頑張ってみてください。

E(予想2300diff): 
割とムズイ、割とムズイし橙白抜きくらいになって欲しいが日本人はこの手の数え上げが得意なので…
数え上げにしてはかなり珍しい、良心に従った方針でそのまま正解できる問題になっていると思います。

Wikipediaを漁って遊んでいると、「投票券(公営競技)」の項目の中にかなり心ときめく図があり、図中の任意の長方形に含まれる赤マスの数を数えたくなりました。
その後設定を「集合」から「順列」に変えて各要素の頻度を尋ねる今の形に。

心ときめく図

F(予想3000diff): 
ARC-Fにしては異例なデータ構造+実装ゲーになっていると思います。そのため従来のFより通されて3000diffくらいに落ち着くんじゃないかと予想していました。
ゲームの解析も大事っちゃ大事なんですが、むしろそれが終わって後退解析をどう実装するかが本質です。

これもYouTuberの動画を漁っていたところ、「N言っちゃダメゲーム」を3人以上で行っているシーンを見ました。
競プロerなら当然「このゲームにおいて複数人が結託した場合にどうなるか」を解析したくなるのが性でしょう。(?)
この「複数人」の設定が「1ターンに取れる石の数の制約」として再現され、今のゲームに。(元々は本当に複数人結託させる問題文でした)
最初は同じゲームを扱った少し異なる問題でしたが、破綻していたことが発覚して今の問題に。

ARC、そんなにたくさん生えるものではない(特に、今回のように自然界を研究して高難度にするパターンなら尚更)ので、年1くらいでやれれば最高かな～くらいの気持ちです。今回だけで撃沈しないように頑張ります、マジで。

最後になりましたが、ご参加頂き誠にありがとうございました！

physics0523's Training #1

https://kenkoooo.com/atcoder#/contest/show/4f518dfd-5208-4ed6-b193-d3cfb60f8ab0

1. C - Add Mod Operations (ばちゃ中2問目, 2500diff, 自力AC)

とりあえず $(A+x)\%y$ という操作を観察する。

気付き1: 適当に操作をかけても $A_i-A_{i+1}$ の値は変えにくいので、これを無理に変えに行く必要がある

気付き2: 片方が $\ge y$ 、片方が $<y$ でないと $A_i - A_{i+1}$ の値は変えられない

気付き3: 最大の $1$ 要素だけを $\ge y$ にすることで、最大の要素だけをうまいこと調整できないか?

気付き3-1: ↑この操作を使えば、「まだ一度も $\ge y$ に直面していない要素」の大小関係は保存できそう

例えば $7 \rightarrow 3$ としたいとき、大きい定数 $big$ をとって $x=big-4, y=big$ とでもすれば実現可能。

更に言うと、全ての要素をたった一度だけ $\ge y$ に直面させると、 $a \rightarrow b$ と変化させたいときに ( $\ge y$ のタイミングが回ってきたときに ) $big - (b-a)$ だけ値を捨てさせればよい。

また、この $big$ を十分大きく取れば、たとえば $k$ 回目の操作で $k \times big$ のように運用しても ( $\mod big$ を最後にとるものとして ) 正しい結果が得られそう。

最後に全体にある値を足して $\mod big$ する (オフセット調整) ものとすれば、ひとまず $N+1$ 回が構成できる。

あと $1$ 回をどう削るか? 答えは、もともと $A_i$ が最小であるものについて値を捨てさせなくてもいいように、他の $A_i$ に対して捨てさせる値を調整すればよい。

これで $N-1$ 回でオフセット調整以外が完了して、この問題に正解することができる。

これ以上の詳細は実装にて。

Submission #50499455 - AtCoder Grand Contest 063

ゆっくり時間をかければ詰め切れるんだけどなぁ系。 3h だと焦って見えなくなるだけで最近のAGC-Cにしては弱いんかな…

自戒ばちゃ(13問目-18問目)

サボった A[RG]C の under 2600diff が 18 問にまで上ってしまったため、潰します

https://kenkoooo.com/atcoder#/contest/show/4151fce3-bd45-485f-8373-74ec924d182e

1-6問目はこちら : 自戒ばちゃ(1-6問目) - physics0523's 精進ログ

7-12問目はこちら : 自戒ばちゃ(7問目-12問目) - physics0523's 精進ログ

13. E - Examination (ばちゃ中15問目, 2553diff, 自力AC)

可能かどうかの判定は sort してやるだけだが、この考察はそんなに正解に繋がらない。

「今持っている点数が $A_i$ 点の人が、 $B_i$ 点以上取らないと留年」という設定なので、一旦すべてを $2N$ 個のイベントとしてソートしてその順に処理することを考える。

「 $B_i$ 点以上取らないと留年」を捌きやすいのは昇順ソート(一度入ってしまえばそのあと永遠に条件を満たし続けるようにできるので)。

ということで、制約を先に入れて得点が現れた時に好きな制約にマッチングすれば判定問題の別解が得られる。

あとは得点が変わらない人間の数の最大化。やるべきことを以下の二通りに分類する。

• 生徒 $i$ の得点が出てきたとき、生徒 $i$ の制約とマッチ
• 生徒 $j$ の得点が出てきたとき、生徒 $j$ の制約とはマッチできないので誰か適当な人間の制約とマッチする

まず、(得点昇順イベントソートの下で)得点が制約とマッチできるならして損しないことが示せる。

そのうえでマッチ可能性の判定は「全ての時点での残っている制約の個数を管理し、マッチングを作る際に【残っている制約の個数が負になってしまうような時点】ができないかどうか」で判定でき、これは遅セグを使うと実装できる。

Submission #50313460 - AtCoder Regular Contest 147

ドブ系だと思ったけど案外すんなり通せて偉いね

14. D - Neq Neq (ばちゃ中16問目, 2554diff, 自力AC)

とりあえず $A_i$ に同じ要素が隣接していたらどちらも消せない。

しかもそれらを超えて要素が干渉することは無いので同じ要素が隣接する点で問題を分けられ、各問題中には同じ要素が隣接する点は無い。

このもとで、要素の取り出し方が何通りあるかを調べる。

まず、先頭と末尾は絶対に消せない。このもとで、 dp[最後に選んだ要素]={場合の数} をしようとする。

1つ前と2つ前からは絶対に遷移できるが、それ以外の遷移はどうなるか?

実は、遷移元と遷移先の要素を含めて、飛ぶ区間に要素が $3$ 種類以上あれば遷移でき、そうでない時は間1軒までしか遷移できない(もっとも、要素が $2$ 種類なのは ababab... のパターンしかない かつこの事が証明に活きる)ことが示せる。

要素が $3$ 種類以上あると遷移できるが、そのような区間は尺取なりsetを活用するなりでどうにかできる。自分がどうしたかは実装を見てほしい(説明するのがめんどいので)

Submission #50323825 - Daiwa Securities Co. Ltd. Programming Contest 2021 (AtCoder Regular Contest 128)

これ解けるようになったの我ながら偉いなぁ

15. D - Sum of Min of Xor (ばちゃ中18問目, 2593diff, 自力AC)

$A_i$ の下から $d$bit 目を $A_{i,d}$ みたいに書く。

上の桁から見た時に $A_{i,d} \neq A_{j,d}$ と $B_{i,d} \neq B_{j,d}$ の丁度一方が成り立つとき $A_i \oplus A_j$ と $B_i \oplus B_j$ との大小関係が決定づけられる。

この条件をこねると、 $A_{i,d},A_{j,d},B_{i,d},B_{j,d}$ のうち奇数個が $1$ であると言い換えられ、更に言い換えると $C_i= A_i \oplus B_i$ としたときに $C_{i,d} \neq C_{j,d}$ が成り立つと言い換えられる。ここが最重要考察。

ここまで来ればウィニングラン。 $C_{i,d}$ を上の桁から調べて、こいつで問題を分割していく。但しだいぶねっとりしてるので詳細を全て書き留めることはしない。

Submission #50433859 - AtCoder Regular Contest 127

割と地力でどうにかなるのにここまでdiff高いの意外だな、この手の問題の考察/実装速度上げたい。

自戒ばちゃ(7問目-12問目)

サボった 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順が異なる問題。

原始根やるだけってのは覚えてたけど、理解してみると本当に原始根やるだけじゃん

当時の俺マジで物事知らなすぎだろ

Submission #50312661 - AtCoder Grand Contest 047

自戒ばちゃ(1-6問目)

サボった A[RG]C の under 2600diff が 18 問にまで上ってしまったため、潰します

https://kenkoooo.com/atcoder#/contest/show/4151fce3-bd45-485f-8373-74ec924d182e

1. B - Insert 1, 2, 3, ... (ばちゃ中1問目, 1663diff, 自力AC)

本番でめちゃくちゃ詰まって絶命した問題。

ひとまず、ある数列 $A$ に対してそれが valid かどうか判定することを考える。ここで嘘にハマりやすいので注意。

例えば (1,2,3,1,2,3,4,5,1,2) は valid だが、この後にひとつ要素が来るとしてその要素で場合分けする。

• $1$ が来たら valid。
• $2$ が来たら invalid になる。
• $3$ が来たら、この $3$ は 1,2 に続くので valid。
• $4$ が来たら、この $4$ は 1,2,3 に続くので valid。
• $5$ が来たら invalid になる。
• $6$ が来たら、この $6$ は 1,2,3,4,5 に続くので valid。
• これ以外が来たら invalid になる。

ここで、例えば $6$ が来た時は 1,2 はもう使えなくなる。

また、 (1,2,3,1,2,3,1,2,3,4) から 4 が来た時のように、続けられる列が複数通りある場合は最も後ろにあるものに繋げて損をしない (=そのように選ぶことで、 valid な列を最長化(最も好意的に解釈)できる)。

また、求める区間 $[L,R]$ を数えるにあたって当然 $A_L = 1$ であるが、どの $A_L = 1$ から始めても $A_1$ から判定した状態の接尾辞が現在の判定問題の状態となる(伝われ)。

よって、以下の解法が成立する。

• 最初、空の stack を用意する。
• $A$ を $1$ 要素ずつ読み込み以下の判定を行う
  • $A_i = 1$ なら stack に $1$ を突っ込む。
  • そうでないなら、 (取り出した要素) $+1  = A_i$ となるまで要素を取り出した後、 $A_i$ を stack に追加する。
    • そのような要素が取り出せなければ stack を空にする。
  • この後、答えに現在の stack のサイズを加算する。

Submission #50085600 - AtCoder Grand Contest 063

ハマりにくいとは言わない(後ろから考えてみたり、微妙に違う判定法に落ち込んだり、ある要素の次に来る要素がどこになるかみたいなことを考えたり…)が、なんで本番でハマり散らかしたんだろ…

本番での反省 : 判定問題を徹底的に詰めて、一般化する方針を取ればよかった

解説では後ろからやる方針だったので、そちらも一応実装。自分は前からの解法の方が自然と感じたが、こっちの方がちょっと証明が楽かも。

Submission #50086034 - AtCoder Grand Contest 063

2. C - Not So Consecutive (ばちゃ中2問目, 2005diff, 自力AC)

なんで落としたんだろこれ… ちょっと時間かけて冷静になれば詰め切れました

dp[ $i$ 個目まで決めた ][ 末尾の要素 $A_i$ ] = { 場合の数 } の方針で押せる。

いったん $k$ が $k+1$ 個以上並んではいけないという制約を無視して遷移をかけた後、 $i$ 項目を置いたせいで初めて $k$ が $k+1$ 個並んでしまうような場合の数を引く。

これは、 dp[ $i-(k+1)$ ] の総和を引いた後に dp[ $i-(k+1)$ ][ $k$ ] を足せば遷移ができる。但し、実際に $k$ が $k+1$ 個並べられるかの判定が必要。これは予計算で $O(N^2)$ かければできる。 (区間内の値が全て -1 か、区間内の値が全て (-1 or x) か、それ以外 を予計算で全区間に対して判定すればよい)

Submission #50087017 - estie Programming Contest 2023 (AtCoder Regular Contest 169)

もっと速い解法があるらしいがこれは後で勉強します(こういうことしてるからダメなんだろうなぁ)

3. C - Sequence Scores (ばちゃ中3問目, 2056diff, 自力AC)

主客転倒。操作回数に寄与しない項を数え上げる方針で行く。

• ある要素 $x$ について、それより前に $x$ がなければその要素は操作回数に寄与する
• そうでなくとも、その直前の $x$ との間に $x$ 未満の要素があればその要素は操作回数に寄与する
• そうでないとき、今着目する $x$ と直前の $x$ とはまとめて操作できるため、今着目している $x$ は操作回数に寄与しない。

ここまでくると場所 $i$ と要素の値 $j$ を固定して主客転倒できる。 $k$ を場所 $i$ の直前に出現する $j$ の位置として全ての $k$ に対する和を高速に求めたくなるが、これはちょっと式をいじると等比数列の和になる。

$O(NM \log \rm{mod})$ (TLE): Submission #50088601 - AtCoder Regular Contest 114

メモ化して $O(NM)$ に落としてAC: Submission #50088710 - AtCoder Regular Contest 114

これ本番提出すらないけどなんで解けなかったんだろ…

4. D - Binomial Coefficient is Fun (ばちゃ中4問目, 2078diff, 自力AC)

明らかに積の和典型。積の和を復習してから解いた。

$C(B_i,A_i)$ は $B_i$ 個の区別可能な球の中から $A_i$ 個を塗る場合の数である。

素直に考えると球 $ M $ 個、仕切り $N$ 個から各領域に対して $A_i$ 個の球を黒く塗るが、これだとうまく行かない。

順番を逆にしてみる。例えば $A=(3,1,2)$ だと xxx|x|xx| をまとめて ? というオブジェクト $9$ 個に置き換える。これを $M-6$ 個の oo...o の中に挿入すれば求めるべきものとの1対1対応が完成する。

結局、求めるべきものはひとつの二項係数になる。

Submission #50088870 - AtCoder Regular Contest 110 (Sponsored by KAJIMA CORPORATION)

5. D - Inc, Dec - Decomposition (ばちゃ中5問目, 2143diff, 自力AC)

割と大胆予想を当てた感がある。

ひとまず $A$ の差分に着目して、 $A$ が $+x (x>0)$ する時を考える。この時 $\Delta B = x+P, \Delta C = -P$ とするべきだが、実は $P=0$ の場合以外は考えなくてよいのではという予想が立つ。

この予想が成り立つと仮定すると、 $B$ の初項を固定すれば他も全部決まってしまう。

より具体的には $B$ の全項を $-1$ 、 $C$ の全項を $+1$ するだけしか自由度が残らず、要素の絶対値の和の最小化は中央値を使えば解けるみたいなやつになります(クソ雑)

多分先ほどの $P \neq 0$ の場合を扱うぐらいならこの自由度で調整した方がお得みたいなことが証明になるんでしょうけど正確には示せず、ただ AC は自力できました

Submission #50105793 - AtCoder Regular Contest 123

追記(?) : 背理法でやったらええんか… Editorial - AtCoder Regular Contest 123

6. D - Binary Representations and Queries (ばちゃ中6問目, 2282diff, 自力AC)

とりあえず問題を理解するためにこのような図を書いた。

$N=3$ の場合に、操作はこの立方体の軸をひとつ選んで、その軸に平行な全ての辺に沿って加算が行われる。

この図をギン目で睨みつけると、次のことがわかる。

• 操作を軸ごとに独立に扱えないだろうか?

dp[ $i$ bit目 ][ 操作元のbit ][ 操作後に辿り着くbit ] = { 寄与を表現する係数 } みたいな配列が求められる。

dp[ $i$ ][0][0]=1, dp[ $i$ ][1][1]=1, それ以外=0 と初期化して遷移は dp[ $X_i$ ][ $j$ ][ $Y_i \oplus 1$ ] += dp[ $X_i$ ][ $j$ ][ $Y_i$ ] とすればよい。

この dp 配列から操作後の配列を復元する必要があるが、これは下の bit から dp で表現されている寄与を実際にかけていけばよい。(ちなみに、どの順番で寄与をかけても結果は変わらない。)

説明が雑なのでこれ以上は実装見てください

Submission #50106548 - AtCoder Regular Contest 151

解説の言語化がかなりわかりやすかった、「軸ごとに独立に扱える」を「$X_i \neq X_{i+1}$ なら swap してもよくて、最終的に $X_i$ でソートできる」の換言、なるほどね: Editorial - AtCoder Regular Contest 151

記事が長すぎるので分割します

Two Fairs(CFR606-D1B)

Problem - B - Codeforces

$N$ 頂点 $ M $ 辺の連結な無向グラフ $G$ が与えられる。

更に、 $1 \le A,B \le N$ かつ $A \neq B$ を満たす整数 $A,B$ も与えられる。

以下の条件を満たす頂点組 $(U,V)$ を数えよ。

• $U \neq A$ かつ $U \neq B$
• $V \neq A$ かつ $V \neq B$
• $U < V$
• $G$ 上の $U$ と $V$ とを結ぶあらゆるパスは、必ず頂点 $A,B$ の両方を通る(通る順序は問わない。)

$4 \le N \le 2 \times 10^5$

$N-1 \le M \le 5 \times 10^5$

嘘方針 : (これで1h以上溶かしました)

「$A,B$ どちらも通る」 = 「$A$ を通る」 + 「$B$ を通る」 - 「$A,B$ どちらかを通る」

反例 :  $A=3,B=4$

「$A,B$ どちらかを通るが、どちらでもよい」みたいな場合が上手く数えられない。

真方針 :

• とりあえず $G$ から $A$ を接続された辺ごと取り除く。このとき、 $B$ を含む連結成分にある頂点同士の組は答えにならない (数えるべき組の少なくとも一方は必ず $B$ から孤立する)
• とりあえず $G$ から $B$ を接続された辺ごと取り除く。このとき、 $A$ を含む連結成分にある頂点同士の組は答えにならない (数えるべき組の少なくとも一方は必ず $A$ から孤立する)
• 「 $A$ を消すと $B$ から孤立する」「 $B$ を消すと $A$ から孤立する」に重複はない。
  • 証明 : $G$ は連結なのでどの頂点 $u$ についても $u - A - B$ or $u - B - A$ なるパスがある。このことから題意は示される。
• この時点で、「 $A$ を消すと $B$ から孤立する頂点」「 $B$ を消すと $A$ から孤立する頂点」のペア以外は答えになりえないことが分かる。
• 逆に、「 $A$ を消すと $B$ から孤立する頂点数」「 $B$ を消すと $A$ から孤立する頂点数」を掛ければ答えになる。
  • 証明 : 左側のある頂点を $l$ 、右側のある頂点を $r$ とする。
  • $l$ から $A$ を通らずに行ける頂点は $A$ を消した時に同一連結成分にある頂点だけだが、これらは全て「 $A$ を消すと $B$ から孤立する頂点」である。これに含まれない頂点に移動するには $A$ を通る羽目になる。
  • 同様に、 $r$ 側からも「 $B$ を消すと $A$ から孤立する頂点」に含まれない頂点に移動するには $B$ を通る羽目になる。
  • この2つの事柄から、「 $A$ を消すと $B$ から孤立する頂点」「 $B$ を消すと $A$ から孤立する頂点」を結ぼうとすると、 $A,B$ 双方を通る羽目になることが言える。よって2つの数を掛けて答えとして良いことが示せる。

Submission #229779750 - Codeforces

本当に信じられないほど沼った。殺してたも～～～