ABC188に挑戦しました

挑戦

競技プログラミングに挑戦するということで、ひとまずABC188にチャレンジしました。 過去に何回かやってたこともあり、ひとまずA~Cまでは解けました。(C がACされたのが47分かかっていました)

C問題でのミスの原因

Cは1回失敗してしまいましたが、その原因が関数の範囲を認識していなかったから。 トーナメントの準優勝を求めるということで、右側の最大値と左側の最大値のうち小さいほうを選択すれば答えがでる!とひらめいたまではよかったのですが、 *max_element()関数への値の与え方を勘違いしました。

 int leftmax = *max_element(A.begin(), A.begin() + N / 2); 
-int rightmax = *max_element(A.begin() + N / 2 + 1, A.end()); 
+int rightmax = *max_element(A.begin() + N / 2, A.end());

*max_element()に与える引数の範囲は[first, last)のため、+1する必要がなかった、、、

C++を普段使っていないからなのか、関数を使うのに正直戸惑います。 (普段はTypeScript(JavaScript)を使っているので、全然配列のイメージとかが違うんですよね…)   D問題も考えはしたのですが、愚直な実装をした結果サンプルに10秒くらいかかってしまって断念しました。

あとから解説を見ると座標圧縮とかいもす法とか知らないことがいっぱいだな、という感じでした。 解説で使われている手法は単純にイベントとして情報を持たせることをしていたので、そこは理解できたと思います。

ひとつわかったのは、D問題レベルになると、2重ループした時点でTLEになること。 愚直な実装はダメで、問題を分解して少なくとも1重ループ(O(N))に落とし込まないといけないですね。

新たな今年の目標

新しい目標として、頑張ってD問題が解けるようになれるように頑張りたいと思います。 今年度中に、いわゆる茶色というのを目指してみようかと思います! AtCoder Problemsを見ると、D問題にだいたい茶色がついているので、まずは底を目標にします。 ちなみに現在レートは190です。アルゴリズム力がないことを公言してしまっていますね。