問題はこちら https://atcoder.jp/contests/abc175
https://github.com/tanakh/competitive-rs これを使っています。
A - Rainy Season
与えられた文字列中のRが連続してる部分の長さの最大値を求めよっていう問題。
定跡的には、R以外の文字を空白文字に置換してやると、その文字列を空白区切りの単語に分解してやれば（こういう関数はたいていの言語には標準ライブラリにあらかじめ用意されているってのを利用する）、あとはその長さのmaxを取ってやればいい。
use competitive::prelude::*;
# [argio(output = AtCoder)]
fn main(s: Chars) -> usize {
let s = s
.into_iter()
.map(|c| if c == 'R' { c } else { ' ' })
.collect::<String>();
s.split_whitespace().map(|w| w.len()).max().unwrap_or(0)
}
･･･んだけど、Aにしては凝った問題を出してくるな、と思って解いてた。終わった後で、問題文に「長さが3固定」っていう条件が入っているのに気付いた。3固定なら、与えられた文字列が"RRR"なら3、"RR"を含むなら2、"R"を含むなら1、それ以外なら0とか、そういう愚直な方法でも通りますね。
use competitive::prelude::*;
# [argio(output = AtCoder)]
fn main(s: String) -> usize {
if s.contains("RRR") {
3
} else if s.contains("RR") {
2
} else if s.contains("R") {
1
} else {
0
}
}
B - Making Triangle
整数がN(<=100)個与えられるので、それから3つを選んで、それらが相異なる値でかつ三角形の3辺の長さになり得るものの数を求めるという問題。
Nが小さいので、3個の組み合わせを全通りチェックすることができる。算数が苦手なので、三角形の条件を脳みその奥底から引っ張り出してくるのにちょっと時間がかかってしまった。3辺の長さをa,b,cとしたときに最長辺がcならばa+b>c、だと思うんだけど、ソートするのがめんどくさかったから a+b>c && b+c>a && c+a>b にした。解説みたら、与えられた数をあらかじめソートしておけば、三つ目の数が自動的に最大になるから楽、ってみてなるほどなあって思った。
use competitive::prelude::*;
# [argio(output = AtCoder)]
fn main(n: usize, l: [i64; n]) -> usize {
let mut ret = 0;
for i in 0..n {
for j in i + 1..n {
for k in j + 1..n {
let a = l[i];
let b = l[j];
let c = l[k];
if a == b || b == c || c == a {
continue;
}
if a + b > c && b + c > a && c + a > b {
ret += 1;
}
}
}
}
ret
}
C - Walking Takahashi
最初数直線上の座標Xから初めて、そこからちょうどK(<=10^15)回、±Dに移動するとき、最終的に絶対値が一番小さいところに行きたい的な問題。
とりあえずXは絶対値をとって正の数にしても同じ問題になるんで、常に正の値から始めることにする。
そこから原点方向に直進しても、0まで届かないとき(X>=K*D)は、明らかにそれが答え。
そうじゃない場合は、原点を跨ぐように往復を繰り返すのが明らかに最適なんでそうしたいんだけど、Kが無茶苦茶大きいので、ナイーブにループはできない。まあ2回往復すると同じとこに戻るだけなので、残り回数を mod 2 してやればいい。
use competitive::prelude::*;
# [argio(output = AtCoder)]
fn main(x: i64, k: i64, d: i64) -> i64 {
let x = x.abs();
let t = x / d;
if t >= k {
x - k * d
} else {
(x - t * d - d * ((k - t) % 2)).abs()
}
}
D - Moving Piece
N(<=5000)個のマスがあって、各マスにはスコアと次にどこに行くのかが書いてある。好きなマスから初めて、K(<=10^9)回次に書いてあるマスへの移動を繰り返すとき、通ったマスのスコアの合計値の最大はいくつか。
開始する位置をN通り試せば答えは求まるけど、Kがでかいのでナイーブにやると間に合わない。間に合わせるにはどうやればいいのかなって考えると、マス目の数は少ないから、Kが大きいときは同じマスを何回も何回も通るはずだってことがわかる。同じマスを通った後は、同じ経路をぐるぐる回るはずだ。その経路の長さは、直前に同じマスを通ったときに、それが何ターン目だったのかを記録しておけば、2回目のターン数からそれを引けば求まる。経路の長さがわかれば、残りターン数をそれで割った回数、そこをループするはず。ループの中のスコアの合計は、これも直前に通ったときのスコアを記録しておけば、同様に二回目に通ったときのスコアからそれを引けば求まる。ループを回る回数だけそれを足してやる必要がある。
ループのスコアの合計が負であれば、回れば回るほど損になるから、もう移動を打ち切ってしまってもいい。正ならば、回れば回るほど得になるので、限界ぎりぎりまで回るのが特になる。最後のループのどこでスコア最大になるかはよくわからないので、ループをスキップする際に、残り回数がループ長をちょっと超えるぐらいにしておけば、ラスト1週はチェックできるので、それで答えが求まる。
ループ長は明らかにN以下になるので、これに必要な計算量はO(N)なんで、初期マス全部にたいしてこれをやってもO(N^2)なので、間に合いそう。
use competitive::prelude::*;
# [argio(output = AtCoder)]
fn main(n: usize, k: usize, p: [Usize1; n], c: [i64; n]) -> i64 {
let mut ans = i64::min_value();
for start in 0..n {
let mut prev = vec![None; n];
let mut i = 0;
let mut cur = start;
let mut acc = 0;
while i < k {
i += 1;
acc += c[cur];
cur = p[cur];
ans = max(ans, acc);
if let Some((prev_acc, prev_i)) = &prev[cur] {
if *prev_acc >= acc {
break;
}
let loop_inc = acc - prev_acc;
let loop_len = i - prev_i;
let loop_cnt = max(0, k as i64 - n as i64 - i as i64) / loop_len as i64;
i += loop_len * loop_cnt as usize;
acc += loop_inc * loop_cnt;
ans = max(ans, acc);
while i < k {
i += 1;
acc += c[cur];
cur = p[cur];
ans = max(ans, acc);
}
} else {
prev[cur] = Some((acc, i));
}
}
}
ans
}
アイデアとしては、ループを検出して愚直な移動をスキップしてトータルで処理するマスの数をK回からNに比例する回数に減らすという単純なものだけど、実装は結構めんどい。実装がめんどい問題は、実装の工夫で実装時間を大幅に減らせたり泥沼にはまったり、純粋にコーディング技術が試されるので、個人的には好きです。上のコードはたぶん全然ダメなので、皆さんでもっとかっちょいいコードを書いてください。
E - Picking Goods
R(<=3000)×C(<=3000)のマスにK個アイテムが散らばってる。(1,1)から(R,C)まで、アイテムを回収しながら移動する。移動できるのは(+1,0)か(0,+1)の2方向のみ。同じ行から拾えるアイテムは3個まで。この時、拾えるアイテムのスコアの合計の最大値を求めよという問題。
アイテムのあるマスとないマスがあるけど、アイテムがないマスには価値0のアイテムがおいてあると考えれば、全部のマスにアイテムが入ってると考えていいのでちょっと実装が楽になる。
同じマスを2回通ることが絶対にないので、ある位置からゴールまで行くときに、拾えるスコアの最大値を考えるとシンプルなDPになる。同じ行は3個までという条件を考慮するために、同じ行でこれまで何個拾ったかをパラメーターに加えればいい。なので、結局R×C×4のDPになる。
･･･んだけど、結構時間制限が厳しい。テーブルのサイズが3000×3000×4×64bit＝256MB必要になる。CPUのL3キャッシュに入りきらないようなでかいテーブルを、割とランダムにアクセスし続けることになるので、想像より結構時間がかかってしまう。
また、競プロではあんまりやる人はいないと思うけど、多次元配列じゃなくて、vec<vec<vec<i64>>>的なダイナミックなメモリの確保の仕方をすると遅いだけじゃなくて最悪メモリ上限（1024MB）を超えてしまう。なので、そういう風にやる場合は、配列の次元をつぶして、フラットな配列にしてやるなどの工夫が必要になる。
use competitive::prelude::*;
# [argio(output = AtCoder)]
fn main(h: usize, w: usize, k: usize, rcv: [(Usize1, Usize1, i64); k]) -> i64 {
let mut bd = vec![vec![0; w]; h];
for (y, x, v) in rcv {
bd[y][x] = v;
}
solve(0, 0, 0, &bd)
}
# [memoise(x, y * 4 + cnt)]
fn solve(x: usize, y: usize, cnt: usize, bd: &Vec<Vec<i64>>) -> i64 {
let h = bd.len();
let w = bd[0].len();
if x >= w || y >= h {
return 0;
}
let mut ans = solve(x + 1, y, cnt, bd);
ans = max(ans, solve(x, y + 1, 0, bd));
if cnt < 3 {
ans = max(ans, solve(x + 1, y, cnt + 1, bd) + bd[y][x]);
ans = max(ans, solve(x, y + 1, 0, bd) + bd[y][x]);
}
ans
}
memoiseマクロ を使っていて、普通にやるなら
# [meoise(x, y, cnt)]
になるところなんだけど、上に書いたような理由でMLEになったりする。なんで、ここを
# [meoise(x, y * 4 + cnt)]
に変えれば、yとcntの次元がマージされて2次元配列でDPできるようにしている。もっとつきつめれば、
# [meoise((x * 3001 + y) * 4 + cnt)]
とかやればフラットな1次元配列上でDPできる。自分で書いててアレですけど、ここを変えるだけでキャッシュするメモリの構造を変えられるのはすごい便利だと思うんで、みんな使ってみてください。
F - Making Palindrome
文字列がN(<=50)個与えらる。各文字列にはそれぞれコストがついてる。この文字列から重複を許して1個以上選んで、それを連結して回文を作りたいんだけど、回文が作れるような選び方のうち一番小さいコストの合計を求めよっていう問題。
ぱっと見どう考えたらいいかよくわかんないけど、回文ってのはだいたい真ん中から考えれば何とかなるものだ。出来上がった回文の真ん中がどうなってるのかを考えたら、文字列の境界か、どれかの文字列のどれかの文字か、どれかの文字列の文字の境目か、のどれかのはず。
これのどれかから初めて、左右が釣り合ってたらそれで終わりでいいし、釣り合ってなかったら少なくとも短い方にどれかの文字列をくっつけて伸ばしてやらなければならない。
で、まあここまで考察すれば、左右どちらに、どういう文字列が釣り合ってないのかを状態にすれば、釣り合ってない部分の文字列は、入力のどれかの文字列の部分文字列のはずなので、状態数の最大はN×C(20,2)×2=50×190×2＝19000とかになる。次の状態への遷移は明らかにN通り以下なので、ダイクストラ法で十分間に合う。
use competitive::prelude::*;
use std::cmp::Reverse;
use std::collections::BinaryHeap;
# [argio(output = AtCoder)]
fn main(n: usize, sc: [(Chars, i64); n]) -> Option<i64> {
let mut q = BinaryHeap::<(Reverse<i64>, Result<&[char], &[char]>)>::new();
for (s, c) in sc.iter() {
q.push((Reverse(*c), Err(s)));
q.push((Reverse(*c), Ok(s)));
for i in 0..s.len() {
if let Some(t) = check(&s[0..i], &s[i..]) {
q.push((Reverse(*c), t));
}
if let Some(t) = check(&s[0..i], &s[i + 1..]) {
q.push((Reverse(*c), t));
}
}
}
let mut ss = BTreeMap::new();
while let Some((c, s)) = q.pop() {
if s == Err(&[]) {
return Some(c.0);
}
ss.insert(s.clone(), c);
for (t, d) in sc.iter() {
match s {
Err(l) => {
if let Some(s) = check(l, t) {
if !ss.contains_key(&s) {
q.push((Reverse(c.0 + d), s));
}
}
}
Ok(r) => {
if let Some(s) = check(t, r) {
if !ss.contains_key(&s) {
q.push((Reverse(c.0 + d), s));
}
}
}
}
}
}
None
}
fn check<'a>(l: &'a [char], r: &'a [char]) -> Option<Result<&'a [char], &'a [char]>> {
if l.len() < r.len() {
for i in 0..l.len() {
if l[l.len() - 1 - i] != r[i] {
return None;
}
}
Some(Ok(&r[l.len()..]))
} else {
for i in 0..r.len() {
if l[l.len() - 1 - i] != r[i] {
return None;
}
}
Some(Err(&l[0..l.len() - r.len()]))
}
}
これも結構実装が重くていい感じの問題だ。上のコードではcheckという、二つの文字列を引数にとって、これらが回文の左右を構成できるかどうか（lのsuffixとrのprefixが完全に一致してるかどうか）、一致してる場合は、釣り合っていない残りの部分を返す関数を作った。この関数だけで状態の遷移が計算できるので、結構すっきり実装できたと思う。
あとどうでもいい話だけど、Rustの左右を表すのに直和型を使ったのだけど、Resultという型の名前が大変違和感があるなあと思った。あとよく考えたら左右で型が同じなんだから、Result<&[char], &[char]>じゃなくて(bool, &[char]) で良かったですね･･･。