ARC109_C(Large RPS Tournament) - プログラムのお勉強メモ

はじめに

AtCoder Regular Contest 109 に参加
大会中にはACできなかったが C 問題 について無事 AC したためメモする

問題概要

2 ^ k 人がじゃんけんのトーナメント大会に参加
n 文字のじゃんけんの手パターンが与えられる
i 番目のユーザは i % n 文字目のじゃんけんの手を出す
- 例えば (グー, チョキ, パー) の順番で法則が与えられると 1人目はグー, 2人目はチョキ, 3人めはパー, 4人目はグー...という感じ
最終的に勝利するユーザの手を出力する

方針

k 回戦実施すると最終決着になるためk回試合を実施
ただ最大で k = 100 であるため 2 ^ 100 人用意して全試合はできない
じゃんけんの手の周期が決まっているので周期毎に勝ち残る人は固定になる
n 文字分だけ k 試合やれば良さそう ★間違ってます

最初の実装(ACできなかったコード)

n が奇数のときと偶数のときで処理を変えないといけない、と思ってしまった
MOD を取ってやれば index が溢れても処理ができる、と思ってしまった

実装(Rust)

fn main() {
    let (n, k) = input!(isize, isize);
    let s = input!(String);
    let mut hands = s;
 
    for _ in (0..k).rev() {
        let mut check_len = match hands.len() % 2 {
            0 => hands.len() / 2 as usize,
            1 => hands.len() / 2 + 1 as usize,
            _ => 0, // ありえないパターン
        };
 
        let pow_check = 2usize.checked_pow(k as u32);
 
        check_len = match pow_check {
            Some(x) => match x < check_len {
                true => x,
                false => check_len,
            },
            _ => check_len,
        };
 
        hands = (0..check_len)
            .map(|x| {
                let first = hands.chars().nth((x * 2) % hands.len());
                let second = hands.chars().nth((x * 2 + 1) % hands.len());
                let result = battle(first.unwrap(), second.unwrap());
                result
            })
            //.inspect(|x| println!("--{}--", x))
            .collect();
 
        //println!("{}", hands);
    }
 
    println!("{}", hands.chars().nth(0).unwrap());
}

(※じゃんけんを実施する関数と入力の関数は省略)

誤りの修正

n が奇数の場合, nの末尾の文字と, nの最初の文字で試合が行われる. その後, n の2文字目と3文字目... という感じで 試合を実行するユーザがずれていく
もともとの実装だと奇数の場合には n+1 (結果的に末尾と1文字目) までしか試合をしていなかったがそれでは不十分
奇数 + 奇数 = 偶数, ということで 2*n まで実施すると法則性のある周期になる
偶数の場合は n までで良いが, 2*n までやっても結果は同じ
k 回試合を実施したらベクタの先頭に優勝者の手が入っている, という感じ

実装(Rust)

fn main() {
    let (n, k) = input!(isize, isize);
    let s = input!(String);
    let mut hands = format!("{}{}", s, s);

    for _ in (0..k).rev() {
        // println!("hands: {}", hands);
        let check_len = hands.len() / 2 as usize;

        let result: String = (0..check_len)
            .map(|x| {
                let first = hands.chars().nth(x * 2);
                let second = hands.chars().nth(x * 2 + 1);
                let result = battle(first.unwrap(), second.unwrap());
                result
            })
            //.inspect(|x| print!("{}", x))
            .collect();

        hands = format!("{}{}", result, result);
    }

    println!("{}", hands.chars().nth(0).unwrap());
}

(※じゃんけんを実施する関数と入力の関数は省略)

覚えておくこと

MOD を取って法則が得られるような場合, 2倍すると全ルールが網羅できることが多い