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を左から見ていって、状…