ACのメモ2022/10/08に公開AtCoder競プロtech目についたC問題を解いてみるの回です。今回はわりとすんなり解けました。処理時間のワーストケースを考えます。その場合は全く同じ探索を10^5回行うことになります。一度全て走査してから位置情報をいい感じに記録しておき、それを定数時間で問い合わせられるようにできればいかにも計算量を削減できそうな感じですね。適切な前処理をすることで特定区間内の合計値を定数時間で求めることができるものとして累積和があります。今回の問題は文字列の中の特定区間内の"AC"の個数を求める問題なので、その個数を記録した配列についての累積和を作っておけば解けそうです。out.flush()}"AC"の位置情報は"A"の位置に1を記録することとしています。StringのindexOf()を遣って調べます。indexOf()は第二引数で探索を開始する位置を指定できるので、それを使って最後まで探索します。累積和の求め方は一般的な方法です。覚えてはいないのでググって調べました。(参照したページに例題としてまさにこの問題が載っていました...が、見出しが見えただけで内容は全く見ていないのでセーフ)注意が必要なのは、区間がAとCをぶった切った場合です。"AC"のうち"A"だけが区間内だと、1多くカウントしてしまうことになるのでその場合の考慮を入れています。(ansが0だったらマイナスになるかもと考えてその考慮を入れたコードを再提出したりもしましたが、1多くカウントしてしまっている場合の考慮なのでそんなことは起こらないですね...)さらにもう一つ。この問題は入出力が大量になりうるので、入力の受け取りにはBufferedReader、出力にはPrintWriterを使っています。PrintWriterを使ったほうが速いのは、都度フラッシュをせず最後にまとめて行うからです。BufferedReaderを使ったほうが速いのはなぜなのかよくわかりません。以前試したら速かったというだけで、実はブレただけで実際には特に変わらないという可能性もあります...wまあ十分余裕があるので良しとします。hira仕事ではJavaとかKotlinを書いています。AtCoderをやっていて、得られた知見などを書いていけたらと思います。(茶コーダー)Discussionhira仕事ではJavaとかKotlinを書いています。AtCoderをやっていて、得られた知見などを書いていけたらと思います。Proよくある質問LinksX(Twitter)GitHubメディアキットLegal利用規約プライバシーポリシ。