AtCoder キーエンスプログラミングコンテスト 2020 参戦記

AtCoder キーエンスプログラミングコンテスト 2020

に参加しました。

結果は 33 分 ABC 2 WA で 993 位パフォーマンス　1384 でした。ここ数回ちょっとずつ上げたレートを吐き出す結果になりました。夕食が家族そろっていて飲んでいたので仕方ない*1ですね...

f:id:y_r:20200119115643p:plain

縦か横か升目の多い方を選んで規定数を超えるまで塗りつぶす。

200 点!!? 400 点ぐらいに見えた。
左腕をソートして順番に見ていく。

区間スケジューリング問題という有名問題らしい。

なお、最初制約を一桁小さく見て $O(N^2)$ 解を投げて TLE くらった。

気づくとギャグ問題。K <= N なので先頭から K 個 S をつなげればよい。あとは S+1 でも並べとけばよいが、S が 10^9 のときだけ 1 を並べる。
最初 S + 1 が 10^9 となるときに 1 を並べて WA をくらった。

最初任意のカードを交換できると誤読していてだいぶ時間を溶かした...

各カードの表裏は $2^{18}$ なので全通り試せる
各カードの表裏が決まるとそのカードの数値が決まり、おける場所は奇数番目か偶数番目に拘束される
表裏を固定して実現可能か見て実現可能なものの操作回数の最小値が答え
- 実現可能かは、裏表決め打ちしたカードをソートして適切な位置にあるか見る
  - 同じ数値のカードがある場合は、奇数番目偶数番目を守ったうえで、ソート前に先頭にあるカードから並べていく
操作回数はバブルソートと同じ (=転倒数) でナイーブに計算しても $O(N^2)$ $N <= 18$ で瞬殺

...考察はあっていたが同じ数値のカードをいじるところで無限にバグを出し続けてタイムアップだった。twitter で見るようにおける場所の奇数偶数にわけてソートした方が楽だった。

寝ている間に (誤読しつつも) 考察が降ってきたので起きてから通した。D より簡単だったかも...

$D$ で昇順ソート
の小さい方から
- 隣接頂点に色を塗っている頂点がなければ、[tex :D] の最小値を持っている隣接頂点を選び出す
  - このとき 2 頂点の最小値が等しくなければ構築不可能
  - そうでなければ 2 頂点を白黒に塗り分けて間の辺のコストに今の頂点の $D$ をいれる
- 色を塗っている頂点があればその頂点とは違う色を今の頂点に塗って、その間の辺のコストを今の頂点の $D$ に設定する
残りの辺のコストは無限大 (実際には最大値) をいれておく
上記でよいのは昇順ソートしてあるので、色を塗り済みの頂点に新しい辺のコストを設定してもその頂点の最小値には影響しないため