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というグラフになります。そして、エッジ…