400埋めなど
・ARC 059: D – アンバランス / Unbalanced 400 トケタ
区間を指定して愚直にやるとO(N^3)かかりそう(部分点解法)
1つの文字に注目すると、2n-1個中にn個あればそこを取り出せばよい。しかしさらに考察すると、そういう場所は更に切り取ると3個中2個ある区間が絶対に存在する。密度をイメージするとよい。
結局、連続で同じ文字か、1つ飛ばしで同じ文字な場所があるかどうかが必要十分になる。1-indexedに直すことに注意 (1敗)。
考察で瞬殺できる問題はおいしいな～
・ARC 092: C - 2D Plane 2N Points 400 トケタ
・SoundHound Inc. Programming Contest 2018 (春): C - 広告 400 トケタ
ネットワークフローと二部マッチングのライブラリを作ったついでに通した。
上は貪欲でもっとうまいこと通せるっぽいけど、面倒になったので二部マッチングで() ちなみに、「青でx座標の小さい方から、組める赤のうちy座標最大のものを取る」というアルゴリズムで倒せるっぽい。証明は、最大マッチングからうまく組み替えればこの取り方にできる、というもの。思いつかんなー。なんとなく貪欲で行けそうな気分を高めるとできるのかしら。ちなみに地味にソートが面倒なので実装めんどくない？
下はグリッドグラフの最大独立集合を求めよという問題で、市松はダメなので、「頂点数 - 最大マッチング数」としないといけない。この式で出るのは、マッチングの最大性から「マッチングのどちらか」＋「それ以外の全て」に置けるので、よい。
・ARC 063: D - 高橋君と見えざる手 / An Invisible Hand 400 トケタ
問題文が長いから読むのやめてたけど、真面目に読んだら簡単だった。
ある場所で値段xで買って、ある場所で値段yで買うとき、y-xが最大の場所で行うのが利益最大。そのような場所の個数pが答えとなる。前から「それまでの最小値」「差y-xの最大値」「それを満たす組の個数」を順に更新していくとO(N)でできる。おいしいなー
・SoundHound Inc. Programming Contest 2018 -Masters Tournament-: D - Saving Snuuk 400 トケタ
ダイクストラでs始点yenでの最短距離とt始点snuukでの最短距離を求めると、両替する街をfixしたときの最小はそれらの和で求まる。あとは適切な順番で最小値を求めるとよい。
これを解くためにダイクストラのライブラリを作ったので、今後も活用していきたい。O(ElogV)で解けるのマジで強いな～
・ABC 061: D - Score Attack 400 トケタ
これをやるためにベルマンフォード法のライブラリを整備。(ソラで書けよという話ではあるが...)
負閉路の位置が後にくるパターンを落としていてたくさんWAを出しました。グラフの問題は謎のコーナーケースが生えやすいので怖い...
・AGC 014: B - Unplanned Queries 500 トケタ
よく分からない条件だが、実は「全頂点で次数が偶数」が必要十分。どんな木を用意しても、葉では偶数が必要、そこから内側にたどれば全頂点で偶数が必要となる。逆に十分性もよい。AGCはこういうことをしてくる。ちゃんと考察しましょうという問題だった。
・CODE THANKS FESTIVAL 2017: E - Coin Authentication 400 トケタ
インタラクティブということで敬遠していたが、最近インタラクティブの仕組みも少しわかったので挑戦。そんなに難しくなかった。いわゆる偽金貨判別パズルで、偶奇はフェイク、n進法を用いるとすぐ解ける。5進法だと9回で できそう。なんとなく10進法でやっちゃったけど。
ちなみに実装にやや神経を使った。というかNが小さいケースでハタンして1敗。悲しいなぁ...
・AGC 020: C - Median Sum 700 トケタ
M-Solutionプロコンでbitset高速化が出たと聞いて、練習にこれを通した(ネタバレクソ野郎)。
bool値のDPとかだと、bitsetを使って高速化することでギリギリ通ることがある。計算量が64分の1になるらしい。今回は2000^3/64=1.25*1e8なので、難しいことをしてなかったら通る。N=2000くらいでbool値使う感じなら使えるかもなので覚えておこう。
・CODE FESTIVAL 2016 Grand Final: A - 1D Matching トケタ
端っこから見ると、組めるだけ組むのが距離最小。PCと電源を区別して位置でソートし順に見ていって、そのとき組めるパターンだけかけていけばよい。pairによるソート(priority queueつかっちゃった)に慣れてきた。
