tokuminiさんのウルシステムズプログラミングコンテスト2023(AtCoder Beginner Contest 286)での成績:263位 パフォーマンス:2090相当 レーティング:1919→1938 (+19) :) #AtCoder #ウルシステムズプログラミングコンテスト2023(ABC286) https://atcoder.jp/users/tokumini/history/share/abc286?lang=ja
AからF問題までの6完。
Predictorで見たときはレート-19とかだったのでみんなすごいなぁと思っていたが、バグだったらしくレートは上がっていた。
A問題
区間が被るとすごいことになりそうでめっちゃ難しそうと思っていたが、制約をよく見ると被らないとのことなので一安心。とはいえA問題の中では実装量多めになってしまった。
B問題
これも、naを見つけて確定させてからnyaに置き換えないといけないとか疑いだしてしまったが、別にそんなことはなかった。(変換先の末尾に変換元の接頭辞がある場合、たとえばaa→nyaの変換だと aaaという文字列をまずnyaaに変換し、変換した後nynyaに変換するということが起きてしまうということを気にした。)
C問題
一瞬難しそうでびびったが、先に回転量を全探索して合わないところを数えれば良いのか。
より高速な解法の解説、すごい発想だ。あと実装がC++の中でもなんか個性的な書き方に見える。余裕があれば写経してみたい。
D問題
DP配列を使い回すタイプでやろうとするとどうも微妙に頭が混乱するが、それで書き始めてしまったのでそれで押し切った。解説のO(NX)解法もすごいなぁ。
E問題
ワーシャルフロイドやるだけで良いんだよね? と疑心暗鬼になりながら実装した。久しぶりすぎて無駄に時間がかかった。
F問題
中国剰余定理っぽいな〜というのは早めに気づいたが、単純に2,3,5,...,23だと積が1e9超えなくて困る。いろいろ調整を考えた結果、2→4、3→9としてできるとわかった。
中国剰余定理については、ちょっと前のyukicoderのコンテストで出てきていたので思い浮かびやすかった。AtCoderのコンテストで同じテーマが連続して出ることは少ないだろうから、一発当てにいくには他サイトのコンテストにも出ていた方が良いんだろうな。
配列がそこそこの長さなので手動で試してみることもできず、ちょっとインタラクティブ部分で変なミスやってないか不安だったけどなんとか一発で通ったので良かった。
ACLにもあるということを知らなかったので後で使ってみる。
G問題
橋を検出して、橋となる辺が一度しか通れない辺だったらカウントし、それが3つ以上あるとダメとかそういうことをこねくり回して考えていた。オイラー路は頭になかったなぁ。