ABC154
ABC154に参加しました。
四完で初めての茶パフォで、あと11で緑でした。D問題でかなりもたついたので、それがなければ緑だったかと思うと悔しいです。
復習というか、E問題が解説を見てもなかなか理解できなかったので記事にするのが遅くなりました。
私の書いたコードはAtCoder上のABC154提出結果をsaikatotoで検索していただくと、みることができます。
考えたこと
文字列S,Tのうち、文字列Uと一致したものの個数をマイナス１してS,Tの数をそれぞれ出力しました。
考えたこと
文字列Sの大きさをLとして、L回S.at(i)にxを挿入しました。大きさLの配列をxで初期化して、L回出力してもいいのかなと思いましたが、今回はSを書き換えることにしました。
考えたこと
配列で受け取り、ソートをかけました。同じ要素があった場合、ソートをかけると連続して並んでいるはずなので、i, i+1をn回比較してあげればいいと考えました。setはほとんど知らなかったので勉強しました。
考えたこと
いったんそれぞれのサイコロが出す目の期待値を出しておくことにしました。i番目のサイコロの期待値は(1+i)/2で、それを配列の中に格納しましたが、この時にint型を割り算すると、あまりは切り捨てられることを失念していました。具体的には(double型) = (int型) / 2とすれば小数点以下まで計算してくれると思っていました。このことに気づかず、10分ほど余計な時間がかかったのは反省しました。また、どうせすべての期待値が/2されているので、最後に/2をすれば余計な手間がかからずに済みました。さらに途中の処理が間違っているのではなく、数値型が間違っているということにもっと早く気が付いたかもしれませんでした。もったいなかったです。
配列に格納した後、最初からK個を足して、答えを保持する変数を用意し、その後新しい期待値を一つ足して、一番先頭の期待値を一つ削除し、保持している答えと大きさを比べる、ということをN-K回繰り返しました。これでもAC出来ましたが、累積和の問題を解いたばかりだったので累積和については知っていたはずだったのですが、累積和の考え方できれいに解けるということを他の方の解説を見て理解しました。
考えたこと
100桁はどうやっても数値型では受け取れないので(多分)、string型で受け取って配列にint型で一桁づつ格納したら処理ができるのかなということまでは考えました。その後、0でない数字が出てくる桁を決め、場合分けして考えるのかな、でもこれだとNより大きいかどうかも個別に考える必要があって、機械的に処理できなさそうだな、というところまで時間内に考えて諦めました。
コンテスト後の解説を見て、桁DPについて勉強しました。適切な配列を用意し、大きい位から順に全探索的に各桁の数字を決めていくと状態の遷移という形で場合分けをするという考え方で、コンテスト中に私が考えた方法とは全く違うアプローチだと思いました。受験数学の感覚だと、ひとつづつ数字を当てはめて考えるのは三桁にもなれば現実的ではないので、すぐに場合分けをしていくという発想になりがちかと思います。”1秒間に10の8乗回の処理ができるコンピューター”で、早く処理ができる方法を考えるときには、順番に当てはめていってその中でうまく場合分けをする、という手順で考えていく必要があるのかなと感じました。かなり分かりにくい日本語で申し訳ないです…。
この後自力でコードを書きました。多次元配列を管理したい状態分用意してあげて、それぞれの状況ごとに遷移を考えていくという手法なので、配列の設定がキモだと理解しました。今回は[桁数を判定する配列][N以下かどうかを判定する配列][0でない数字がいくつ出てきたかを判定する配列]とし、それぞれの大きさを[Nの桁数＋10][2][K+1]としました。遷移を考える際、0以外の数字がすでにK回出てきているときに、0以外の数字が出てきた場合はcontinue;していたのですが、これはcontinue;で抜ける範囲がどこまでなのかを考えておらずにWAを出しました。そこで、大きさを[K+1]ではなく[110]とし、そのままKに加算することにしました。ただ、もともとK以下で変数が動くように設定しているので、余裕をもって110とするのではなく、K+2とするだけで十分でした。さらに、0が出てきたときは無条件でNより小さくなると考えて処理を書いていましたが、Nのどこかに0が含まれていた場合、小さくならずに大きさが同じままになる場合があるので、遷移式を0が出てきた時も0以外が出てきた時もどちらも[sma || x < n.at(i)]としました。この二か所で躓いたのになかなか気づけませんでした。
今回は以上です。少しづつできることが増えてきて面白いです。
