Atcoder Beginner Contest 038

AtCoder Beginner Contest 038 - AtCoder Beginner Contest 038 | AtCoder

意識しようとしたこと

• 問題の疑問点はすべて解消する
• 自分でミニマムケースを作る
• エッジケースを考える
• 解き方を思いついた後、穴がないかしっかりと疑う時間を作る。

ABC問題なし。

D

ツリー構造にすると、箱の比較が減るのでは

AtcoderBeginnerContest/d.cpp at master · kitabatake/AtcoderBeginnerContest · GitHub

クラスベースでツリー構造はイメージ通りに実装できたが TLE .

このように少し複雑になった時のオーダー数がさっとイメージできていないのが課題。

解説動画を見て。

AtCoder Beginner Contest 038 D問題 ニコニコ動画講座/動画 - ニコニコ動画

物凄く解りやすくて尊敬。

• データを座標上にプロットしてみることで何か発見できることがあるかも？

• DPを使う際の基準として、ステップごとに確定していくデータがあるというのが大事と思った。 今回のケースでは、wで昇順にソートして、小さい順に箱に入る数を見ていく。（以降に見る箱は以前に見る箱には入らないため、順に確定していく）

• セグメントツリーを実装して解くことができたが、このデータ構造がどういったケースで有効かがまだよく解っていないため考察する価値がありそう。

振り返り

今回の問題は問題の理解自体はそれほど難しくなかったため、「意識しようとしたこと」がうまく当てはまらなかった。

ABC, C++自体に若干慣れてきた感があるけど、今回のD問題は難しかった。

一般的なデータ構造の理解し、問題の理解、分解、抽象化からデータ構造の選択がスムーズにできるようになれば少し変わってきそう。