https://atcoder.jp/contests/abc437/tasks/abc437_d入力例1で2がらみは、-(2 - 3) + (2 - 1)と考えると、Bで2より大きいものときは負になって、そうでないときは正になります。つまり、自分以下のものの個数を数えればよいです。これは尺取り法を使えば速い…

https://atcoder.jp/contests/abc436/tasks/abc436_aRで解いていきます。 まず入力ですが、scanでホワイトスペース区切りで全部読み取ってvectorにします。第2引数をcharacter()にすると文字列の、integer()にすると整数のvectorになります。 出力はcatを使…

https://atcoder.jp/contests/abc436/tasks/abc436_fこれはよくある和の順序を変えれば答えられる問題です。問題文では範囲を指定してそれからシャッター時間？を変えていますが、まずシャッター時間を固定します。入力例1だと、まず1だけ写るようにします。…

https://atcoder.jp/contests/abc436/tasks/abc436_e例えば、3 2 1 4 5という列があったとすると、3と1を入れ替えればいいですよね。位置1にある3は本来の位置3に戻さなければならないです。このように、今ある数とその位置は関係があって、それを結べばグラ…

https://atcoder.jp/contests/abc435/tasks/abc435_e範囲を覆うので木を利用したいですが、単純にSegment Treeを使うと空間が大きすぎて無理ですし、自力で木を作ると変な入力(1 1、2 2、3 3、…)にも対応しないといけないので平衡木にしなければならずコーデ…

https://atcoder.jp/contests/abc435/tasks/abc435_d黒いノードをいちいち探していたら、そのたびにO(N)かかるので、間に合いません。 そうでなくて、黒くするたびに逆に辿っておけば、合計でO(N)しかかかりません。 // Reachability Query 2 #![allow(non_s…

https://atcoder.jp/contests/abc434/tasks/abc434_e異なるウサギが同じ位置に行けると問題が生じるので、グラフにすればいいとわかります。入力例1なら、ウサギはそれぞれ3と5、-1と5、-1と9なので、3 - 5 - -1 - 9というグラフになります。そして、エッジ…

https://atcoder.jp/contests/abc433/tasks/abc433_f簡単な例から考えましょう。例えば、1111222とします。 1文字だけ取るとすると、4つある1から1つ、3つある2から1つ取るときの場合の数は、2つずつ取るときの場合の数は、3つ取るときはです。乗数のCの右側…

https://atcoder.jp/contests/abc433/tasks/abc433_e小さい値から行列の要素を埋めていけばよいです。行と列の片方にその値があればどちらかを適当に埋めていけばいいのですが、両方にある場合は交わった要素をその値にしなければなりません。 また、それ以…

https://atcoder.jp/contests/abc433/tasks/abc433_d2つ目の引数の桁数は1～10なので、Aiを10倍から1010倍してMで割った余りをカウントしておけばよいです。 // Suddenly, A Tempest #![allow(non_snake_case)] use std::collections::HashMap; ////////////…

https://atcoder.jp/contests/abc432/tasks/abc432_e和の中の式は、なら常に、なら3つの範囲に分けて、なら、なら、ならとなります。 値とそれがいくつあるかを木にすればよいです。 // Clamp #![allow(non_snake_case)] //////////////////// library /////…

https://atcoder.jp/contests/abc432/tasks/abc432_d14回なので最大でも16384個の長方形しかできないので、それらが繋がっているかどうかを調べます。 // Suddenly, A Tempest #![allow(non_snake_case)] use std::collections::HashMap; //////////////////…

https://atcoder.jp/contests/abc422/tasks/abc422_g1は簡単です。箱1のボールの個数がAの倍数の母関数は、 なので、3つの箱全体での母関数は、 分母は精々8項なので、O(N)でxNの項まで計算できます。2は1のようにはいきません。ボールを区別するので指数型…

https://atcoder.jp/contests/abc431/tasks/abc431_f例えば、Dが1でAをソートした列が1 2 3 4だとすると、1と2の有効列は 1 2 2 1の2つが考えられますが、これに3を追加するとすると、どちらでも2の左か最後に追加するしかないので、どちらの場合も2通り追加…

https://atcoder.jp/contests/abc431/tasks/abc431_eBinaryHeapを使って、何回鏡を変えたかの小さいほうから処理して、ゴールにたどり着いたときの操作回数を得ます。 // Reflection on Grid #![allow(non_snake_case)] //////////////////// library //////…

https://atcoder.jp/contests/abc431/tasks/abc431_dBodyのWeightを状態、トータルの嬉しさを値にしてDPすればよいです。最大でもですが、余裕で間に合っています。 // Robot Customize #![allow(non_snake_case)] //////////////////// library ///////////…

https://atcoder.jp/contests/abc430/tasks/abc430_f入力例の最初のケースだと、 1 2 4 3 2 4 5という位置関係なので、1は右端には行けません。2は左に3個はあるので、4番目以降になります。 なので、木を作って指定した範囲に1を足せるようにするとよいです…

https://atcoder.jp/contests/abc430/tasks/abc430_e1個ずらしでタイリングするとよいです。すなわち、 元の文字列 ----------------------------- ----- ----- ----- ... -----みたいに切り出します。ただし、今回は右端まで行ったら、左に戻ってくるように…

https://atcoder.jp/contests/abc430/tasks/abc430_dBTreeSetを使って、前後の要素を拾ってこればよいです。 // Neighbor Distance #![allow(non_snake_case)] //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T { let mut line = String::</t:>…

https://atcoder.jp/contests/abc429/tasks/abc429_f横方向に領域を分割していきます。最後まで分割したら、隣の領域同士を結合して木を作ります。各ノードは左端の各行から右端の各行までの最短距離(+1)を記録しておけばよいので、簡単に結合できます。ルー…

https://atcoder.jp/contests/abc429/tasks/abc429_e各点でSの点までの距離を求めればよいです。ただし、異なる2つのSの点を求めなければなりません。 // Hit and Away #![allow(non_snake_case)] //////////////////// library //////////////////// fn read<T: std::str::FromStr></t:>…

https://atcoder.jp/contests/abc429/tasks/abc429_dC以上になった人の数が何人なのかと、それが何回有効かを別にカウントするとコーディングが楽になります。前者は尺取り法的に計算すると計算量が減ります。 // On AtCoder Conference #![allow(non_snake_…

https://atcoder.jp/contests/abc428/tasks/abc428_e木の直径は、適当な点Aから最も遠い点Bを探して、さらに点Bから最も遠い点Cを探します。BとCの距離が直径です。そして、BとCから直径の半分の距離の点があるのでその点Mが木中点です（距離が奇数ならBとC…

https://atcoder.jp/contests/abc428/tasks/abc428_dyの桁数を決めれば整数の範囲が決まるので、平方根のfloorを求められればその範囲の平方数の個数が求められます。 // 183184 #![allow(non_snake_case)] use std::cmp::{min, max}; //////////////////// …

https://atcoder.jp/contests/abc427/tasks/abc427_f長さ60ですが、半分だと230通りの部分列があるわけではなく、隣は空けないといけないのでフィボナッチ数になって200万程度しかないので全部を部分列でMの剰余がいくつになるかを求められます。前半と後半…

https://atcoder.jp/contests/abc427/tasks/abc427_e幅優先探索をすればよいですが、同じ盤面を繰り返すかもしれないので、同じ盤面には移れないように盤面をHashSetのキーにできるようにします。そのためにHashとCloneを実装します。マス目はゴミがあるかど…

https://atcoder.jp/contests/abc427/tasks/abc427_dKが10以下なので、各ターンで各々のノードが必勝かどうかを調べます。後ろのターンから決めます。 // The Simple Game #![allow(non_snake_case)] //////////////////// library //////////////////// fn …

https://atcoder.jp/contests/abc426/tasks/abc426_d0か1を同じところに固めないといけないですが、そこ以外は同じ文字は2回の操作、違う文字は1回の操作が必要です。なので、0の最も大きな塊と1の最も大きな塊を探します。 // Pop and Insert #![allow(non_…

https://atcoder.jp/contests/abc425/tasks/abc425_e単に を計算するだけですが、Mが素数とは限らないので割り算ができません。 素数ごとに計算すると簡単です。nの階乗が素数pをいくつ持っているかは、 で計算できます。入力例1の最初のテストだと、4は2を…

https://atcoder.jp/contests/abc425/tasks/abc425_d新たに黒く塗ったセルの隣のセルが次に塗れるセルの候補なので、それを集めて塗れるか判定します。 // Ulam-Warburton Automaton #![allow(non_snake_case)] use std::collections::HashSet; ////////////…