https://atcoder.jp/contests/abc438/tasks/abc438_f数える順番を変える、じゃないですが、数え方を変えます。すなわち、問題文はパスを列挙してそのパスに含まれない最小値を足しますが、最小値を固定してそうなるパスを数えます。例えば入力例2で最小値0な…

https://atcoder.jp/contests/abc438/tasks/abc438_eバケツを渡した先を辿るとグラフになります。まずグラフを連結成分に分割します。各ノードの行先は一つなので、必ずループに陥ります。そうしたらあとは何回ループを回るかなどを考えればよいです。 まず…

https://atcoder.jp/contests/abc438/tasks/abc438_dAとBだけで考えると、途中まででよりBよりAが上回っていればよいので、AからBを引いて足してより大きくなっていればいいことに気が付きます。入力例1では、それぞれの項を引き算すると、 -1 1 -2 2 1累積…

https://atcoder.jp/contests/abc436/tasks/abc436_b斜めの列を埋めつくしたら次の斜めの列に移行するから必ず全部埋まるという話ですね。 行列を作って、順にその要素に値を入れていくだけですね。 N <- scan("stdin", integer()) table <- matrix(0, nrow=…

https://atcoder.jp/contests/abc437/tasks/abc437_eVec<Vec<Vec<usize>>>で木を実現します。 入力例1なら、最初にxが0を探します。そうすると、2番目と4番目のyが1で、1番目のyが2なので、yは順番だけ考えて、tree[0] = [[2, 4], [1]]となります。次に2か4がxのものを探し</vec<vec<usize>…

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の剰余がいくつになるかを求められます。前半と後半…