日本語によるプログラミングコンテスト
https://atcoder.jp/contests/abc456/tasks/abc456_f1日飛ばしでもいいという問題です。これが毎日コストをかけるということなら、ウィンドウ幅を一定にしてスライドしていけばいいのですが、1日飛ばしだとうまくいきません。コストを払うときと払わないときでoとxで表すと、最初がoかxで分けてそれぞれでそこまでの和の最小を求めます。長さがKを超えてくると前を移動しなければなりませんが、そのときも最初がoかxの両方を求める必要があります。しかし、情報は最初がoかxかとそこまでの最小の和で次がoかxかの情報はないので、これは無理です。 最初が固定されていればこの問…
https://atcoder.jp/contests/abc456/tasks/abc456_e都市と曜日の組み合わせをノードにして有向グラフにして、ループがあるかを判定します。 // Endless Holidays #![allow(non_snake_case)] //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T { let mut line = String::new(); std::io::stdin().read_line(&mut line).ok(); …
https://atcoder.jp/contests/abc456/tasks/abc456_d最後の文字が何かを状態とするDPです。空文字もあるので4通りです。 // Not Adjacent 2 #![allow(non_snake_case)] //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T { let mut line = String::new(); std::io::stdin().read_line(&mut line).ok(); line.trim(…
https://atcoder.jp/contests/abc455/tasks/abc455_c各要素の頻度を調べて、要素と頻度を掛け合わせて、それをソートして、後ろからK除いた配列の和を取ればよいです。 頻度を調べるのはtableという関数で、要素はnamesで取ることができます。 最後、指数表示で出力されないようにします。sprintfを使うと簡単でしょう。 v <- scan("stdin", integer()) N <- v[1] K <- v[2] A <- v[3:(N+2)] tab <- table(A) values_num <- as.double(names(tab)…
0.はじめに はじめまして、もしくはお久しぶりです。競技プログラミング歴6年目に突入した、かえでです。 これは、2026年4月26日日曜日午後3時から午後7時までの4時間の短期コンテスト「JR西日本・ALGO ARTIS プログラミングコンテスト（AtCoder Heuristic Contest 064）」の参加メモになります。 コンテスト中に書いているものなので、読んでいる方にとっては、言葉足らずな部分が多くあるかと思います。コンテストが終わってしまうと忘れてしまうことも多いので、できるだけ自分の思考や足取りを記録できれば良いと思っています。 詳しくは後から追記するとして、コンテストに参加…
https://atcoder.jp/contests/abc455/tasks/abc455_fコストは になります。スライムが合体するときにたとえばが出会うときにの項が発生するからです。 範囲に一律に足すから遅延評価セグメント木を使いたくなりますが、 なので、2乗和が必要なのでふつうのようにはいきません。しかし、を足したとき、 となるので、和と2乗和を各ノードに持っておけばよいです。 一般的なLazySegTreeはAIに書いてもらいました。 // Merge Slimes 2 #![allow(non_snake_case)] //////////////////// library /…
※ネタバレ注意 atcoder.jp atcoder.jp キーワード：Rectangle Add Max Get メモ：NicheLibrary を使って書き直し（\(f(l,r)\) の最大値が 0 である場合に改めて注意） ライブラリ： notleonian.github.io atcoder.jp atcoder.jp キーワード：Rectangle Add Max Get メモ：NicheLibrary を使って書き直し ライブラリ： notleonian.github.io atcoder.jp atcoder.jp キーワード：LCA、木DP、メモ化再帰 メモ：数え上げたいのは経…
はじめに公式解説の解法は場合分けが多く、ユーザ解説が存在していなかったので今更ながら記す。なお、他の人の AC 提出を軽く見ただけでも、この記事で紹介する解法と同じと思われる提出は見つかる。解法としての新規性はないことは前置きしておく。問題一部の要素が固定された \( ( 1,2,\ldots,N ) \) の順列について、転倒数の 2 乗の総和（を 998244353 で割った余り）を求める問題である。atcoder.jpなお、固定されていない要素の個数を \(K\) とすると、求めたいのはそのような順列を一様ランダムに発生させたときの転倒数の 2 乗の期待値に \(K!\) を掛けたものに…
https://atcoder.jp/contests/abc455/tasks/abc455_e一つでも同じ数の部分文字列の数を数えます。文字列を半分にして、片側だけに収まるそのような部分文字列を再帰的に数えて、別に両方にまたがる部分文字列を数えます。真ん中から左側に伸びる部分文字列をBの数からAの数を引いたものの数を数えます。真ん中から右側に伸びる部分文字列も同様に数えて、値を足したら0になるものを探します。AとBとCの数でも同様に数えて、包除原理を使います。 // Unbalanced ABC Substrings #![allow(non_snake_case)] use std::c…
https://atcoder.jp/contests/abc455/tasks/abc455_dPがどこにあるのかとC以上の移動が高速にできなければいけませんが、リスト構造を使えばよいです。 // LRUD Moving #![allow(non_snake_case)] //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T { let mut line = String::new(); std::io::stdin().read_line(&mut line).ok();…
qiita.com
note.com
findy-code.io
qiita.com
www.slideshare.net
qiita.com
chokudai.hatenablog.com
qiita.com
qiita.com
