モノグサプログラミングコンテスト2022（AtCoder Beginner Contest 249）に参加しました。

結果

A,B,C,Dの4問ACでした。 C問題で何を答えれば良いのかを理解するのに時間がかかった…問題文がややこしくてよく意味がわからなかった…
たまにこんな風に何を言っているのかよくわからない問題があるけど、これは自分の読解力が足りないのか？
D問題はデータ型をlong longじゃなくてintにしたところがあったのが原因で1WA。5分くらい無駄にした。

A - Jogging

A問題にしては難しい問題だと思う。愚直にシミュレートして答えるしかなさそう。

まずは、歩く時間＋休む時間を1セットとして考えてX秒で何セット繰り返すかを計算する。セット数 $\times$ 歩く速さ＋1セットを満たさず余った時間で進む距離　がX秒で進む距離になる。

これを二人分計算して距離の大小比較をして長い距離を進んでいる方を答える。

B - Perfect String

3つの条件を全部を満たすかどうかを確認して答える問題。文字数の制約を見るとせいぜい100文字程度なので1文字づつ確認していけば時間は余裕で間に合う。

C++だと文字は数値で扱われるので $'a' \leq S _ {i} \leq 'z'$ みたいに比較演算子で判定できる。大文字が出てくる、小文字がでてくるはフラグで管理した。全ての文字が相異なると言うのは、1文字づつsetに入れた後のsetのサイズと文字列のサイズが一致しているかどうかで判断した。

C - Just K

問題文の意味がよくわからなかった。

とりあえず簡潔に言い換えると以下になると理解して問題を解いていった。

好きな数の文字列を選択する
どの文字が何回出てくるか数える
出現回数がK回の文字が何個あるか数える
3の個数の最大値を答える。

1の部分はbit全探索で対応した。Nは最大でも15で $2 ^ {15}$ は32768で $10 ^ {4}$ 程度なのでbit全探索部分だけでTLEすることはない。

2の部分は事前に文字列毎にどの文字が何回出てくるかを集計しておき、選択した文字列分の集計結果を合計すれば良い。

3の部分は、2の計算結果がKとなっている文字の数を数えた。

4の部分は、bit全探索内で3の結果の最大値を更新し続けて最終的な最大値を答える。

問題文がよくわからなかっただけで、ACするためのアルゴリズム自体はそこまで難しくないと思う。bit全探索を知っている・実装できるなら解ける問題だと思う。

D - Index Trio

問題文を読むと最初は、ちょっと難しそうな問題だと思った。
問題文を読んでの考察としては

制約的にはNに関する二重以上のループで解こうとするとTLEになるのでNに関しては1重のループで解けないとACできなさそう。
愚直に解こうとすると $O(N ^ {3})$ でTLEする。
こういったパターンの問題はi,j,kのうちi,jが決まればkが確定する事が多く $O(N ^ {2})$ までは計算量を削減できる場合がある。
$\frac{A _ {i}}{A _ {j}} = A _ {k}$ のままだと割り算の部分で誤差が出てWAになりそうなので式変形して $A _ {i} = A _ {j} \times A _ {k}$ で考えたほうが良さそう。
$A _ {i}$ は $A _ {j}$ の倍数
整数列Aの順番はそれほど大事じゃないのでソートしても問題ない。