9/29-10/5

この場所を有効活用したいと思ったのでばちゃの結果を書くことにした。代表になれないのにIOIばちゃをする人になった(大学生になったらどうせ解かないし...)。
できる日は5時間ばちゃをやってここに記録するようにしたい。

出たコンテスト

CF#589(Div.2) 3完 2095->2017
AGC039 2完 2027->2043

IOI2013 Day1 virtual

100+12+55=167点。謎問題で点数がだいぶ左右されるのつらそう。

~0:20くらい 1問目、2問目を読む。2問目が謎なので後に回すことにして、1問目はすぐに小課題3まで分かる。
~0:40くらい 1問目の小課題4が分かり、それに連動して満点解法も分かる。自分がこの時間で分かるということは簡単枠だろうと思ったので実装することにする。
1:07 1問目の小課題4だけ通る。なぜか一緒に取ろうとした小課題1が通らない。
1:51 謎だったので満点解法を実装すると、通らない理由がわかる。なぜか65点。
1:54 M=N-1で壊れていることに気づく。100点。
2:41 3問目を読むと、小課題3まで分かったので書くと通る。
2:54 すぐに小課題4もわかったので通す。それ以降はヤバい臭いがするので飛ばす。
3:57 2問目がよくつかめなかったので雰囲気で書いて出す。6点。
4:16 微妙な改善を投げるが12点。そのままコンテスト終了。

1問目 Dreaming

各連結成分について、「そこからの連結成分内への距離の最大値が最小となる頂点」のみ他の連結成分と繋げればよい。これに気づくと、次の3つの問題を解けばよくなる。
・木の中で最も遠い2頂点間の距離を求めよ。
・木の中で、「ある頂点を根にしたときの深さの最大値」の最小値を求めよ。
・頂点ごとにコストviが定まっているN頂点0辺のグラフがある。これにN-1辺を追加して、d(i,j)=vi+vj+(iとjの距離)*L の最大値を最小化せよ。
1つ目と2つ目は、全方位木DPをすることで求まる。
3つ目は、実はviが最大の頂点から他の全頂点へ辺を張るのが最適となる。
これは、viが最大な頂点をmとして、m-t1,t1-t2に辺が張られているとき、m-t1,m-t2 に辺を張り直しても損をしないことからわかる。
これでO(NlogN)で解けた。

2問目 Art Class

画像分類をしてくださいという問題。
無思考で「差の二乗和」とかを求めて特徴量を探そうとしていた。
なにもわからない...

3問目 Wombats

55点までは省略。ここから非自明パート(解説を見た)。
最短路テーブルをセグ木に載せることを考える。具体的には、列iから列jまでを被覆するノードでは、「C(p,q)=(i,p)から(j,q)への最短路の長さ」を任意のp,qについて求めたテーブルCを持つことにする。
「D(i,j)=i行目からj行目への、任意の列の2組の最短路テーブル」を求めたいとする。進行方向の性質から、これはi < k<=jなるkについて、D(i,k-1)とD(k,j)から求めることができる。愚直に計算するとO(C^3)。
k-1側の出る場所を固定すると、実は、k側で入る場所を右に動かすにつれ、「k-1からkへ移動する列」も右に動いていくことがわかる。この性質を使えばO(C^2)で求められる。
k=(i+j)/2とすることでセグ木のマージが同じようにできるので、辺更新1回についてO(C^2logR)でできる。
回答クエリについては、全体を被覆する区間を見るだけでよい。O(1)でできる。
これで解けた...と思ったが、実はサイズR*C^2のテーブルを用意しただけでMLEする。時間には余裕があるのでセグ木を工夫するとできるらしいが、面倒になって実装していない...。

解いた問題

JSC2019決勝-A Equal Weight

https://atcoder.jp/contests/jsc2019-final-open/tasks/jsc2019_final_a
15分くらい。300ではない。
まず、A,Bが相異なるので、条件を満たす組で同じシャリやネタが2回使われることはない。
握りの重さの種類数は高々2*10^6通りであることに注目する。
愚直全探索を考えると、シャリとネタの組を全部試し、重さに被りが出たところで終了、というようになり、これはO(NM)に見える。しかし、2*10^6通りより多い組を試した時点で1つ以上被りが生まれるはずである。そのため、2*10^6+1通りより多い通り数が試されることはなく、間に合う。

CF1228E Another Filling the Grid

https://codeforces.com/contest/1228/problem/E
コンテストが後5分長ければ通っていた...。
1の置き方を決めていくことを考えると、「行の中で最初に1が現れる列」が単調増加すると仮定して、
dp(i,j,k):i行目まで見て、i行目の中で最初に現れるのがj列目で、jがk回連続しているときの通り数
というDPをすると、累積和を使って面倒だがO(N^3)で解ける。コンテスト中はこの方法でやった。
上のDPは1の順序を固定してやったせいで面倒になっているが、冷静に考えると「1が既に入っている列の個数」さえ求まっていればよいことがわかる。
dp(i,j):i行目まで見て、1がj個の列に入っている時の通り数
というDPでO(N^3)で解ける。
また、実はこれは包除原理が使える。「i個の行、j個の列に1が含まれていないことがわかっている時の通り数」を計算し、偶奇に応じて足し引きすればよい。O(N^2)で解ける。「または」のみの式は「かつ」の通り数を足し引きすることで求められる、というのが包除原理。

JSC2019決勝-C Maximize Minimum

https://atcoder.jp/contests/jsc2019-final/tasks/jsc2019_final_c
座標xにあるイチゴについて、min(x,L-x)に置いてあるとして考える。
間に2つ以上イチゴのある2つの距離が答えになることはない。また、L/2に最も近い2つについて、(最も近いものを折り返した時の2つの距離)より距離が長くなることはない。よってこれと「間に1つイチゴがあるような2つの距離の最小値」とのminが答えの下界となる。
これは、「左から偶数番目にあるやつを折り返す」というように決めると達成できる。
L/2に近い2つの方の距離は毎回計算してよい。間に1つイチゴがあるような2つの距離は、この2つの集合が一度の操作で定数個しか変化しないことを用いると求められる。
「今の座標の集合」と「間に1つイチゴがあるような2つの距離の集合」をmultisetで管理すればO(NlogN)で解ける。
実装がとてもつらい。

AGC039-B Graph Partition

https://atcoder.jp/contests/agc039/tasks/agc039_b
V1に入れる頂点を1つ固定し、全頂点への最短距離を計算する。すると、最短距離がdの頂点をV(d+1)に入れるのが最適となる。なぜなら、Vi(i>d+1)に入れると壊れるのは明らかで、Vi(i<=d)に入れたとしても、それが条件を満たすならばV(d+1)に条件を満たしたまま移動できるからである。これは最短距離の性質を考えるとわかる。
このようにして構築したグラフのうち、条件を満たすものがなければ-1、あればd+1の最大値が答えとなる。

感想

相変わらず競技プログラミングをする時間がない。
PGBATTLEで入賞していてうれしかった。