日本語によるプログラミングコンテスト
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::io::stdin().read_line(&mut line).ok(); line.trim().parse().ok().u…
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] # 正方向に進む n1 <- F(L, i+1, x1) if(x < 0 && 0 < x1) { n1 <- n1 + 1 } x2 <- x - L[i] n2 <- F(L, i+1,…
https://atcoder.jp/contests/abc453/tasks/abc453_e入力例1だと選手1は単独でチーム、選手2は2人のチームだから、と考えたくなりますが、これだとうまくいきそうにありません。 見る角度を変えて、チームAの人数を決めればよいです。それをAとすると、Aが範囲に入る人数とBが範囲に入る人数とどちらにも入る人数を数えれば、組合せで直ちに求められます。 Aが範囲に入る人数を求めるにはBinary Indexed Treeに全ての範囲を加えればよいです。そして、両方に入るには、AとBを足せば常にNなので、真ん中で折り返して重なる部分を範囲にしてBITに加えればよ…
4回目の挑戦 前回 kubotat.hatenablog.com 近況 結局我慢できなくて書籍を買った gihyo.jp かなり難しい 何度かRustで問題に挑戦した経験があるからぎりぎり理解できているみたいなところがある 完全ミリしらからいきなりこの本は無理だと思う だんだん各種の型とかもわかってきたし、そろそろ問題の内容によってはCまで解ける可能性もワンチャンあるんじゃないかなという淡い期待を抱き始めている 直前に解いてみた過去問では大筋のアルゴリズム部分を自力で考えて解くことができているので 結果 atcoder.jp 結局今回も2完のみで終了 今回はなんとなくC問題も解けそうな気がして…
https://atcoder.jp/contests/abc453/tasks/abc453_d隣は距離1なのでQueueを使えばよいです。ただし、方向依存なので、マスごとにどの方向から来たかで分けて考えます。そして、それぞれにその前がどこから来たかをメモしておいてtrace backするのを簡単にします。 // Go Straight #![allow(non_snake_case)] use std::collections::VecDeque; //////////////////// library //////////////////// fn read<T: std::str::…
0.はじめに 1.問題の概要 2.ビジュアライザを見る 3.マニュアルモードを使う 4.最初の考察 5.最初の提出 6.ビジュアライザを見て考察する 7.ウォーキングしながら考察する 8.考察と実験の繰り返し（評価関数の改善と高速化） 9.全てのテストケースで合致する解を作る（できず） 10.プログラムの見直し 11.1個ずつ配置する 12.1個ずつ配置する2 13.1個ずつ取る3 14.1個ずつ取る4 15.初期盤面を作る 16.自分でプログラムを書く 17.久しぶりのHighest更新 18.得意ケースを調べる 19.さらなる改善 20.3000テストケースの結果 21.ビームサーチの調整…
問題文 https://atcoder.jp/contests/abc453/tasks/abc453_e 問題概要 ヒト $1, 2, \dots, n$ を $2$ のグループ A, B に分ける．このとき， $2$ つのグループはいずれも $1$ 人以上を含む 任意の $i$ についてヒト $i$ は丁度 $1$ つのグループに含まれる ヒト $i$ が属するグループに含まれる人数は $L_i$ 以上 $R_i$ 以下である の全てを満たす必要がある．条件を満たす分け方の総数を（${} \bmod 998{,}244{,}353$ で）求めよ． 制約 $2 \leq n \leq 2 \…
https://atcoder.jp/contests/abc452/tasks/abc452_f転倒数は1個右に追加したり左から除いたりしたときの増減を求めるのは簡単です。右に追加するときはあらかじめ木を作っておいて、自分より大きいものの数を数えればいいです。そうやって尺取り法のように木を更新しながらカウントしていきます。ただし、その周辺でずっとKになるところではややこしいです。 // Interval Inversion Count #![allow(non_snake_case)] //////////////////// library //////////////////// fn …
https://atcoder.jp/contests/abc452/tasks/abc452_ejの剰余を使うので、jを固定すると考えます。例えばj=3とすると、となるので、N/3個のパートができてしまいます。しかし、トータルでは、だから、個のパートです。とという二つの累積和を作っておけばでそれぞれのパートが計算できます。 // You WILL Like Sigma Problem #![allow(non_snake_case)] //////////////////// library //////////////////// fn read<T: std::str::FromStr>…
https://atcoder.jp/contests/abc452/tasks/abc452_d部分文字列がなのだから、あと少し計算量を減らせればよいです。例えば、入力例1のTならakaとadaなら同じことなので、重複がある、すなわちDPが使えるんじゃないかと思われます。Sを左から見ていって、状態を何文字目までTと合っているかとすれば、状態遷移も部分文字列がここで終わるかまだ続けるかの2通りしかないので、計算量はなので十分に間に合います。 // No-Subsequence Substring #![allow(non_snake_case)] //////////////////// li…
qiita.com
note.com
findy-code.io
qiita.com
www.slideshare.net
qiita.com
chokudai.hatenablog.com
qiita.com
qiita.com
