AtCoder Beginner Contest 160 ふりかえり

AtCoder Beginner Contest 160に参加しました。Cまでは解けて、D問題がわずか1分のタイムオーバーで非常に悔しく楽しい回でした。
atcoder.jp

A,B問題

WAもなくスムーズに解答できた。2問で11分くらい。

C問題

C - Traveling Salesman around Lake

40分くらいかかった。最短移動距離と表記がありDFSなどの探索が必要かと思ってしまったが不要だった。解答アルゴリズムに到達するまでに時間がかかった。わかれば簡単。最小を求めるために最大を見つける問題。ある2点間において最大の部分を見つけて、そこを省く感じ。ただし、円環で一周する部分のケアを忘れずに。
実装においては、windowsイテレータアダプタとfoldコレクションを使いRustっぽく書けた、と思う。

use std::io::*;
use std::str::FromStr;

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();

    token.parse().ok().expect("failed to parse token")
}

fn main() {
    let k: i64 = read();
    let n: usize = read();
    let a: Vec<i64> = (0..n).map(|_| read()).collect();

    let max_d = a[..].windows(2).fold(0, |max_d, d| {
        if max_d < d[1] - d[0] {
            d[1] - d[0]
        } else {
            max_d
        }
    });

    if max_d < k - a[n - 1] + a[0] {
        println!("{}", a[n - 1] - a[0]);
    } else {
        println!("{}", k - max_d);
    }
}

D問題

冒頭にも書きましたが、この問題を22:41にACしました！残念！
と同時にこれまで覚えてきた技をつなげてコンボ決めることができたので楽しかった。時間切れだけど。

問題は各頂点からその他の最短距離を求める問題。ただし、定形のグラフの形があってそこにX,Yのイレギュラーな頂点間の辺が設定される。解き方はいろいろあって、私はちょうど勉強してたBFSが使える！と思って、BFSを使って解いた。Nの最大が2000なので、O(N^2)でも間に合うと根拠をもって検討開始できたところが良かった。解説PDFではグラフの与えられ方から、最短経路は3パターンいずれかの最小値とすれば良いとされていた。これだとO(1)となり速い。けども解説動画ではBFSを使っていたので、まあACするなら全部正義。強いて言うなら早く実装できればより正義。

最短経路の3パターン

頂点Xと頂点Yを結ぶ辺を使わない場合	｜i-j｜
頂点Xと頂点Yを結ぶ辺を使う場合	｜X − i｜ + 1 + ｜j − Y ｜ または ｜Y − i｜ + 1 + ｜j − X｜

この問題で使えた技

• 無向グラフの入力受付*1
• BFS（幅優先探索）による最短経路探索
• nC2の組み合わせ
• ハッシュマップによる古い値に基づく値の更新

コンテスト中に新しく出せたコマンド

• 二次元ベクタの初期化

use std::io::*;
use std::str::FromStr;
use std::collections::VecDeque;
use std::collections::HashMap;

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();

    token.parse().ok().expect("failed to parse token")
}

fn main() {
    type Graph = Vec<Vec<usize>>;
    let n: usize = read();
    let x: usize = read();
    let y: usize = read();
    let mut G: Graph = vec![Vec::new(); n];
    for i in 0..n-1 {
        G[i].push(i+1);
        G[i+1].push(i);
    }
    G[x-1].push(y-1);
    G[y-1].push(x-1);

    let mut dist:Vec<Vec<i32>> = vec![vec![-1; n];n];
    let mut queue: VecDeque<usize> = VecDeque::new();

    //各頂点からその他への頂点への最短距離をBFSで求める
    for i in 0..n {
        dist[i][i] = 0;
        queue.push_back(i);

        while !queue.is_empty() {
            let v = queue.pop_front().unwrap();
            for nv in G[v].iter() {
                if dist[i][*nv] == -1 {
                    dist[i][*nv] = dist[i][v] + 1;
                    queue.push_back(*nv);
                }
            }
        }
    }

    let mut scores = HashMap::new();

    for i in 0..n {
        for j in i+1..n{
            //println!("dist{}",dist[i][j] );
            let count = scores.entry(dist[i][j]).or_insert(0);
            *count += 1;
        }
    }
    //println!("{:?}",G);
    //println!("{:?}",dist);
    for i in 1..n {
        println!("{}", scores.get(&(i as i32)).unwrap_or(&0));
    }


}

おわりに

残念ながらD問題のACとはいかなったが、コンテストに出るたびに少しずつ上達していることを体感している。日々努力の方向が間違っていないことを確認できており安心する。この調子でいきたいと思う。直近はダイクストラ法の修得を目指す。

蛇足

競技プログラミング時の入出力インターフェースがSurface Go(10inch) + 専用キーボード + モバイルディスプレイ(15.6inch)という状態で、マウスカーソルの操作をトラックパッドでやっている。いろいろ遅い！ので、充電式無線マウスを購入。ギリギリ時間切れを経験できたので、良い購入機会だなと。*2

*1:解説動画ではグラフを陽に持たないで実装していた

*2:有線マウスをつなぐとケーブル増えてつらい（有線マウス使う場合、Surface Go なので3本増える）。