https://atcoder.jp/contests/abc462/tasks/abc462_e、として、斜め45度にまず進んで残りは、まっすぐ進むとのときはそのままでいいですが、で進むときはコの字に進んででどちらかをどちらが小さいかで決めます。 // Alternating Costs #![allow(non_snake_c…

https://atcoder.jp/contests/abc462/tasks/abc462_dPriorityQueueに開始時刻の順に入れて、終了時刻-Dを過ぎたら取り出します。その時刻にPriorityQueueにいる人の数でその時刻開始の組合せ数が決まります。 // Accomplice #![allow(non_snake_case)] /////…

https://atcoder.jp/contests/abc461/tasks/abc461_e入力例1で考えると、1行目を黒く塗って+3、3行目を黒く塗って+3、2列目を白く塗るのですが、黒が2つあるので-2、最後に1行目を黒く塗るのですが、1回目のクエリで1行目を塗ってあるので、その間に列を1回…

https://atcoder.jp/contests/abc461/tasks/abc461_d何行目から何行目かを固定して、何列目から何列目まででKになるパターンを数えます。全部0以上なので、尺取り法的に数えられて、計算量はでなんとか間に合います。 ただし、K=0のときうまくいかないので、…

https://atcoder.jp/contests/abc460/tasks/abc460_eの桁数をとすると、なので、だから、はの倍数です。 i128を使うと簡単ですね。 // x + y ≡ x + y #![allow(non_snake_case)] //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T { let mu</t:>…

https://atcoder.jp/contests/abc460/tasks/abc460_d1回目以降に黒になったマスは白と黒が交互に現れるので、最初に黒になるターンをメモしておきます。 // Repeatedly Repainting #![allow(non_snake_case)] //////////////////// library ////////////////…

https://atcoder.jp/contests/abc459/tasks/abc459_d各文字がいくつ使われているか調べて、一番多い文字を等間隔に置いて、その間に多い順に置いていけばよいです。 こういう問題はOptionを使うとよいですね。 // Chalkboard Median #![allow(non_snake_case…

https://atcoder.jp/contests/abc456/tasks/abc456_g久しぶりに解説を見てみたら、母関数を使う方法が書いてありました。 Sをxで分割して、それぞれの領域の長さをとして、日のうち連続する休日が日までの場合の数をとすると、求める場合の数は、となります…

https://atcoder.jp/contests/abc458/tasks/abc458_d半分に分けて、奇数個だから左側が一つ多くなるように保ちます。 // Chalkboard Median #![allow(non_snake_case)] use std::collections::BinaryHeap; //////////////////// library ///////////////////…

https://atcoder.jp/contests/abc457/tasks/abc457_d値の下限を決めて、そこに達するまで何回操作するかを調べます。そして、二分探索でその下限を決めます。ただし、細かいところがややこしいですね。 // Raise Minimum #![allow(non_snake_case)] ////////…

https://atcoder.jp/contests/abc454/tasks/abc454_c有向グラフを1から辿るだけですが、Rでグラフをふつうに作る全然時間が足りません。そこでノードの隣のノードの配列をリストにします。こうすると時間内に収まります。 v <- scan("stdin", integer()) N <…

https://atcoder.jp/contests/abc456/tasks/abc456_cDP的に、前の文字と隣に同じ文字無しに何文字続いているかを記憶していきます。 最後はやっぱり出力のところですね。 D <- 998244353 v <- scan("stdin", character()) S <- v[1] char_to_int <- function…

https://atcoder.jp/contests/abc456/tasks/abc456_f1日飛ばしでもいいという問題です。これが毎日コストをかけるということなら、ウィンドウ幅を一定にしてスライドしていけばいいのですが、1日飛ばしだとうまくいきません。コストを払うときと払わないとき…

https://atcoder.jp/contests/abc456/tasks/abc456_e都市と曜日の組み合わせをノードにして有向グラフにして、ループがあるかを判定します。 // Endless Holidays #![allow(non_snake_case)] //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -</t:>…

https://atcoder.jp/contests/abc456/tasks/abc456_d最後の文字が何かを状態とするDPです。空文字もあるので4通りです。 // Not Adjacent 2 #![allow(non_snake_case)] //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T { let mut line = </t:>…

https://atcoder.jp/contests/abc455/tasks/abc455_c各要素の頻度を調べて、要素と頻度を掛け合わせて、それをソートして、後ろからK除いた配列の和を取ればよいです。 頻度を調べるのはtableという関数で、要素はnamesで取ることができます。 最後、指数表…

https://atcoder.jp/contests/abc455/tasks/abc455_fコストは になります。スライムが合体するときにたとえばが出会うときにの項が発生するからです。 範囲に一律に足すから遅延評価セグメント木を使いたくなりますが、 なので、2乗和が必要なのでふつうのよ…

https://atcoder.jp/contests/abc455/tasks/abc455_e一つでも同じ数の部分文字列の数を数えます。文字列を半分にして、片側だけに収まるそのような部分文字列を再帰的に数えて、別に両方にまたがる部分文字列を数えます。真ん中から左側に伸びる部分文字列を…

https://atcoder.jp/contests/abc455/tasks/abc455_dPがどこにあるのかとC以上の移動が高速にできなければいけませんが、リスト構造を使えばよいです。 // LRUD Moving #![allow(non_snake_case)] //////////////////// library //////////////////// fn read<T: std::str::FromStr></t:>…

https://atcoder.jp/contests/abc454/tasks/abc454_eまず、問題より簡単な全てのマスを通る経路を考えます。そうすると、はどうやっても無理で、なら経路が簡単にわかります。これはどうしてでしょうか。マスを一つ移動するとの偶奇が変わります。偶数から始…

https://atcoder.jp/contests/abc454/tasks/abc454_dリスト構造を作って、パターンにマッチすれば削除します。 // (xx) #![allow(non_snake_case)] //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T { let mut line = String::new(); std:</t:>…

https://atcoder.jp/contests/abc453/tasks/abc453_c1回ずつ再帰的に進めばの計算量ですが、時間がギリギリです。 v <- scan("stdin", integer()) N <- v[1] L <- v[2:(N+1)] F <- function(L, i, x) { if(i == N + 1) { return(0) } x1 <- x + L[i] # 正方…

https://atcoder.jp/contests/abc453/tasks/abc453_e入力例1だと選手1は単独でチーム、選手2は2人のチームだから、と考えたくなりますが、これだとうまくいきそうにありません。 見る角度を変えて、チームAの人数を決めればよいです。それをAとすると、Aが範…

https://atcoder.jp/contests/abc453/tasks/abc453_d隣は距離1なのでQueueを使えばよいです。ただし、方向依存なので、マスごとにどの方向から来たかで分けて考えます。そして、それぞれにその前がどこから来たかをメモしておいてtrace backするのを簡単にし…

https://atcoder.jp/contests/abc452/tasks/abc452_f転倒数は1個右に追加したり左から除いたりしたときの増減を求めるのは簡単です。右に追加するときはあらかじめ木を作っておいて、自分より大きいものの数を数えればいいです。そうやって尺取り法のように…

https://atcoder.jp/contests/abc452/tasks/abc452_ejの剰余を使うので、jを固定すると考えます。例えばj=3とすると、となるので、N/3個のパートができてしまいます。しかし、トータルでは、だから、個のパートです。とという二つの累積和を作っておけばでそ…

https://atcoder.jp/contests/abc452/tasks/abc452_d部分文字列がなのだから、あと少し計算量を減らせればよいです。例えば、入力例1のTならakaとadaなら同じことなので、重複がある、すなわちDPが使えるんじゃないかと思われます。Sを左から見ていって、状…

https://atcoder.jp/contests/abc451/tasks/abc451_e入力例1を見ると、重みが2と3があるので、これが辺だとわかります。ただ、こういう考え方だとうまく手順が作れない気がします。 そこで最小の2の辺を一つ取ると、頂点1と頂点2が辺です。次にこの頂点1と頂…

https://atcoder.jp/contests/abc451/tasks/abc451_d小さい順に出せばいいので、PriorityQueueを使います。そのとき、ある数の次の数が重要になりますが、2つあって、その数の右に1を追加するかのと、1を追加したあとに2に置き換えるなどがあります。128のよ…

https://atcoder.jp/contests/abc450/tasks/abc450_e文字列の列は、ある程度大きくなったら前の方は変わらないので、Rを超える長さまで長さだけ作っておきます。それをとすると、それはとの結合なので、範囲はそのどちらかか結合部をまたぐかで再帰的に添え…