近況報告
ここ最近このブログどころか、精進がほとんどできていなかった。というのも、自分は今修士1年でつい先日まで研究の中間発表の準備に取り組んでいたのと、就活の面接ラッシュでなかなか趣味に時間が取れない状況だった。 とはいえ中間発表も無事に終え、就活もだいぶ満足する形で終えられたので、今週からは精進する時間がしっかりと取れそうである。入水目指して頑張りたいね。
さて、AtCoderの現在のレートは1111(ゾロ目！)になった。直近4回のうち、2回は勝利、2回は変動ほぼ無しといった感じで安定感ある結果を残せている。 特にABC340については初めて6完できたし、ABC341では遅延セグ木をちゃんと使いこなせたのでとても成長を感じている。精進してないけど。
ところで、この緑diff精進についてだが、今回からRust中心で解いていこうと思う。やっぱABC341 EでPythonで書いた遅延セグ木がTLEし、Rustで書き直したら300ms台でACできた経験が大きい。再帰や遅延セグ木で殴れるがTLEが怖いなぁというお気持ちがやっぱ辛いので、制約が厳しい問題向けにRustの習熟度を上げていきたい。(あとRustで解ける問題は(BTreeSetとか使わなければ)大体Pythonでも楽に解けそうなので)
解いた問題
- ABC016 C - 友達の友達
- ABC311 D - Grid Ice Floor
- ABC075 C - Bridge
- ABC124 D - Handstand
- ABC057 C - Digits in Multiplication
- ABC293 D - Tying Rope
- ABC334 E - Christmas Color Grid 1
- ABC273 D - LRUD Instructions
ABC016 C - 友達の友達
感想 (解答中に考えたこと)
- なんかめちゃくちゃ制約が緩いので、とりあえず全探索すれば良い
提出コード
ABC311 D - Grid Ice Floor
感想 (解答中に考えたこと)
- 無難にBFSが通りそう。停止した位置についてBFSして、使ったマスを埋めていく。
提出コード
ABC075 C - Bridge
感想 (解答中に考えたこと)
- 過去に解いた記憶があるが…… UnionFindで橋判定したいもの以外を繋げて、sameかどうかを見れば橋かどうかがわかる。
提出コード
ABC124 D - Handstand
感想 (解答中に考えたこと)
- 最近のABCでセグ木の問題の設定に似てる。反転操作は境界部分を持てば区間更新を1点更新にできる。
- よく読んでみるとそんな難しいことしなくても良さそう。ランレングス圧縮したあとの
は必ず
...01010101...という格好になるので、[10101...01]のような区間で、0が個含まれていてかつこの区間が最長なものを出力してあげれば良い事がわかる。しゃくとり実装すればok。
提出コード
ABC057 C - Digits in Multiplication
感想 (解答中に考えたこと)
の制約がちょっと大きい。とはいえ
なので、
について全探索すればせいぜい
回の計算なので通る。
提出コード
過去解いてたらしい(覚えてない)
ABC293 D - Tying Rope
感想 (解答中に考えたこと)
- これは解いた記憶がある。ロープに色が云々言っているが、つまり2頂点がとある辺で繋がっているグラフが
個の辺で繋ぐことを考えれば良い。
- ある頂点は3つ以上の辺を持たないことは問題の制約により言えるので、環状の判定はUnionFindで繋ぐ際にsameかどうかを判定すれば良い。
提出コード
ABC334 E - Christmas Color Grid 1
感想 (解答中に考えたこと)
- これはそもそも出たコンテストの問題ですね。緑のマスをUnionFindで繋げて、赤のマスが緑になった際にUnionFind#groupsの長さがどう変化するかを考えてあげれば良い。
- 4方のマスを新たなUnionFindで繋げて、groupsの長さを見れば繋げた際にいくつ緑の連結成分数が変化するかが求められる。
提出コード
コンテスト中はUnionFindで繋げず、各緑の連結成分にid振ってたらしい。
ABC273 D - LRUD Instructions
感想 (解答中に考えたこと)
- どうせ愚直シミュレーション……と思い制約を確認してみるとあまりにも大きすぎてひっくり返った。
- 結局これはある進行方向に対して、直近の壁はどこにあるのかを求めることができれば良い。
- 縦軸・横軸毎にHashMapを用意し、各要素ごとにBTreeSetで壁の情報を追加する。進行方向は4方位のどれかなので、現在地点から進行方向にある壁のBTreeSetについて二分探索で直近の壁を求めてあげればなんとかなる。
