ABC207の感想
AtCoder Beginner Contest 207に参加しましたのでその感想を書いていきます。問題はこちらから。
結果はこんな感じでした。
ABC(45:40+0WA)
順位 2501 / 8401
パフォーマンス 949
３完でした。しかし、D以降はとっても難しいようでしたのでこんなもんでしょう。今回はDを飛ばして、Eを考えてました。解けませんでしたが、あと一歩のところまで迫りまることができました。でも、その一歩が遠いのかもしれません。また、C問題でさえ（さえっていうの失礼かもしれません）結構難しかったです。なかなかにスリリングな回でした。でも、これはこれで楽しめたので問題なしです。
感想いきます。
A問題
３つの数字から２つ選んでその最大値を出力します。この問題で一番苦戦したのは、VisualStudioが故障したことです。もうね、本当に焦りました。
急いで、VisualStudioの新しいプロジェクトを作りました。が、いつもは競プロで
#include <bits/stdc++.h>
を読み込んでいるのですが、これは自作しないといけないので、デフォルトでは入っていません。さらに焦ります。
結局おとなしくコードテストを使いました。オンラインの環境が整っているの素晴らしいですね。助かりました。
問題自体はなんかちょちょいとやりました。
B問題
この問題はまず理解するのに5分ぐらいかかりました。入力の値が４つもあるのでとても難しかったです。
結局、色々考えた結果1回ずつシミュレートしていこうという結論になり、for文を回しました。でも、どこまで回せばいいのかの検討が付きませんでした。
B問題なんだからO(1)ってことはないだろう、というとんでもない考察をした結果よくわかりませんが、1e7まで回しました。結局これでACです。ホッとしました。
コンテスト後にTwitterで同様の議論がありまして、どうやら1e5が最大のようです。よかったよかった。
C問題
この問題はとても難しかったです。まず、嘘解法に走ります。
開区間と閉区間がありますので、Lが開区間なら+1、Rが開区間なら-1としました。制約をみるに、O(N^2)で間に合うことはわかっていたので、上記の値を用いて判定を行いました。2つの区間の大小はわからなかったので、そこを場合分けして書きました。
とすると、サンプル２は通るのに、サンプル１がダメでした。ここから迷走を始めます。
まず、ダメな例として、両方とも開区間でR=L+1の場合には、すごいことになります。L=3,R=4なら上記の計算後L=4,R=3となりますね。よくわかりません。なにを思ったかこれを不適な例とみなしてしまい。L=2e9,R=-2e9として、計算を進めました。
でも、サンプルをもう一度眺めてみると、(3,4)って不適でもなんでもないなあ、ということに気づきました。でもどうやってやるんだろう。
次に思ったのが、開区間の表現を0.5とする方法です。今思えばこの方法で十分ACできますね。ただ、コンテスト中は区間の端で一致する場合に浮動小数点誤差で＝が取れないなあ、と悩んでしました。このあたりで、40分ぐらい経っていましたね、焦る焦る。
ここで、上の考えをちょっと派生させて、各値を*2して開区間を-1と表現することを思いつきました。これ我ながら天才だと思いました。それと同時に、C問題難しくないですかね？と思わされました。
結局この方法で無事ＡＣです。難しいですね。
でも、ＷＡを出さなかったのは褒めてもいいと思います。よく最後まで詰め切りました。
D問題
ちらっと見ました。Ｅの方が解かれていたのと、なんか苦手そうな波動を感じたのでＥに行きました。
E問題
この問題の解法は一瞬で浮かびました。なんか似たような問題を何問か解いたことがあります。ただ、一つ不安なのが計算量です。
dpで、j番目を見ているときに、直前の区間端がk番目で、i個目のグループの時、の組み合わせ数
を管理すれば解けるのですが、これの計算量はO(N^3)です。ドキドキしながら、また添え字をバグらせながら実装を進めていきました。
サンプル１だけどうしても会わなくて１５分ほど格闘していましたが、残り時間10分ほどで何とかプログラムは完成。
O(N^3)ですが、定数倍は軽いので、そのあたりがうまいことなんとかしてくれないかな、と淡い期待を抱きながら提出。ＴＬＥです。まあ、そうですよね。甘くないか。
結局残りの10分も諦めずに高速化できないかもがいてましたが何も浮かばず、時間切れです。悔しいです。でも、よく食らいつきました。
F問題
みてないです
あとがき
今回は全体的に難しかったと思います。結果として、早解き勝負になってしまいレートは落ちてしまってます。でも、自分の実力よりもちょっと（かなりかもしれません）上の問題でもがくのはとっても面白いです。解けないと悔しいのはもちろんそうなのですが、時間が迫り焦る中、絶対倒してやると燃える感じ。大好きです。この瞬間が競プロで一番好きかもしれないです。
次回は解いてみせます！と毎回言っている気がしますが、まあそのうち解けるでしょう。解けるといいなあ。まったりと精進します。のんびりいきましょう。
この記事が気に入ったらサポートをしてみませんか？