2024/02/24 1 年半ぶりに algorithm コンテストに参加した。
コンテストページ
https://atcoder.jp/contests/abc342
結果
- ABCDE5完 (71:20) 0 ペナ
- パフォーマンス 1652
- Rating 1311 -> 1354
かなり久しぶりに参加していろいろ忘れている気がしたが、意外と良いパフォーマンスが取れて安心している。
https://atcoder.jp/users/sankantsu/history/share/abc342
感想
先日 AHC030 に参加して久々に競プロ熱が高まっており、algorithm も参加するかと思って出てみた。 かなり久しぶりだったので、当日開催前に ABC341 の問題を解いてリハビリしたりしていたが、overflow やら範囲外アクセスやらでかなりミスを重ねていたので、やっぱり競プロ慣れが抜けているなとちょっと心配になるところもあった。 アルゴリズムもいろいろ知識が抜けている感じがある。いろいろな記事を眺めていると、前に勉強したのにどんな内容だったか思いだせないデータ構造などが結構あった。
レーティングが下がるんじゃないかという不安はあったが、それでも参加するのが慣れを取り戻すには一番だろうと思い、参加はしてみることに決めた。 いざ参加してみると、思ったより順調に進みペナルティもつけずに 5完することができて、レーティングも上昇した。 問題の相性が良かったのではないかと感じるが、ひとまず満足のいく結果がとれて安心した。
A
文字列の中で 1 文字だけ異なるものの index を見つける。
解けないことはないのだが、最初どうやって書くか少し迷ってしまい 9 分も溶かしてしまった。 前後 2文字を先読み後読みすることで解決したのだが、後から解説を読んで 2重ループにしているのを見て、計算量気にしないなら確かにそれが楽だよなと学んだ。
B
数字の出現順のクエリについて答える。
列の長さもクエリも少ないので、計算量気にせず愚直に。 特に迷うところなく、5分ぐらい。
C
1文字置換を繰り返してできる文字列を求める。
文字列もクエリも長いので愚直だとだめ。
少し迷ったが、アルファベットごとの変換テーブルを更新していく形で O(σ(Q+N))。
12 分ぐらい。
D
かけ算して平方数になる値のペア数を求める。
平方数を除算して同値分類するというアイデアはすぐに思いついたが、少し実装をバグらせて時間を消費。 17 分ぐらい。
E
特定の駅に到着するための終発の時刻を求める問題。
問題文が長く、パラメタが多いので読解に時間がかかったが、実質的にはただのダイクストラで queue につっこむ探索候補を少し工夫するだけなので、それほど迷うところはなかった。 そんなに難しくない印象だったが、Atcoder Problems で確認すると水 diff 上位ぐらいになっているので思ったより高い。 自分がこういう無駄に問題文が複雑なパターンを読解するのが比較的得意な部類ということだろうか。 26 分ぐらいで実装。
F
ブラックジャック風のゲームで最適戦略をとったときの勝率を計算する。
E を解き終った時点で残り 30 分あったので取りくんでいた。
まずディーラーの行動は確定的であるので、結果の分布が正確にわかるので、ここから考察してみる。 累積和を組み合わせた DP で終了状態のパターン数が正確に計算できることには気付いた。 しかし、その後最適戦略が何であるかは時間内にはわからなかった。
ディーラーの結果の分布から、プレイヤーが特定の値で stay したときの勝率は正確にわかる。 したがって、stay の勝率と draw の勝率が逆転するかどうかを N から下にむかって検証していき、stay するかどうかの境界を定めれば良いと気付く。 draw の勝率も、累積和 + DP で計算できる。
あとは、この戦略をもとに各値で終了する確率をディーラーのときと同様にプレイヤーの終了分布を計算すれば正解できる。 誤差評価はあんまりよくわかってない。
考察に時間がかかったが、自力 AC することができた。数少ない黄 diff 自力なのでうれしい。
