https://atcoder.jp/contests/abc444/tasks/abc444_e左から見ていってそこをRとすると前回のLから右に動かします。そうしたときに、 を求めます。本当はバランス木を作ればいいのですが、面倒なのでAをソートしてSegment木を作って、その値が範囲にあるのか…

https://atcoder.jp/contests/abc444/tasks/abc444_d和を求める問題はだいたい和の順序を入れ替えればよいです。この問題では、各桁にいくつ1があるかを調べて、繰り上がりを考慮して数字に直して、最後に出力します。 // Many Repunit Sum #![allow(non_sna…

https://atcoder.jp/contests/abc443/tasks/abc443_e上にしか行かないので下からたどり着けるマスかどうか調べます。各列の一番下の壁を持っておきます。 // Climbing Silver #![allow(non_snake_case)] //////////////////// library //////////////////// …

https://atcoder.jp/contests/abc443/tasks/abc443_c逐次実行すると遅いと思っていましたが、意外と速いですね。実質100msかかっていないです。 v <- scan("stdin", numeric()) N <- as.integer(v[1]) T <- as.integer(v[2]) if(N == 0) { A <- c() } else {…

https://atcoder.jp/contests/abc443/tasks/abc443_dまず一番上から考えて、その隣を上げることにします。隣が自分より2以上低ければそこを1低いところまで上げます。その隣は考えてはいけません。例えば、1 2 4 1となっていたら、2はそのままでよくて、4を3…

https://atcoder.jp/contests/abc442/tasks/abc442_c利害関係で直接つながっている研究者の人数を数えればいいです。頻度を数えるにはtableという関数を使うとよいです。ただ、頻度0は出てこないので、1ずつ加えてからあとで1を引きます。 直接つながってい…

https://atcoder.jp/contests/abc442/tasks/abc442_e点を周方向に並べればよいです。+x軸上を一番大きいとして、反時計回りに小さくなっていくとします。集計するときは、+x軸をまたぐときは注意します。 // Laser Takahashi #![allow(non_snake_case)] ////…

https://atcoder.jp/contests/abc442/tasks/abc442_d範囲の和を取るには累積和を計算しておけばよいですが、隣の入れ替えは累積和を一つ変えればいいだけなのでO(1)です。 // Swap and Range Sum #![allow(non_snake_case)] //////////////////// library //…

https://atcoder.jp/contests/abc438/tasks/abc438_gこれも足し算の順番を変えて解きます。順番を変えるというのは、どこを固定するかという話です。ここではBを固定します。入力例1だとまずBの最初の1とそれに対応するAを考えます。Bのindex:i mod Mが0とき…

https://atcoder.jp/contests/abc441/tasks/abc441_c問題が読み取りにくくてずっと誤解していたのですが、よくよく読んだらわかりました。これはどのカップに何mリットル入っているかはわかるので、上から選べばいいんですね。 Rでまとめて処理したら速くな…

https://atcoder.jp/contests/abc441/tasks/abc441_f何番目の商品まで考慮したかとトータルの金額を状態にして、最大の価値を値にしたDPを考えると、計算量はなので、なんとか間に合います。 入力例1だと、最初は0円で価値も0なので、 [0, -∞, -∞, -∞, -∞, -…

https://atcoder.jp/contests/abc441/tasks/abc441_e場合の数を数えるから分割統治法かなと思って考えても、各領域でAとBの数の差ごとに場合の数を考えないといけなくて、領域の結合でさらにAとBの差ごとの場合の数を数えるのにかかってしまって時間が間に合…

https://atcoder.jp/contests/abc441/tasks/abc441_d辺を辿るだけですね。 // Paid Walk #![allow(non_snake_case)] //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T { let mut line = String::new(); std::io::stdin().read_line(&mut l</t:>…

https://atcoder.jp/contests/abc440/tasks/abc440_e多次元で途方もない量のデータを大きいほうから並べるという問題なので、PriorityQueueを使うのだろうとわかります。 Aを降順にソートして、Aに対応するクッキーの数を[K, 0, ...]とするとおいしさの和が…

https://atcoder.jp/contests/abc440/tasks/abc440_dXからX+YがソートしたAの要素が何個またぐかを二分探索します。 // Forbidden List 2 #![allow(non_snake_case)] //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T { let mut line = St</t:>…

https://atcoder.jp/contests/abc439/tasks/abc439_f山と谷の数ということですが、山があれば谷があります。そして、山と谷は交互に来ます。つまり最初と最後が山なら門松的ということになります。最初の点とその次の点と最後の前の点と最後の点を、A, B, C,…

https://atcoder.jp/contests/abc439/tasks/abc439_eある凧を上げると、その両側で別個に考えられるので、その凧のところで最大いくつ凧が上げられるかというDPを使えばいいのではと思いつきます。 凧を(A, B)の辞書順でソートすると、となります。要するに…

https://atcoder.jp/contests/abc439/tasks/abc439_d1個7に当たる値を決めれば5と3も決まるので、結局同じ値があったときが問題になります。jを固定して、jが最大と最小に分けて、最大ならそうなるギリギリのiとkを求めれば、iまでの個数とkまでの個数を掛け…

https://atcoder.jp/contests/abc436/tasks/abc436_c各ブロックの左上を記録しておきます。範囲が広いので配列は使えないので連想配列的なものを使えばよいのでPythonで書くのは簡単ですが、Rではそう簡単にはいきません。 まず、hashというライブラリを使え…