れとろのメモ置場

とあるSEのメモ置場

デンソークリエイトプログラミングコンテスト2022 Winter(AtCoder Beginner Contest 280)

デンソークリエイトプログラミングコンテスト2022 Winter(AtCoder Beginner Contest 280)に参加しました。

結果

A,B,Cの3問正解でした。

C問題までは相変わらず楽勝だったけど、D問題が解けそうで解けなくてもどかしかった。

A - Pawn on a Grid

与えられた複数の文字列の中から指定された文字が全部で何文字あるかを数えて答える問題。

文字列の数や、各文字列のサイズが対して大きくないので全探索で十分間に合う。

文字列の扱い方を知っているかどうか確認する問題かな。

B - Inverse Prefix Sum

とある数列を求めて答える問題。

与えられる数列Sは答えるべき数列の和となっている。  S _ {1} = A _ {1}, S _ {2} = A _ {1} + A_ {2} ,・・・

なので求めたいA _ {i}S _ {i}S _ {i-1}の差となる  S _ {i} - S _ {i-1} = ( A _ {1} + A_ {2}+・・・+ A _ {i} ) - ( A _ {1} + A _ {2}++ A _ {i-1} ) = A _ {i}

よってA _ {1}から順番に計算して出力すれば良い。

C - Extra Character

文字列SとSのどこかに1文字追加した文字列Tが与えられるので、Tの何文字目が追加された文字なのかを答える問題。

文字列のサイズ的に線形探索してもTLEにはならないのでSとTを先頭から順番に見ていって、初めて不一致となる文字が何文字目なのかを答える。 Sの文字数分確認して不一致となる文字がなかった場合はTの最後の文字が追加された文字となる。

D - Factorial and Multiple

ある整数Kが与えられるのでN!がKの倍数となる最小のNを答える問題。

問題文を読むとKを素因数分解するか約数列挙してどうにかすれば良さそうと言うのは考えたけど、その後どうすればどんなパターンでも統一的に解けるのか思いつかなかった。

考察としては以下くらいは思いついた。

  •  2 \leq K \leq10 ^ {12}なのでO(\sqrt{N})くらいで解かないとTLEになりそう。
  • Kの倍数になると言うことはKで割った余りが0になる。(N !mod K =0)