今週もAtCoderに参加しました
今週も、AtCoderのABCに参加してきました。 5問解くことができて 、気分は上々です。 サークルのほうの記事はゆっくり書こうかな…ここにはそれぞれの問題を解いての所感と、簡単な解法について触れようかと思います。
ということで念のために注意、 ABC476回 の解法への言及があります。これを読んでくれている方はそんなこと分かりきってますかね。
結果
| 得点 | A | B | C | D | E | F | G |
|---|---|---|---|---|---|---|---|
| 1475(1) | 100 | 200 | 300 | 425(1) | 450 | - | - |
| 100:33 | 1:01 | 4:35 | 15:57 | 95:33 | 55:04 | - | - |
| パフォーマンス | レート推移 | 新レート |
|---|---|---|
| 1173 ( 2382位 ) | +12 | 1067 ( highest ! ) |
考察・所感
A問題、B問題
問題なし！割愛します。
C問題
いつもC問題が安定して解けるわけではなく時間がかかることがあるのが悩みですが、今回は比較的素早く解けました。 ソートしたくなるから、毎回上位４つだけを保持すれば、そのソートには定数時間しかかからない という考え方で解きました。 heapq(優先度付きキュー)から毎回3つ目まで取り出すという書き方で途中まで書いていたのに、間違っているような気がして消してしまいました。 それがなければかなり早解きできていたのですが。
D問題
C問題以上に安定しないD問題ですが、今回解けた問題の中で最も難しいと感じました。 問題文の理解に5分ほど時間がかかりました。 ドリンクを先に買うことができればそのあとはシンプルに、kドル札を1ドル札k枚としてデザートを何個買えるかを求められそうだと分かります。 したがって、ドリンクを買う数を全探索して、そのそれぞれについてデザートを何個買えるかを求めました。 変数が多くなってくると頭のバッファに入りきらないことは分かりきっていたので、変数名をはじめから丁寧に定義していたのが良かった点です。いい感じにコーディング負担を減らせた感覚があります。
E問題
ある区間の最大値や最小値を高速に求める必要がある、要素を更新する必要がある、ということからセグメント木を使えば「更新されるべき要素の値」が分かります。 それが分かれば、各要素の値とインデックスを紐づけておいてそれも同時に更新していけば解けるということに気づきました。 添え字ミスが重なってかなり時間をかけたのと、一度デバッグ出力をコメントアウトせずに提出してしまったところが反省ポイントでしょうか。 とはいえある程度的確な考察はできていたので、嬉しいです。
最後に
5完できる回なんてそうそうないので、とても嬉しいです。 ゆくゆくは安定して5完できる力をつけたいなと思っていますが、空き時間にADTに参加する程度の精進具合なのでどうなることやらわかりません。 まあまったりいきましょう。お疲れさまでした。