ルール(？)
- AtCoder ProblemsでRecommendされた問題のうち、Moderate以上の難易度*1のものを1問以上解く
- 日曜日スタート、土曜日はABCがあるので基本お休み(3ACできるよね、という自分への圧)
- 眠さに負けてStreakが切れてもめげない。また次の日やればいいじゃないの精神
今週のおすすめレート: 646
要するに日曜に問題を解こうとしたらリストの一番上にあった問題のレート(自分のレートに依存するのでABCにRatedで参加する度に変わるはず)
土曜日のABCがまずまずの好パフォーマンスだったのでちょっと上がりました。
やった問題
2022/08/07
ABC118: C - Monsters Battle Royale
- 自力AC？ 🙆
- 所要時間: 9分
どうすんのこれ、って一瞬悩む問題。後から解説*2読んだら「競技プログラミングは時にはエスパー力が求められる。」って書いてあってちょっと面白かった。シンプルに配列全体の最大公約数を求めれば解になる。
問題文にある計算がまんまユークリッドの互除法の操作であることに気付けば自信を持って提出出来た問題。もちろん忘れてたのでドキドキしながら提出してた。
2022/08/08
- 自力AC？ 🙆
- 所要時間: 34分
AGCの問題って解法を思いつくまでがややこしい気がする。何文字かおきに文字を拾っていったら指定した2つの文字列が現れるかどうかなんだけど、x =(L / N) * i + 1 y = (L / M) * j + 1として xとyが重なる箇所すべてでs[x]とt[y]が一致すればよいので、そのチェックをしていく。
最小の文字列も何も、L = N.lcm(M)のときに条件が成立しなければどんなに値を大きくしてもダメなので、出力は最小公倍数か-1のどっちかになる。
NとMが互いに素だった場合に先頭要素の比較を忘れるというしょうもないミスで2WAのちAC。
2022/08/09
CODE FESTIVAL 2015 予選B: C - 旅館
- 自力AC？ 🙆
- 所要時間: 9分
解法としてはわりとシンプルで、一番人数の多い予約を一番大きい部屋に割り当て、2番目に多い予約を2番目に大きい部屋に割り当て、……とやっていったときに全部の予約に対して十分なキャパシティの部屋を用意出来ればOK。
部屋分割の考慮をする必要がないので、逆順ソートさえ忘れなければわりとあっさり満点回答が出来ると思う。
2022/08/10
- 自力AC？ 🙅
- 所要時間: 33分
27分ほど自力でやってどうも結果が合わないので解説を読んでAC。 「演説の費用対効果の高い順番にソートして得票見込みが上回ったらその時のカウンタの値を返す」というのは合っててそこまでは10分くらいで組んだものの、費用対効果の計算が間違っていてズルズルと20分超。
演説の効率は単純に町全体の人数でよいと思っていたけど、どのくらい差が縮むか、なので(高橋陣営が獲得する票数) + (青木陣営が失う票数)で計算しないとダメだったという算数の問題で敗北。もう同じ失敗はしないと思うけど、ミスがシンプルすぎてわりと悔しい。
2022/08/11
気が付いたらすごい時間だったのでスキップしました😇
2022/08/12
- 自力AC？ 🙆
- 所要時間: 48分
DPかしらと悩んだけどどうしてもj軸の方針が出せず、再帰もそれっぽいコードが浮かばず悩む。
ただ取引回数は多いに越したことはない操作なので、素直に翌日のレートをエスパーして有利になるなら取引する、で解いていったらあっさりAC。
正直「この難易度でこんな悩むDPの問題出るかな？」というメタ推理が入ったことを否めない。最初から頭にあった解法とは言え、本番では正確な難易度が分からない状態で解くのでそういうアプローチはよくない。
*1:もしくはそれに近い難易度
