ユニークビジョンプログラミングコンテスト2023 秋 (AtCoder Beginner Contest 323)に参加しました。
結果
A,B,C,Dの4問正解でした。
30分ちょっとでD問題まで解けて、後の時間ずっとE問題考えてた。 E問題の確率を mod998244353で求めるっていうのが全く分からなかった。 定義を読んでみてもどこからその数字出てきた！？ってなって、たぶんこれは解けないやって思った。
A - Weak Beats
0,1でできた文字列の偶数番目の文字が全部0かどうかを判定して答える問題。
文字列の任意の文字を取得できるかどうかと、その文字列が特定の文字かどうかの判定ができれば解ける問題。
B - Round-Robin Tournament
o,xで構成された試合結果がN人分与えられるので、 勝利数別プレイヤー番号別にソートして上から順番にプレイヤー番号を出力する問題。
文字列からoの数を数えて各プレイヤーの勝利数を計測する。 次に勝利数とプレイヤー番号でペアを作って、そのペアをソートして上から順番にプレイヤー番号を出力して解いた。 ソートは、勝利数に関しては大きい順、プレイヤー番号に関しては小さい順と項目によって昇順、降順が異なるので自作の大小比較用関数を作成して、それを使ってソートを行った。
勝利数とプレイヤー番号をセット管理しつつ、そのセットをうまくソートできれば解ける。
別の方法で解くなら、
勝利数の最大値を求めて、勝利数の最大値から0まで順番に探索対象の勝利数を変化させつつ、
各ループで対象としている勝利数と一致しているプレイヤー番号を小さい順に出力していけば解けそう。
C - World Tour Finals
N人のプレイヤーがM問ある問題の一部を解いている。 問題を解いているかどうかはo,xでできた文字列で与えられる。 現時点の最高スコアに追いつくには最小であと難問解けば良いかを各プレイヤー分答える問題。
問題の点数と問題番号でペアを作って、点数の高い順位ソートする。 それとは別に各プレイヤーの現在のスコアを計算し最高点を求める。 各プレイヤーに対して、点数の高い順に何問解けばスコアが現時点の最高スコアを超えるか数えて出力する。
B問題に続いて、ペアを作ってソートすれば後は簡単な処理で解ける問題。 この問題も2つの項目をセットでソートして管理するのがポイントだと思う。
D - Merge Slimes
サイズのスライムが
匹いる。
同じサイズ2匹で倍のサイズのスライム1匹に合成できる。
スライムの数を最小で何匹にできるかを答える問題。
合成するのは同じサイズ同士だけだし、合成した結果2匹が1匹になるので 合成できる時は合成したほうがスライムの数は減らせる。 なので、サイズが小さいスライムから順番に可能な限り合成していけばスライムの数は最小にできる。
スライムのサイズや数は最大でになるので1から順番そのサイズのスライムがいるかどうか確認しながら処理していくと間に合わない。
存在するサイズとそのサイズが何匹いるかをうまく管理すれば解ける問題。
B,C問題も2つの項目をセットで管理する問題だったけど、今回は一方の項目の値が動的に変わったり、項目が追加されたりがあり得る。なので値の更新や項目の追加がやり辛いペアを使うのは相性が悪い。
今回は処理速度的に不安だなと思いながら連想配列のmapを使って解いた。
合成後の新しいサイズのスライムの数は/2匹追加になるし、
合成後の元のサイズのスライムの数は
を2で割った余りになる。
サイズの小さい順にこの処理を順番に実施しつつ、 各サイズで余ったスライムの数を数えていけば簡単に答えが出せる。
E - Playlist
問題の内容的にDPで解く問題だと思った。
それ以前に問題文の内容が一部分からなくて解ける気がしなかった。 確率を mod998244353で求めるというのが意味不明だった。
定義を読むと xz≡y(mod998244353) を満たすような 0 以上 998244352 以下の整数 z が一意に定まります。この z を答えてください。 ってあるけど、どうやってそれを求めるのか分からなかった。 出力例1の解説でzとして突然369720131が出てきてて、どこからその数字持ってきた！？ってなってた。
定義を読んでると暗号化理論でこんな感じの数式みたことあるなあと思ったりした。
