サイト移行のための準備を真面目に進めた。Vulkan入門をもうちょっと書き進めてからとか言っていたが、どう考えてもそんなの待ってたらいくらでも時間が経つし、早く出すべき。
ABC298に出た。かなり失敗した。Eが解けなかったのが痛い。
A: やるだけ
B: やるだけ
C: 箱に入っているカードの番号とある番号のカードの入っている箱をそれぞれmultisetとsetで管理する。
D: クエリ1が来たときは10倍してxを足す。クエリ2が来たときは(先頭の数字)×10^(文字数-1)を引く。後ろに繋げて先頭から出すので各数字はキューで管理すれば十分。
E: なんかごちゃごちゃやって解けなかった。高橋君青木君それぞれについてi回目の操作時にマスjにいるパターン数、とかを計算することはできたのだが、何を分母として見るべきなのかをちゃんと考えきれなかった。
F: R行C列の総和Sは(行Rの総和)+(列Cの総和)-(マスR,Cに書いてある数字)で求まる。数字が1か所以上書いてある行は高々N行以下なので、各行についてもっともSが大きくなる列を高速に見つけられればよい。
RMQの出来るセグ木に各列の総和を書き込む。ある行を考えるとき、その行の中で数字が書き込まれているマスを見る。それらのマスについて、そのマスの値を列の総和から引く。これによって(列Cの総和)を(列Cの総和)-(マスR,Cに書いてある数字)にすることが出来る。あとは普通に最大値を取って行の総和と合わせればよい。
各行について列を見るために$O(\log N)$、各マスについてセグ木の更新処理が走るので$O(N\log N)$、全体で$O(N\log N)$となる。
G: 解けず。H,Wが小さいのでそこが狙い目なのだろうが、トリッキーな出題すぎて手のつけようがなかった。
GCJ Farewell Roundに出た。Atcoderと出題傾向がちょっと違って面白かった。
英語の読解や出力形式の部分などで時間を食ってしまったため、形式に慣れていればもう少し行けたかもしれない。まあでも楽しかったのでヨシ！
Round A
1問目: やるだけ
2問目: 端から見て行き、今まで照らした区間によって照らされない電灯が出てきたらその1つ前を転倒させる。そもそも照らせないような場合は、最初に端と各電灯間の距離だけ見ておけば判定できる。
3問目: 同じ色のカードが2か所以上に分かれている箇所があると単調非減少列は作れないので不可能。そうでないなら、端から見て行って新しい色が出るたびにそれを出せばよい。
4問目: 26を引く、26*2を引く、26*3を引く…とやっていって引けないことが分かったらそこで文字を判定するだけ。
5問目: ランレングス圧縮してしまうと楽。同じ手の人の区間はfloor(区間の人数/2)を書き換えればよく、これを各区間について合算すればよい。円周なので、最初の人と最後の人が同じ手の場合に注意。それから全員が同じ手を出している場合、これはfloor(人数/2)ではなくceil(人数/2)とする。
Round B
1問目: 鬼トレの陣取対局に似ている。これは1次元上なので、回り込まれる心配がない。出来る限り相手を得点が少ない側に押し込めてやるのが最適となる。
アリスの初期位置を決めた場合、ボブの最適な初期位置はアリスの隣。隣に居られない場合は出来るだけアリスに近い位置。あとはアリスとボブが互いに近づき、ぶつかったらあとは各自取れるケーキを取っていくのが最善となる。
アリスの初期位置を決めればあとの得点は全て簡単に決まるので、アリスの位置は全探索した。全探索で間に合うときは全探索するのが確実。
2問目: $kD = X_i-X_{N-i+1} mod N$となるような絶対値最小のkを$1\leq i \leq \lfloor\frac{N}{2}\rfloor$について探して絶対値の総和を取る。拡張ユークリッドで頑張って一次不定方程式を解けばよろしい。ライブラリ整備しててよかった。なお絶対値なのは、k<0が逆回転に対応しているため。
3問目: 「ある数字を採用した上で、その数字以上(以下)の番号のみで作れる最大のspacioutなset」をDPで求める。求まったらあとは各数字について、その数字以上の～とその数字以下の～を足して1を引けばよい。
4問目: 全く分からず。UnionFind使った愚直解はさすがに書けたので部分点は出たが。
5問目: もうちょいで解けそうだったのだが無理だった。まず、Functional Graphであることが分かる。木の末端部は使いまわせるものが来るはずがないので、まずは端からやっていけばよい。あとは木なので迷うことがなく、サイクル部に到達する。ここからの処置が分からなかったというか、自信が持てなかった。あと、グラフが連結などという保証はどこにもないので非連結の場合も対応する必要がある。
Categories: 未分類