AtCoder Beginner Contest 337 振り返り

A - Scoreboard

特に困ることはなく、合計を出す。

use proconio::input;

fn main() {
    input! {
        n: usize,
        xy: [(usize, usize); n],
    }

    let x: usize = xy.iter().map(|(x, _)| x).sum();
    let y: usize = xy.iter().map(|(_, y)| y).sum();

    if x > y {
        println!("Takahashi");
    } else if y > x {
        println!("Aoki");
    } else {
        println!("Draw");
    }
}

B - Extended ABC

テストケースが意外と少なくて、テストケース全部通しても本当にあってるのかって少し確認に時間使った。
B=>A, C=>A, C=>Bが禁則となるためそれを除外する。

use proconio::{input, marker::Chars};

fn main() {
    input! {
        s: Chars,
    }

    let mut cur = s[0];
    for c in s {
        if c != cur {
            if cur == 'A' && (c == 'B' || c == 'C') {
                // OK
            } else if cur == 'B' && c == 'C' {
                // OK
            } else {
                // NO
                println!("No");
                return;
            }
        }

        cur = c;
    }

    println!("Yes");
}

C - Lining Up 2

aのindexとvalueを逆転させた配列を先に作っておく。
ソート関数工夫すれば何とかなるかなーとおもったけど、それを考えるだけ時間の無駄だった。

use proconio::input;

fn main() {
    input! {
        n: usize,
        a: [i64; n],
    }

    let top = (0..n).find(|&i| a[i] == -1).unwrap();
    let mut r = vec![-1; n + 1];
    for i in 0..n {
        if a[i] != -1 {
            r[a[i] as usize - 1] = i as i64;
        }
    }

    let mut cur = top as i64;
    loop {
        if cur == -1 {
            break;
        }
        print!("{} ", cur + 1);
        cur = r[cur as usize];
    }
    println!("");
}

D - Cheating Gomoku Narabe

xとxの間で1つずつずらしながら.の数を数える。
.の数をscoreとしてカウントして.の数が最も少ないものを答えにする。
1つずらしたときに先頭と末尾がoと.で異なっていればscoreに変化があるのでそれで更新する。

問題をxとxの区間に絞って計算する方針は立てたが、Kの最大長から作業用のコピー作るとだめっぽそうだったのでじゃあどうすればって考えるのに時間かかった。

use itertools::iproduct;
use proconio::{input, marker::Chars};

fn main() {
    input! {
        h: usize,
        w: usize,
        k: usize,
        mut s: [Chars; h],
    }

    let mut ans = i64::MAX;

    for y in 0..h {
        let mut l = 0;
        let mut score = 0;
        for x in 0..w {
            if s[y][x] == 'x' {
                score = 0;
                l = x + 1;
                continue;
            }

            let len = x - l + 1;
            if len <= k {
                if s[y][x] == '.' {
                    score += 1;
                }
                if len == k {
                    ans = ans.min(score);
                }
            } else {
                if s[y][l] == '.' && s[y][x] == 'o' {
                    score -= 1;
                }
                if s[y][l] == 'o' && s[y][x] == '.' {
                    score += 1;
                }
                ans = ans.min(score);
                l += 1;
            }
        }
    }

    for x in 0..w {
        l = 0;
        score = 0;
        for y in 0..h {
            if s[y][x] == 'x' {
                score = 0;
                l = y + 1;
                continue;
            }

            let len = y - l + 1;
            if len <= k {
                if s[y][x] == '.' {
                    score += 1;
                }
                if len == k {
                    ans = ans.min(score);
                }
            } else {
                if s[l][x] == '.' && s[y][x] == 'o' {
                    score -= 1;
                }
                if s[l][x] == 'o' && s[y][x] == '.' {
                    score += 1;
                }
                ans = ans.min(score);
                l += 1;
            }
        }
    }

    if ans != i64::MAX {
        println!("{}", ans);
    } else {
        println!("-1");
    }
}

総括

ABCD解けた。WAとTLEなし。
E問題に着手したタイミングで残り5分だった。
この問題、有名な問題だったので知ってたがさすがに残り5分でさっと解ける感じではなかった。
全体的に3分ぐらい早く解ければなんとかなったかなぁ。

最近体調崩してて参加できなかったり、スコア落としてた。立て直したい。