AtCoder

前書き なるべく愚直な操作でなんとかする解法です。（実質的には同じかもしれませんが、）mod での累積和を使っていません。 コンテスト中、解法が思いつかずになんとかして無理やり解く方法を考えたもので、綺麗な解法ではないです。 公式解説を読むほうが勉強になると思います。 問題 atcoder.jp 考え方 であれば、左から順に可能な限り0にしていき、0にできない残り個が0になっているかを確かめればよい であるときは、一旦左から順に0にしていったあと、左から 元の数列の値に戻していく ことを考えていく すると、から個については、0ではない値になる 「左から0にする」操作のあと、「左から元の数列に戻…

Toyota Programming Contest 2023 Spring Qual A（AtCoder Beginner Contest 288）に参加しました。 結果 A,B,Cの3問正解でした。 D問題がやけに難しかった。一旦おいておいてE問題を解いたほうが良かったかも。 E問題はさっと問題文を読んだ所感だとDPで溶けそうな問題だと思った。 A - Many A+B Problems 問題文の通り処理する。 標準入力でちゃんと数値を2つ受け取れれば困らない程度の難易度のいつも通りのA問題。 B - Qualification Contest これも問題文の通り処理する。 N個の文字列を…

ABC288D とりあえず，クエリは無視して考える.まず \(a_{[i,i+k)}\) の区間全体に \(-x\) を足す．次に \(a_{[i+1,i+1+k)}\) の区間全体に \(x\) を足す．すると，真ん中は変化せず， \(a_{i}\)と \(a_{i+k}\)だけ変化する．とくに， \(x = a_{i}\) として計算すれば， \(a_{i}\) を \(0\) にして， \(a_{i+k}\) に追加した形になる．よって， index が\(+k\)毎に， \(a\) の値をまとめることができる． \(c in k\) に対してまとまった値達が全て等しいことが， 良い数列…

ABC288C DFSをして，すでに到達している頂点に到達したら， その辺はサイクルを作っているので除く辺となる． 同じ辺につき2回カウントするので2で割る． この様な辺は，(向きも考慮するとき)後退辺と呼ぶらしい？ DFSにおける頂点，辺 dfs(cu, pa){ // >>> // *** [頂点]に関する処理 (入ってきたとき) // <<< for(ne : to[cu]) if(ne != pa){ // 必要ならifをつける // >>> // *** [辺]に関する処理 (出るとき) // <<< dfs(ne, cu); // >>> // *** [辺]に関する処理 (出ると…

https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_aaマージソートを実装するだけです。 URLはExcel方式ですね。 // Sorting #![allow(non_snake_case)] fn read<T: std::str::FromStr>() -> T { let mut line = String::new(); std::io::stdin().read_line(&mut line).ok(); line.trim().parse().ok().unwrap() } fn read…

https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_zN種類だったとして最初に1種類目が出るまで1回、次の種類が出る確率は(N-1)/Nなので、次の種類が出るまでの回数の期待値はN/(N-1)、その次の種類が出る確率は(N-2)/Nなので、次の種類が出るまでの回数の期待値はN/(N-2)、などとなり、全種類が出るまでの回数の期待値は、となります。 // Coin Gacha #![allow(non_snake_case)] fn read<T: std::str::FromStr>() -> T { …

https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_v2つを足してある値になるは、ソートしてしゃくとり法ですね。 // Choose Cards 3 #![allow(non_snake_case)] fn read<T: std::str::FromStr>() -> T { let mut line = String::new(); std::io::stdin().read_line(&mut line).ok(); line.trim().parse().ok().unwrap() } fn r…

tokuminiさんのToyota Programming Contest 2023 Spring Qual A（AtCoder Beginner Contest 288）での成績：302位 パフォーマンス：2172相当 レーティング：1807→1849 (+42) :) https://atcoder.jp/users/tokumini/history/share/abc288?lang=ja A~Eまでの5完。ペナルティを出さなかったのが良かった（というか単純にサンプルが充実気味だったのかもしれない）。前回の反省を活かし、D問題で詰まった際に一旦飛ばしてE問題を先にACし、気持ちに余裕を作…

問題 提出解答 問題の概要 制約 解法 (1) 良い数列の特徴づけ 解法 (2) 判定 問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 整数列 が以下の操作を好きな回数だけ行うことで全ての項を にすることができるとき, は良い数列であるという. 及び整数 を選び, の全てに を足す. 長さ の整数列 がある. 次の 個の問に答えよ. の第 項から第 項までの部分列は良い数列か? 制約 解法 (1) 良い数列の特徴づけ 整数列 に対して, 以下は同値である. は良い数列である. に対して, とする. このとき, である. (上) ならば (下)について, 各操作は可逆であ…

atcoder.jp 順列Pの逆置換であるような順列Qを求めるだけ……ですが、分かりにくかったので。 目的としては、Pの各要素に対して、Xは何番目にあるか？を Q[X] とすることで O(1) で返せるようにすることです。 P = {2, 3, 1} Q = {3（Pにおいて1は3番目）, 1（Pにおいて2は1番目）, 2（Pにおいて3は2番目）} という感じですね。 public static void solve () { int n = nextInt(); int[] p = nextIntArray(n); int[] q = new int[n]; for (int i=0; i<…

問題 提出解答 問題の概要 制約 解法 問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 頂点 辺の単純無向グラフ が与えられる. ただし, このとき, のサイクルを持たないような全域部分グラフ における の最小値を求めよ. 制約 解法 の最小値を考えるということは の最大値を考えることに対応する. よって, サイクルを持たない全域部分グラフにおける辺の本数の最大値を求めることにする. 実は, 辺の本数の最大値は の連結成分の数を として, である. これを示すためには次の事実を使う. 頂点の木における辺の本数は である. まず, の連結成分の数が であるから, 各連結成…

atcoder.jp 愚直に解くことも可能ですが、制約上明らかに間に合いません。 例を挙げて考えてみます。問題文の例だと分かりにくいので、分かりやすいやつを作ってみます。 A = {3, 6, 9, 12, 15} Q1 = 20 Q2 = 3 このとき、A[0]~A[n-1]のいずれとも異なる数（解説にもあるように、良い数とする）を全て列挙してみます。 1, 2, {3}, 4, 5, {6}, 7, 8, {9}, 10, 11, {12}, 13, 14, {15}, 16, 17...... Q1の K=20 は、明らかに A[n-1] の 15 よりも右側にあり、答えは 25 です。…

問題 提出解答 問題の概要 制約 解法 問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 個の整数のタプル に対して, を求めよ. 制約 解法 の順に 個の整数のタプル を読み込み, を出力することを 文で 回繰り返せば良い.

競プロについての活動記録を毎月とってみようと思います。 これをやる理由は 競プロのモチベーションアップにする 記録しておいたらもしかしたら後で何かの役に立つかもしれない 何か記事を書く癖をつけたい という感じです。 もしかしたら今回しかやらないかもしれません。この記事を書きながら数回前のコンテストについてけっこう覚えてないなと思ったので、当時思っていた感想とは異なるものもあるかもしれません。 AtCoder のレート変化 1658 → 1607 (-51) レートが上がることの多い ARC にだけ Rated 参加したが、すべてレートが下がってしまった。 もう水色に落ちたくないなと思っていたけ…

atcoder.jp 数列Aにおいて、X=1...N がどの位置に出てくるかを事前に全て記録しておくことで、 クエリを高速に処理できるようにします。 具体的には、List in List で管理します。 list.get(0) = {数列Aにおいて 0 が出現する場所（添え字）} list.get(1) = {数列Aにおいて 1 が出現する場所（添え字）} list.get(2) = {数列Aにおいて 2 が出現する場所（添え字）} ... list.get(N) = {数列Aにおいて N が出現する場所（添え字）} 仮に、L=4, R=6, X=2 のクエリが来たとして、その時の list.…

atcoder.jp 一冊ずつ読む本をシミュレーションする必要はなく、 最終的に机Aから i 冊、机Bから j 冊読むことになるので、その組み合わせを探索すればOK。 しかし、上記の組み合わせを全て試す場合、計算量が N * M となり間に合わないので、二分探索を使う。 具体的には、 ・机Aから i 冊読むときの時間を ta 分とする。 ・すると、机Bからは、残りの K - ta 分ぶんだけ本を読むことができる。 →K - ta 分を超えないようにできるだけ机Bから本を読むとき、何冊読めるかを二分探索する。 とすれば、計算量は最悪の場合でも 200000 * となり、間に合うっぽい。 stat…