ルール(？)
- AtCoder ProblemsでRecommendされた問題のうち、Moderate以上の難易度*1のものを1問以上解く
- 日曜日スタート、土曜日はABCがあるので基本お休み(3ACできるよね、という自分への圧)
今週のおすすめレート: 757
要するに日曜に問題を解こうとしたらリストの一番上にあった問題のレート(自分のレートに依存するのでABCにRatedで参加する度に変わるはず)
直近のABC259で自己ベストパフォーマンスを叩き出したのでだいぶレートが上がった模様。 それでも先々週より低いんだけど、ちゃんと毎日1AC出来るのか土曜の時点ではドキドキしてた。
やった問題
2022/07/10
眠すぎて無理でした…
2022/07/11
- 自力AC？ 🙅
- 所要時間: 1時間
40分悩んでj - i != k - j問題をどうにか出来る気がしなかったので 解説を読む。
Array#tally というメソッドを知る。結構使いたいパターン多そうなやつ。(前にやった問題にも使いたいパターンあったような…)
解法が分かってしまえばわりとシンプルで、別に場合分けをゴリゴリする必要もなくR、G、Bのリストからそれぞれ選んでインデックスの小さい方から並べたら1つ目の条件満たす組み合わせを数え上げできるよねという話。
そこからj - i == k - jなものを取り除けばよいわけで、そっちは素直にループ回して条件満たす分だけ合計から引いていけば答えになる。
これ自力でたどり着けなかったのちょっと悔しいなー。
2022/07/12
ABC243: D - Moves on Binary Tree
- 自力AC？ 🙅
- 所要時間: 45分
久々の二分木操作(と言っていいのか分からないけど)、データ構造書いてあって助かる…
ド直球で問題文通りのコードを書いて案の定のTLEから悩み、2回くらいWA食らってから解説を読んだものの、そのWAコードを粛々とデバッグしていったら普通にAC。処理回数ではなく扱ってる数字の桁数がヤバかったパターン。実際に106の入力作って確認してるんだから気付きなさいよ、という話ではある。
基本的に上下運動なので昨日の問題みたいなノリでLとRの個数とかから求められないものかねと一瞬思ったものの、順番入れ替えるとやっぱり位置が変わってしまうのでむりぽ。
2022/07/13
やろうとしたら日付を跨ぎメンテが始まってしまいました😇
2022/07/14
- 自力AC？ 🙆
- 所要時間: 5分
(全力のドヤ顔)
掛け算は因数を1つでも0にすれば0になるので、最小数は多く見積もっても+でsplitしたそれぞれの項の数になる。もともと0が含まれていればスルー、そうじゃなければ数え上げに加える。多めに見積もっても5万なので、素朴にループぶん回せばOKぽい。
ACしたコードだと因数1個ずつ分けて確認してたけど、数字は必ず1桁という制約があるのでformula.include?("0")でよくないか、ということに後から気付く。
これ引き算含んでたらもうちょい面倒そう。
2022/07/15
- 自力AC？ 🙆
- 所要時間: 1時間40分
変なところで変な悩み方をして時間を浪費している。AGCのA問題なので実際のコンテストでも時間内にギリギリ解けた計算ではあるが、初見がABCのC問題だったらぶっちぎりの物理TLE。
問題としては配列をひっくり返すのがポイントなくらいであとは地道に必要な値を計算していけばOKで、変に凝ったことやろうとしなければ多分30分くらいで解けたのに勝手にこんがらがった感じ。自力で解けたけどとてもくやしい。
ABC211: D - Number of Shortest paths
- 自力AC？ 🙆
- 所要時間: 1時間50分
変なところで時間を浪費しちゃったパート2。競プロ問題では初BFS体験かもしれない。既知のノードを安易にスキップするとまずいんだけど、サンプル問題で気付けたのでありがたかった。 「その値が出現したか」をチェックするのにいつも通り配列を使ってTLE起こしてたのをハッシュのキー存在チェックに置き換えただけで爆速になってビックリしました。適切なデータ構造って大事。
1つだけどーーーしてもWAのままのテストケースがあり30分を無駄にする。このテストケースだけ他と比べて異様にメモリ食ってるので気味悪く感じつつ、問題文をよく見なおしたらいつもの109+7で剰余を取るパターンで、そこだけ直したらあっさりACで気が抜けた。問題文はしっかり読みましょう。 まぁそれ踏まえても1時間は超えているのでもう少し慣れないとダメそう。
珍しくコミットを分けていたので、悩んでいる痕跡を見たい方がいらっしゃいましたらこちらからどうぞ。
2022/07/16
ABCは日曜だし、2日くらい休んじゃったし、金曜もちょっと頑張ったから2問くらい解こうかしら、ということで無謀にもARCにRated参加して砕け散った後に2問ほど。 実はレート変化した影響でおすすめレート下がってるんだけど、どっちにしろレート変わるでしょって思ってARCの前にやる問題を抽出しておいたので一応この日も今週のおすすめレート付近の問題。
- 自力AC？ 🙆
- 所要時間: 3分
大変シンプルなコードとなっております。特にRubyの場合は気付けば瞬殺、という感じ。
どう考えても端からコツコツと色を変えていくしかないので、String#squeezeで隣り合わせの文字を全部圧縮した文字数 - 1が正解。squeeze的なメソッドがない言語だと、先頭から順に走査して手前の値と違う値であればカウント可算、みたいなことをする必要がありそう。
- 自力AC？ 🙆
- 所要時間: 30分
1を開始地点としたときのルートを新しい配列に取って、どこかで必ずループが発生するはずなのでループの発生地点をチェックする。ループ突入を確認したらループ内のどこにいるかを計算で求めれば多分O(N)くらい？ ここまで書いたところで解説を読んで「ダブ…リング…？」となったので、茶色の問題でもまだまだ覚えることは多そう。
*1:もしくはそれに近い難易度
