えびちゃんの日記

えびちゃん（競プロ）の日記です。

PAST #4 参加記

考えていたことなどを書きます。

tl; dr

受検前

有料期間中に受けるかどうか考えました。

前提として、既にエキスパートの認定証を持っているので、以下のような葛藤が生じます。

エキスパートを取れた場合：

  • 少しの間、承認欲求が満たせる
  • 数ヶ月ぶんエキスパートの有効期間が延びる

エキスパートを取れなかった場合：

  • それなりのお金を払って無を取得できる*1
  • 気持ちがめちゃくちゃになる

そもそも、値段が安くはないので、気軽には払えません。 お布施という意味では払う方がいい気もするんですけど。

というのがあって、悩んだのですが、無料になってからうけることにしました。

問題公開日

なかなか公開されません。

ツイートをするとすぐ公開されてびっくりしました。

URL をエスパーしてコンテストページでリロードして待っていたのですが、PAST 過去問 の一覧に反映されたのは問題公開より後だった気がします。

はじまるよ

一覧を見ると「構文解析」と書いてあったので、うれしくなりつつも「どうせ構文解析要素は薄いんだろうな」と思いました。

A

3 つの要素の中央値は「最大値と最小値でないもの」なので、以下のように求めました。

let min = a.min(b).min(c);
let max = a.max(b).max(c);
let med = min ^ max ^ a ^ b ^ c;

総和から引いてもいいと思います。

B

特になし。頭が無だったので "ERROR" ではなく "0" とか書いていました。

C

特になし。

D

特になし。

この辺で、作業用 BGM を準備しようと思って（ナメていませんか）、前によく見ていた動画を探そうとしたのですが、見つかりません。 少し調べると、投稿者が動画もアカウントも全て消していたことが判明し、かなり動揺しました。これを書いている今も引きずっています。

E

Rust は標準に順列を生成するのがないので、itertools を使いました。 そういうのがない言語だとどうするのがいいのでしょう。

ここでは長さ \(N \le 5\) の順列を全て生成すればいいので、「\(N\) 進数 \(N\) 桁を全部つくり、各桁が distinct なもののみ見る」とか？ よく考えると、この問題では \(26^N\) 通り全部作って判定するのが楽かもしれません。

動揺のせいか、D のコードを投げて全ケース RE になっていました。 PAST #1 でも同じことをした記憶がありますね。

F

特になし。

G

動揺のせいか、「. が見つかったら . に変えて、判定を終えたら # にする」という謎を実装していました。

判定用に union-find を使っていたのですが、自作ライブラリ用の bundler がバグっており、その直しに数分を要しました（あーあ）。

H

特になし。

これ、どう線形で解くんでしょう。

I

尺取りでもいいと思うのですが、にぶたんでもいいと思ったのでにぶたんをしました。 円環は 2 周持つのがセオリーだと思いますが、変に配列外参照をしたりすると嫌なので、念のため 3 周持ちました。

この辺で「あれ？ そういえば構文解析たのしみだった。何問題だったかにゃ」と思って、問題一覧を見ると既に AC しており、全てを察してかなり嫌な気分になりました。

J

超頂点を作って Dijkstra をします。

K

\(10^9\) で割った余りとあったので、\(10^9+7\) が MathJax の描画ミスとかで \(10^9\) に見えているのではないかとか疑い、右クリックして確かめました。

転倒数と書いてあるのでセグ木を貼るのかと思いましたが、値が \(20\) 以下とのことなので、そっちで抑えるんだろうなとなりました。

系列二つに対して、「その系列における転倒数」と「各値の出現回数」がわかれば、それらをくっつけた系列に対するそれらの値もわかります。結果として、全体の転倒数もわかります。

これは ACL practice L に似ています。

最初に用意されている系列に対する転倒数と出現回数を求めるパートがありますが、これは「既にできている系列に、長さ \(1\) の系列をくっつける」という操作を考えれば、上の計算方法を流用できることがわかります。

こういうやり方は meldable heap の push を meld でやるやつに似ている気がします。

L

偶奇で分けます。

配列 \(a\) を用意し、クエリ 3（一点加算）によって変化した値を持ちます。 クエリ 1・2 における変化はひとつの変数 \(x\) で持ち、クエリ 1 がきたら足し、クエリ 2 がきたら引きます。

\(a[2i]-a[2i+1]\) の形式で書ける値の個数カウンタと、\(a[2i-1]-a[2i]\) におけるそれを用意します。 出力クエリでは、それらのカウンタで \(x\) や \(-x\) の個数を調べればよく、終わりです。

添字関連でこわれるかなと思ったのですが、一発完動だったのでうれしかったです。

M

なんかこう、賢いをすればいいんだろうなとか、逆順に処理するのが定石だろうなと思いつつ、HL 分解で済ませました。

N

盤面サイズが定数でめずらしい。 サンプルを見ると最大ケースが載っており、いろいろ察します。

値の種類が二つのときの中央値は多数決と同じですね。そういえば最近 MAO の話を聞かない気がします。

包除をするのかな、いや無理かとか思いました。 あと、なぜか縦横がそれぞれ \(60\) くらいだと思っており、「bit DP は無理か〜」と思って棄却しました。

一旦 O を見てしばらく考えて無理になったあと bit DP でいいじゃんとなり、しばらくバグらせるも、なんとか AC できました。 一番上と一番下に 000000 を追加するといい感じになりました。

O

最小費用流？と初手で思って棄却したんですが、冷静に考えるとこれを詰めるべきだったと思います。 区間なのでそれを利用して（スキップするような感じで）辺を張るんでしょうとか思ったのに、なんで辿りつかなかったんでしょうね。

結局、in-place DP っぽく考えたいもののよくわからないとなり、実家になじめていませんねとなりました。

おわり

\(10^9+7\) にしなければ数え上げを出しても ok みたいなのを感じました。

動揺していた序盤と N 以外ではバグらせなかったのはよかったかなと思います。

満点を取るつもりだった人が 94 点で「エキスパートでよかった〜」と言っているの、ダサいですよね。つらい。

*1:厳密には無ではなくて、前のエキスパートが切れてから少しの期間は有効になるものは取得できることが期待されます。