ブログっぽいことをしようと思いました。
出たコンテスト
CF#558(Div.1) 2完 2018->2095
PG BATTLE 結果不明
ABC142 6完 1982->2027
解いた問題
手応えのあった問題だけ。
JOI2009春 1-2 Stamps
https://www.ioi-jp.org/camp/2009/2009-sp-tasks/2009-sp_tr-day1_20.pdf
30分くらい。
新しい文字列T="IO"+S+"OI"としても、端の"IO""OI"を変化させることに意味はないので、Tのもとで考える。
Tは I..I とO..O が交互に繰り返される形になっている。これらのブロックをまるまる削除したり追加したりすると、2つまとめて消すことになり、必ず損をすることになる。
これでI..I、O..Oを独立に考えてよくなったので、操作回数が最小かつその中で文字列が最短になるものを考えると、
ブロックの長さLが奇数のとき floor(L/2)回変更する
Lが偶数のとき 1文字削ってfloor(L/2)回変更する
のが最適となる。
これを愚直に実装すればO(|S|)で解ける。
CF1229A Marcin and Training Camp
https://codeforces.com/contest/1229/problem/A
30分くらい。
「a_uで立っているbitがa_vで立ってない、またはa_u=a_v」の場合に(u,v)に有向辺を張ったグラフを考える。
明らかに、入次数=0な頂点は使えない。また、それを消すことによって入次数=0になる頂点は使えない。
これを再帰的に繰り返していき、残った頂点は全て入次数>0であり、これらを全て選ぶのが最適。
bit演算を使えば高速にグラフを構築でき、O(n^2)で解けた。
CF1229B Kamil and Making a Stream
https://codeforces.com/contest/1229/problem/B
コンテスト中はこの解法が間に合うとは全く思ってなかった。解説AC。
ある列Aについて、gcd(A_0),gcd(A_0,A_1),...,gcd(A_0,A_1,...,A_N)の中での種類数がO(logA_0)であるということを使う。これは、順に見ていった時にgcdが減る場面では必ず1/2以下になるということから分かる(gcdで掛けられている素因数が1つ以上減るので)
葉側の頂点vをDFSしながら走査していく。unordered_mapを使って「根からvまでのパスの中の、vを含むgcdの集合」を種類ごとに管理できるので、O(nlog(xmax))で解けた。
CF1229C Konrad and Company Evaluation
https://codeforces.com/contest/1229/problem/C
40分くらい。
稼ぐ額が大きい方から小さい方へ辺を張った有向グラフとして見ると、頂点が更新されたときに、入ってきている頂点を全て出ていくように変更し、差分を計算する、という処理をすればよいとわかる。
実は、これを愚直に実装するだけでACできる。
クエリを√M個のブロックに分割して考える。
・頂点がブロックで初めて更新されたとき
これで更新される辺数の和が2M(次数の和)以下であることは明らか。
・頂点がブロックで2度目以降に更新されたとき
各頂点について、1度更新されると入次数は0になり、1つのクエリについて高々1つしか入次数は増えないので、ブロック内のクエリ数から、変更する必要のある辺数は√M回以下。よって合計でM回以下。
これを合わせて、O(Q√M)になる。
ABC142-F Pure
https://atcoder.jp/contests/abc142/tasks/abc142_f
「全頂点が入次数1、出次数1のグラフ」はサイクルの集合となる。このうち1つ構築すればよいので、1つのサイクルになるような誘導部分グラフを求めればよい。
まず、元のグラフにサイクルがなければ明らかに-1である。そうでなければ必ず以下のように構築できる。
サイクルの始点を決め、順に見ていく。後ろから入ってくる辺があれば自分の前にある頂点、「入ってくる元の頂点」の後にある頂点は使わないようにする。後ろへ出ていく辺があればその間にある頂点はグラフに含めないようにする。この結果できるグラフは必ず2頂点以上のサイクルになるので、条件を満たす。
感想
コンテスト以外で1問しか解いていなくてまずい。こういうのを可視化していきたい。
