ABC209
最近モチベーション下がっていたのと今回も下がった。
多分このままコンテスト出るとレートもモチベーションも下がり続けるので、過去解く等したほうが良さげ。
最近はpythonでばかり解くようになってきた。
Submission #24105642 - AtCoder Beginner Contest 209
- [0,9] の個数は 10 なので 一般化して[X,Y]=> (X-Y+1) 個になりそう。
Submission #24113121 - AtCoder Beginner Contest 209
- Nの制約などが緩いので普通にfor回して書ける。
- 合計 -要素数//2 とかでもだせるんじゃなかろうか。
Submission #24127335 - AtCoder Beginner Contest 209
特定の順番だと簡単に考えられる
- Ci<=Ci+1 が成り立つなら、 Ciで1つ数を選んだ分 Ci+1 のときに選べる数が減る ような計算ができる
- そうじゃない時どうするか？
- Ci>Ci+1 になってしまうと 先に選んだ数が、次の選択範囲に入るのか？で計算が面倒くさそう
- DPかと思った
- Ci>Ci+1 になってしまうと 先に選んだ数が、次の選択範囲に入るのか？で計算が面倒くさそう
- ソートしてもよさそう、に気づくまで時間がかかった
- Cn = {3 5} と Cn={5 3} とかは同じ値になるはずなので計算しやすいように昇順ソートする
- 後からコード見て考えると、掛け算なんだから順番変えて結果変わらん
D
Submission #24170364 - AtCoder Beginner Contest 209
コンテスト中に解いていない/解けなかった
- Floyd-Warshall とかで 全点間最小距離 を一度計算して、それ使ってQuery処理するんだろうけど
Floyd-Warshall 書けないので投げた
- 実際に後で書いてみたら Floyd-Warshall だと TLEする (N=105 で 3重loopするんだからそれはそう)
- 問題文の 頂点と辺の数、すべて連結しているとのことからグラフが木と断定できるらしい
- 気づかなかったけど確かにそうっぽい
木だとわかると 2点間の距離の偶奇は ある頂点 を 根として計算すれば出せる
- Queryはたくさんあるので逐一求めていたら まずい。のでcacheする
かなりバグらせたよ。
- これくらいは多くても5WAくらい、可能なら1WAで通したい。
- 日本語だと ワ―シャルフロイド だけど 英語だと Floyd-Warshall が引っかかる…？
感想
C/Dがモチベーション下がる問題だった。
全然精進してないので周囲のレベルアップに置いて行かれるのは仕方ないんだろうけど…
- 個人的にはどちらも簡単ではない問題だと感じたが...
- Atcoder Problems で見るとCにいたってはなんと灰色
- 茶色ですらない... (感覚的には 茶色の中～緑の低 くらい？)
- C提出で 30min 切っていたので、まぁそこそこのscoreだと考えてもうここで読書に切り替えたりしていた。
- D、もう少し頑張っても良かったかもなぁ...
(新しく出た問題は自分が理解できる解説が見つからないことが多いので、結局解く意味があんまりなかったりするという偏見があるのでとっとと諦めがち。)
