PAST2 バチャ記

atcoder.jp

どういう記事？

第二回PAST のバチャで全完をキメたので適当に振り返る、誰得？な記事です。

解法ネタバレのような何かを含みます。

解法・問題ごとの感想

適当に解法を書くだけです。解説ではありません。

A - エレベーター

階と整数をうまく一対一対応させるとできる。 (地上0階が存在しないという罠...)

B - 多数決

全部数えるだけ。

C - 山崩し

これを書いているときに、山崩しという設定だったことを初めて知った。

問題文で丁寧に説明されている通り実装するとできる。

D - パターンマッチ

いい解法が思いつかなかったが、 としてあり得る文字列を全部試せばよい。

E - 順列

問題文に書いてある操作をやりまくればとけると思う。UnionFind を持っていれば貼るだけ。

F - タスクの消化

この辺から制約が大きくなるので、適当にやりすぎるとTLEする。

タスクを std::priority_queue などで管理すればいい

G - ストリング・クエリ

文字をひとつずつ追加・削除していると日が暮れる。

std::queue<char, int> のような感じで管理すると解ける。

H - 1-9 Grid

問題設定が割と好きかもしれない。

実装は、適当にやればできそう。

I - トーナメント

トーナメントをシミュレーションすればいい。(優勝者だけは、最後に出場した試合で勝利しているという罠...)

J - 文字列解析

問題文に書かれている通りに操作をすると解ける、それだけ。

ちなみに、僕の感覚ではこの問題までが自明枠

K - 括弧

括弧列は、初項 で、(で 、)で する数列を考えると分かりやすかったりする。(我流なのでもっといい方法がありそう)

正しい括弧列は、このような数列の内、全ての項が非負で末項が である数列と対応する。

このことを考えながら超適当に DP を書くと通る。

L - 辞書順最小

「適当に前から貪欲すれば通るじゃん！」と思って適当に書いたらTLEした。

区間 min をしたかったので、セグ木で殴る、おしまい。

バチャ終わった後思いつきましたが、優先度付きqueue でも書けそう。

M - 食堂

個人的にこの問題が最難だと思う。

問題の日本語を読み解くのが難しいですが、頑張って前処理をすると二分探索を使ってクエリあたり対数時間で解ける。

N - ビルの建設

なんか JOI にありそうな雰囲気。座圧してBITで解ける。(非本質な座標圧縮は、書くために多くのモチベを必要とすることで知られている。)

O - 可変全域木

この中で一番好きな問題。

適当に最小全域木を作る。 を求めたい。右の項以外は自明なので、右の項を求めることを考える。

これは、クラスカル法で、クエリあたり で解ける。(これだとTLE)

全てのクエリに対して並列で二分探索をすることで、解ける。(計算量を書くのを面倒くさがる人)

感想

N 以外はそんなに知識を必要とはしない問題だった気がすると書いてから思ったが、並列二分探索などは結構高レベルな知識なのかもしれない (?)

尾張に

本当に誰得？な記事が完成してしまった。永久に下書き保存しておいても意味がないので、とっとと世に放つことにする。