AtCoder Beginner Contest 322に参加しました。
結果
A,B,Cの3問正解でした。
C問題まではサクッと解けて、D問題は手間がかかりそうだからD問題よりは簡単そうに見えたE問題を先に解くことにした。
でもE問題をバグり散らかしてたのでサンプルケースは通せてもACは取れなかった…
コンテストのほとんどの時間をE問題に充てたことになるけどそれでも解けなかったのはちょっと力量が足らなさすぎる気がする。
解き方の方針自体は解説と合っていたのでサクッと解いておきたかったなあ
A - First ABC 2
与えられた文字列の中でABCと並んでいる場所を探して1番最初の文字位置を返す問題。
文字列を線形探索してA,B,Cが並んでいる場所を探す。
文字列検索なのでライブラリを使ってサクッと解くこともできそう。
B - Prefix and Suffix
文字列が2つ与えられるので一方がもう一方の接頭辞や接尾辞になっているかを判定して4通りあるパターンそれぞれに対応する指定値を出力する。
文字列の長さは長くないので接頭辞や接尾辞の判定は文字列検索で十分間にあう。 接頭辞かどうかのフラグと接尾辞かどうかのフラグを用意して、 各フラグの状態から4パターンのうちのどれに該当するか判断する。
C - Festival
N日間のうちどこかM日は花火が上がる、 指定された日付のうち1番早い花火が上がる日まで何日かかるかをN日分出力する問題。
花火が上がった日でカウントを0にリセットして、N日目から1日目まで順番に最後に花火が上がった日からの日数をカウントしつつ配列に入れていけば簡単に解ける。
前から考えると大変だけど後ろから考えれば簡単に解けるようになる問題。
E - Product Development
DPで解ける問題。
N個アイテムがあって、選択するとK個中k番目の価値がだけ上昇する。
K個すべての価値をP以上にするときの最小コストを答える問題。
ほぼ解けてると思うけど、一部バグがあるみたいでテストケースが6つくらいWAだった…
DP[i番目のアイテムまで確認した][i番目のアイテムを選んだ/選んでいない][パラメータ]=最小のコスト
として計算していくことにした。
パラメータもP進数K桁の数値として処理した。 そうでもしないとパラメータKの値に応じてDPの結果を管理する配列の次元数を変えないといけなくなる。 それはちょっとめんどくさいのと、各パラメータの上限Pは1桁だったので パラメータをK桁として管理することにした。
