ルール(？)
- AtCoder ProblemsでRecommendされた問題のうち、Moderate以上の難易度*1のものを1問以上解く
- 日曜日スタート、土曜日はABCがあるので基本お休み(3ACできるよね、という自分への圧)
- 眠さに負けてStreakが切れてもめげない。また次の日やればいいじゃないの精神
- 虚無埋め*2を考えるくらい疲れてるなら寝る
今週のおすすめレート: 665
要するに日曜に問題を解こうとしたらリストの一番上にあった問題のレート(自分のレートに依存するのでABCにRatedで参加する度に変わるはず)
ABC267がまたなんとも微妙な結果で下がる。累積和ェ…
ただ残り20分切ったところでDPの問題を解き始めて、時間内にほぼ解説通りの内容で提出出来たのは成長だと思った。初期値ミスってコンテスト中にAC出来なかったけど……
ということで今週も競プロ典型 90 問の問題をやっていく。
やった問題
2022/09/04
競プロ典型 90 問: 003 - Longest Circular Road(★4)
- 自力AC？ 🙅
- 所要時間: 56分
これは無理だと思って早々に解説を読んだんだけど、正直読んでもしばらくよく分からんかった。
手元で図を描いてみた限り、というか解き方がそれを前提としているのでそうなんだろうけど「道の数はN-1本」かつ「任意の都市間は1本以上の道路を通ることで移動できる(＝孤立しているノード(群)は存在しない)」場合は閉路はできないことが保証されているようなので、そこから「最短距離の最大値」を求めていくことになる。
慣れてないと本当かなってそもそものところで悩んじゃうんだけど、まぁこの条件で木構造で表現できることを示唆しているんですよと言われればそれまでの話ではある。
まずは1とか適当なノードでBFSを最後までやって最短距離が一番長いノードを探す。
その「適当なノードから一番遠かったノード」の1つ(提出結果を見る感じ多分どれでもいい)を根としてもう一度BFSをかけ、一番遠かったノードまでの距離が木構造全体の最大の最短距離となり、これを「木の直径」と呼ぶらしい*3。
2回目に根にしたノードから一番深かったノードの一つへ道を通せばスコアの最大値とすることが出来るので、木の直径＋1が解となる。
ということで、木の直径という概念とその求め方を知っていればサラッと解けるタイプの問題。知らないと頭抱えてしまうやつ。多分次は大丈夫。
2022/09/05
競プロ典型 90 問: 007 - CP Classes(★3)
- 自力AC？ 🙆
- 所要時間: 13分
参照する値を先にソートしておいてひたすら二分探索していくパターンのシンプルな問題。
検索条件をa_i >= b_jとしたとき、差が最小になりうるのは取得できたb_jと一つ下のクラスなので、値そのものではなくbsearch_indexで検索するのと比較を忘れないようにするあたりがポイントかなと思う。
2022/09/06
競プロ典型 90 問: 008 - AtCounter(★4)
- 自力AC？ 🙅
- 所要時間: 33分
前に解いたやつになんか類題あったよなぁって思ったらやっぱりそんな感じ。比較対象にする文字列が固定だし、組み合わせの数を答えるだけなのでこっちの方が数段簡単なはずなんだけども。
薄々DPかなと思いつつさっさと解説を読んでしまったが正直まだ飲み込めてない。書きあがってしまえばシンプルなコードなんだけどなー。LCS絡みのDPはもうちょっと練習が必要そう。
2022/09/07
競プロ典型 90 問: 012 - Red Painting(★4)
- 自力AC？ 🙅
- 所要時間: 55分
ついに来たかUnionFind。
「移動できるマスのグループを管理する」という発想には至ったものの、25分くらいかけて書いたコードがTLE起こしたので諦めてUnionFindの仕組みからお勉強。
なんか都度組もうとするとマージあたりで悩みそうで、一度データ構造を作っておけば使いまわしがきくっぽいのは助かる。*4
といいつつ、わりかしシンプルな作りなので慣れたらスニペットなしでもいけそうだけど。
2022/09/08
競プロ典型 90 問: 014 - We Used to Sing a Song Together(★3)
- 自力AC？ 🙆
- 所要時間: 3分
N人に対してN個の学校しかないので、どちらも昇順に並べてあてがうしかないよね、と考え、その通りにコードを書いて恐る恐る提出したらそのままAC。この手の解法を貪欲法と呼ぶらしいんだけど、資料を読んでみてもどの辺のことを指しているのかが良くわからないあたりがなんかDPの説明と似ている。
2022/09/09
競プロ典型 90 問: 016 - Minimum Coins(★3)
- 自力AC？ 🙅
- 所要時間: 57分
うまいこと無駄を省いていく系の全探索。
一般的に流通している硬貨セットであれば単純な貪欲法で行けるらしいと昨日読んだ資料に書いてあった。が、今回はなんとも中途半端な額だったりなんだりで多い方から安易に取っていっても最後に割り切れなくなることが多いので、上手いこと探索数を減らしつつ全探索をやっていくパターン。最後どうしても剥がれなかったTLEの参考にRubyのACコードを読んだところ、 1つめのループ1つあたり1回ずつ余計に回していた差で少なくとも300msくらいのロスをしていたらしいことが分かる。これはシビアですわー
