naoya_t@hatenablog

いわゆるチラシノウラであります

AGC埋め(先日のAGC 030の問題を解く大晦日)

晦日にC, D(ともに1000点問題)を解いてみた
と言っても両方とも30日に開いたけど解けず、31日にも考えたけど解けず、Dに至っては解説を見たけど大事なところが分からず人の実装を見てなるほどと思ってAC取れた次第

AGC 030 C - Coloring Torus (1000)

K\le 500のケースについては一列に並べるだけでいいと思うんだけど問題は500\lt K\le 1000のケース…
いろいろな並べ方を考えてみたけれど思いつかず

解説読んだ

4の倍数のn(たとえば4)で

1 2 3 4
2 3 4 1
3 4 1 2
4 1 2 3

のように組めばn=4色。偶数行目に+nすると

1 2 3 4
6 7 8 5
3 4 1 2
8 5 6 7

として2n=8色で塗れる。ここで8の代わりに4(=8-n)を置くと7色で

1 2 3 4
6 7 4 5
3 4 1 2
4 5 6 7

となってこれも塗り方として有効である。(4の周りには必ず1,3,5,7が1つずつある)
7→3, 6→2とすることで6色・5色も可能になる。

1 2 3 4   1 2 3 4
6 3 4 5   2 3 4 5
3 4 1 2   3 4 1 2
4 5 6 3   4 5 2 3

このように、n=2k4k-3\le K\le 4k をカバーできる。

  • n=2で2〜4色(1色の場合はこの方法では構築できない、というか単にn=1で1を塗ればいい)
  • n=4で5〜8色
  • n=500なら997〜1000色

(分かったけれど、これをどうやって思いつけと言うのだろうか…)

→AC
https://atcoder.jp/contests/agc030/submissions/3904812

AGC 030 D - Inversion Sum (1000)

期待値の線形性を使うに違いない。
交換を繰り返すことで元の配列のどれがどこにどれだけの確率で存在するかは計算できる。
ある数(大)がある数(小)より左にある(即ちi\lt jのときA_i\gt A_j)かどうかをその確率から計算できるのでは…?と思って色々ひねってみた。(けれどそういうわけではなかった)
とすると、あるA_i,A_jの組み合わせの大小関係の確率遷移がDPか何かで求まればいいのか。
長さ\frac{N(N-1)}{2}(あるいはインデックスが面倒だからN^2)の配列になると思うのだけれど、これをQ回更新してたら4\times 10^9で死。変更のある部分だけ変更することで(ijが絡む組に限られるので2N-1箇所かな)DP部分の計算量は O(NQ) に収まりそう。最後に全部足し合わせて2^Nを掛けて出来上がり、で計算量はO(N^2+NQ)。メモリは配列1本で必要なところだけ更新でO(N^2)で済むのかな。
そこまでは自力でたどり着けたのだけれど
交換が発生したときに確率がどう推移するかが分からなくてギブアップ。

解説読んだ

解説も(悪い意味で)同様。(確率の遷移について説明がない)
人のコードを読んでみた。

  • 各クエリ(交換する場所をx,yとする)について
    • xでもyでもないすべての場所i (0\le i\lt N)について
      • \displaystyle dp[x][i]=dp[y][i]=\frac{dp[x][i] + dp[y][i]}{2}
      • \displaystyle dp[i][x]=dp[i][y]=\frac{dp[i][x] + dp[i][y]}{2}
    • それと
      • \displaystyle dp[x][y]=dp[y][x]=\frac{dp[x][y] + dp[y][x]}{2}

それだけ…
どゆこと?

  • まず、dp[i][j]_NC_2組じゃなくてN^2組の位置について(i≠j という制約があってN(N-1)組だけど)見ていて
  • x,yの交換で (x,i) (y,i) が(\frac{1}{2}の確率で)入れ替わるので、この2つは半分ずつ混ぜ合わせた値(即ち2つの元の値の平均値)になる
    • (i,x) (i,y) についても同様
  • (x,y) (y,x) も同様に(\frac{1}{2}の確率で)入れ替わるので(以下略)

実装してみて(かなりシンプルだ…)
→AC
https://atcoder.jp/contests/agc030/submissions/3905332
解けてしまえばこれは美しい問題だった