ルール(？)
- AtCoder ProblemsでRecommendされた問題のうち、Moderate以上の難易度*1のものを1問以上解く
- 日曜日スタート、土曜日はABCがあるので基本お休み(3ACできるよね、という自分への圧)
- 眠さに負けてStreakが切れてもめげない。また次の日やればいいじゃないの精神
- 虚無埋め*2を考えるくらい疲れてるなら寝る
今週のおすすめレート: 672
要するに日曜に問題を解こうとしたらリストの一番上にあった問題のレート(自分のレートに依存するのでABCにRatedで参加する度に変わるはず)
直近のABC266で終了ギリギリの3完だったので、レートも初めて下がってしまいました、悲しい。
やった問題
2022/08/28
- 自力AC？ 🙆
- 所要時間: 9分
シンプルに部分文字列のバリエーション数を求める問題。長さは最大300なので、前から素直に流していっても十分AC。
2022/08/29
- 自力AC？ 🙆
- 所要時間: 5分
頭から順に比較していってジョーカー(？)だったら相手方の文字が交換可能な文字かどうかを判定すればよいのでわりとシンプル。 どうでもいいんだけどテストケースが今まで見たことない数あってビビった。
2022/08/30
体調が微妙だったのでお休み
2022/08/31
昨日に続き体調が微妙だったのでお休み
2022/09/01
何となく思うところがあり、しばらくの間競プロ典型 90 問の★3～4の問題を解いていくことにする。
90問中条件を満たすのは全部で3534問あるらしいので、向こう2か月弱くらいで消化できるかしら。
競プロ典型 90 問: 001 - Yokan Party(★4)
- 自力AC？ 🙅
- 所要時間: 29分
解で二分探索するパターンの典型問題らしい。13分経過くらいで平均値と分割位置双方の総当たり以外のまともな解法が出てこなかったので諦めて解説を読んでAC。
1～平均値の範囲で所定の長さ以上のようかんを指定個数(以上)作れるか、というのを二分探索で調べていく。
dividable?の内容はだいたい想像通りではあったけど、これの長さを二分探索で絞っていくのは思いつかなかった。まぁ、まさにこういう経験値を稼ぐためにやってる感じ。
2022/09/02
ABC266: C - Convex Quadrilateral
- 自力AC？ 🙅
- 所要時間: 35分
直近のABCでの因縁の問題で(おそらく出題者の意図した)間違いが少なく解ける解法があったのでそっちで解いてみた。当日は凹み過ぎてそれどころじゃなかった…… 一応「ベクトルの外積を求めれば判定できる」ってのはコンテストで解いてる間に分かったんだけど、大学数学をさっぱり覚えていないのがここで響くとはね、という感じ。 コンテスト当日にやった方法も後からユーザ解説で入ってたので裏技って程でもなかったんだけど中学数学の知識で行ける代わりにコードが複雑になる。コード行数で言うと今回16行で解けたコードが32行になったので、ちょうど倍ってところ。
競プロ典型 90 問: 002 - Encyclopedia of Parentheses(★3)
- 自力AC？ 🙆
- 所要時間: 28分
余力があったのでもう1問。辞書順ソートはカウンタの値を二進数変換することでクリア、カッコの対応は前から走査して開きで+1、閉じで-1して最終的に0になればOKと判定、2n-1以降は絶対に成立しないのでその手前で検証を止めれば実行時間もクリア。
別解も提出してみたものの、最初に0の個数を数えてちょうど n / 2にならなければ検証をスキップする方が若干早く終わるらしい。
