ルール(？)
- AtCoder ProblemsでRecommendされた問題のうち、Moderate以上の難易度*1のものを1問以上解く
- 日曜日スタート、土曜日はABCがあるので基本お休み(3ACできるよね、という自分への圧)
- 眠さに負けてStreakが切れてもめげない。また次の日やればいいじゃないの精神
- 虚無埋め*2を考えるくらい疲れてるなら寝る
今週のおすすめレート: 794
要するに日曜に問題を解こうとしたらリストの一番上にあった問題のレート(自分のレートに依存するのでABCにRatedで参加する度に変わるはず)
先週末のABC (AtCoder Beginner Contest 273)
3完だったんだけど難しめというかCとDの落差が大きかったからか緑パフォーマンス継続。
D問題でだいぶグダグダしてしまった。終わった後に解けてみるとこれ取りたかったなぁっていう悔しさが出てくる。が、ABC270の時並みの奇跡のデジャブでも起きないと今の私には厳しかったのはdiffを見ても明らか。
そのD問題は素朴にやってまぁダメですよねとなり、「これ進行方向の一番手前の壁の位置をサクッと探る何かないと無理でしょ」っていうところまでは気付く。
が、それ以前にランタイムエラー起こしまくって何事かと思ったら109 * 109の配列なんて宣言出来る訳ないということに気付いたのがコンテスト終了50秒(!)前。そのあとも解説やら他の人のACコードやらを読んでもなかなかWAが剥がれず、とりあえず寝てバグ取りしましょってなって当日のupsolveチャレンジは終了。
コンテスト中の時間圧迫要因としてE問題にうつつを抜かしたりしてたこともなくはないので「D-E間で難易度逆転したところでそれは概ねDがやたら難しいというだけであり、今の実力ではDが解けないなら大体Eも解けないよ」ということを肝に銘じておこうと思います。気分転換にはいいんだけどね……
余談なんだけど、「コンテスト中に得点を多く稼いだ方の勝ち、同点なら早い方が勝ち」というところまでは知っていたものの、得点とペナルティ可算後のタイムが一致した場合はどうなるのと思ったら、ペナルティの数や解いた問題数に関わらず、合計得点とペナルティ可算後のタイム*3が一致する場合は同率順位になるっぽいということを知る。
やった問題
2022/10/16
土曜日に解けなかったD問題をupsolveしようとしたら頭が回らずそのまま寝ました。
2022/10/17
- 自力AC？ 🙅
- 所要時間: 多分30分＋当日2時間くらい
コンテスト当日にさっぱり解けないまま終わった問題を、16回目の提出でようやくAC。
ランタイムエラーの原因に早く気付いて縦横それぞれに壁の位置持たないとダメだってところまで1時間経過くらいまでに気付けてればもしかしたらワンチャンあったかねぇという感じ。
前述のとおり当日あまりにもWAが剥がれず、他の人のACコードを見ても何が違うのか分からなかったのでもう一度コードなぞってダメだったらもう写経するか？となって多少手直しをしたコードを提出したらあっさりAC。
どうもインデックスを遡る方向で進行方向一番手前の壁のインデックスを間違えてたのが決め手っぽく、よくコードを見たら1引くの忘れてた。とりあえず自分で考えたコードでAC出来てよかった。
- 自力AC？ 🙅
- 所要時間: 多分30分くらい
青diffなので正直私にとってはかなり難しめなんだけど勢いでE問題もupsolve。
「実はそのときの末尾の値さえわかれば良くて、全体の情報は不要であること」「直前の状態を指さすことができること」あたりに気付いて木というかGit的な構造がイメージ出来れば、コード自体はD問題よりシンプルに(解説を読みながら)書けた。問題から解法を見抜いて使いこなすにはもうちょっと慣れが必要そう。
2022/10/18
競プロ典型 90 問: 048 - I will not drop out(★3)
- 自力AC？ 🙅
- 所要時間: 38分
ナップサック類題の二次元DPと見せかけて貪欲法で行けますよっていうか貪欲法じゃないと間に合わないパターンの最適結果を調べるタイプの問題。ちょっと貪欲法がどういうものか分かってきたかもしれない。
実際Nの最大値が2×10^5でKはその倍まであるのでちゃんと考えたら少なくとも二次元DP無理でしょっていうのは気付ける問題ではある。一般的にループ回数は109くらいが限界って言われるので、1010だとC++でも無理なのでは……
ちなみに解説の解法を適用させるにあたって地味に「部分点は満点の半分より大きい」という条件がポイントで、これがないと降順ソートかけたときに追加点のほうが先に来てしまう可能性があるので問題が一段階ややこしくなる。そうなるとソートの条件を増やす方向になるのかなぁって思うんだけどそれで行けるんだろうか。
メタいことを考えると、C問題でこの手の問題だったら深く考えず貪欲でやってしまってもいいのかもしれない。これがNが1000くらいで、かつ解答にかかる時間が問題ごとにマチマチであれば重量を解答時間に、価値を得点に読み替えたナップサック問題になるのでD問題でDPになるよって感じかな。
2022/10/19
競プロ典型 90 問: 050 - Stair Jump(★3)
- 自力AC？ 🙆
- 所要時間: 10分
方針さえ決まればシンプルに組み合わせ計算を繰り返す問題。
L段進むことを選べる回数は最大でn / l回で、L段進む回数が決まればあとは1段ずつ上がっていくしかないので、「進む段数を選ぶ回数」というのはL段進む回数 + (n / l - L段進む回数) + n % l になるので、これとL段進む回数とで組み合わせを計算するのを0からn / lまで繰り返す感じ。組み合わせ計算はスニペット持っておくのが楽そう。
……とまでメモを書いてから解説を読んだら一次元DPで解いてた。Rubyのコードだと実行時間短い方から5人くらいほとんど組み合わせ計算でやってたけど、どっちでも書けるのが一番だと思う。
ABC268: C - Chinese Restaurant
- 自力AC？ 🙆 (今回解説を読まずにACしたという意味では)
- 所要時間: 13分
一応当日upsolveしているんだけど、どうしても引っかかっているトラウマ回の復讐復習。
問題を理解できていれば、皿の位置をどうやって求めたらいいのか問題文で説明している親切設計ではある。(p_i - i) % nで「皿p_iはいくつずらしたら人iの正面に来るのか」を求められるので、皿ごとにずらすべきオフセット回数を投票していくようなイメージ。両脇もOKということで真正面に追加で-1、+1のところにも投票していく。あとは投票用の配列の最大値を取ればOK。と読み解いてみれば確かに茶diffだよねっていう問題なんだけどなぁ。今度類題出たら絶対正解してやる……
2022/10/20
競プロ典型 90 問: 052 - Dice Product(★3)
- 自力AC？ 🙆
- 所要時間: 6分
数学的考察ってほどでもないんだけど、先にサイコロ2個くらいで愚直に式作ってみるとスムーズに解ける問題。
解説に因数分解って書いてあるから構えちゃうけど、サイコロA・Bの目をそれぞれa_1～a_6、b_1～b_6として、
a_1 * b_1 + a_1 * b_2 + ... + a_6 * b_6
→a_1 * (b_1からb_6の和) + a_2 * (b_1からb_6の和) + ... + a_6 * (b_1からb_6の和)
→(a_1からa_6の和) * (b_1からb_6の和)
と変形できるので、じゃあそれぞれのサイコロの目を足したものを順に足して掛けていけばいいよね、と考えることが出来る。
2022/10/21
競プロ典型 90 問: 058 - Original Calculator(★4)
- 自力AC？ 🙅
- 所要時間: 35分
なんだか不思議な演算を延々としていくんだけど、規則性を見出してショートカットする問題。
延々と法則性の見えない変化が続くかと思えば、どうも計算量的に有効な範囲でループすることが保証されている(？)らしく、Hashか何かで出現タイミングのインデックスを記録しておいて、ループを検出した時点でループのサイズと残りの移動回数から最終的な到達点を計算すればOK。Kがループ手前で止まるようであれば素直に指定された演算をやっていけばいい、らしい。
むしろ類題として指定されてた前に解いた問題の方が構造がはっきり見えている分すんなり解けたんだよなぁ。
