ardririyの足跡

ABC386

2024/12/29
ABC386

A - Full House 2

なんか沼にハマりました。フルハウスになりうる3パターンを愚直に判定。提出

a = list(map(int,input().split()))
a.sort()

if a[0] == a[1] and a[1] != a[2] and a[2] == a[3]:
    print('Yes')
elif a[0] == a[1] == a[2] and a[2] != a[3]:
    print('Yes')
elif a[0] != a[1] and a[1] == a[2] == a[3]:
    print('Yes')
else:
    print('No')

実はA問題だけで4分かけています。すべてはここから始まっていたのかも。

B - Calculator

00のときは貪欲に入力すればOK。提出

s = input()

i = 0
ans = 0

while i < len(s):
    if i != len(s)-1 and s[i] == '0' and s[i+1] == '0':
        i += 1
    ans += 1
    i += 1
print(ans)

C - Operate 1

|S| = |T|, |S| + 1 = |T|, |S| = |T| + 1の3通りに分けて、それぞれについて判定すればよいです。そうでない場合はNo。提出

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

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

    if s.len() == t.len() {
        let mut st = false;
        for i in 0..s.len() {
            if s[i] != t[i] {
                if st {
                    println!("No");
                    return;
                }
                st = true;
            }
        }
    } else if s.len() + 1 == t.len() {
        let mut st = false;
        let mut si = 0;
        let mut ti = 0;
        while si < s.len() {
            if s[si] != t[ti] {
                if st {
                    println!("No");
                    return;
                }
                st = true;
                ti += 1;
            } else {
                si += 1;
                ti += 1;
            }
        }
    } else if s.len() == t.len() + 1 {
        let mut st = false;
        let mut si = 0;
        let mut ti = 0;
        while ti < t.len() {
            if s[si] != t[ti] {
                if st {
                    println!("No");
                    return;
                }
                st = true;
                si += 1;
            } else {
                si += 1;
                ti += 1;
            }
        }
    } else {
        println!("No");
        return;
    }
    println!("Yes");
}

ABC324C - Error Collectionでほぼ既出らしいです(あんまり感じなかったが...)。当時はコンテスト中にACできていなかったことを考えると成長を感じます。

D - Square Permutation

大沼にハマってしまった。まず白いマスについて、白黒の境界線を作りうるものだけをjが小さい順に列挙して、その後に黒いマスすべてについて二分探索を用いて白マスの領域内に含まれていないかを判定すればよいです。提出

#[allow(unused_imports)]
use itertools::Itertools;
use proconio::input;

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

    let mut v = vec![(0, n as i64 + 1)];

    for &(i, j, _) in q.iter().filter(|&x| x.2 == 'W').sorted_unstable_by_key(|x| x.1) {
        if v.last().unwrap().1 > i {
            v.push((j, i));
        }
    }

    for &(i, j, _) in q.iter().filter(|&x| x.2 == 'B') {
        let mut ok = 0;
        let mut ng = v.len();
        while ng - ok > 1 {
            let mid = (ok + ng) / 2;
            if v[mid].0 <= j {
                ok = mid;
            } else {
                ng = mid;
            }
        }
        if v[ok].1 <= i {
            println!("No");
            return;
        }
    } 
    println!("Yes");
}

こういうちょっと実装が見えにくいタイプの問題は苦手で、2かなりの時間をかけてしまい、しかも2ペナをつけてしまいました。典型に帰着する力が弱いとも言えます。

E - Maximize XOR

コンテストには10分間に合わず。

落ち着いて考えると、NN個からKK個選ぶ選び方が10610^6に収まるということは、NNが大きいときはKKはとても大きいかとても小さいかのどちらかになりそうです。 KKが小さいときは選び方を全探索すればよく、KKが大きいときはAAの総xorと選ばないN−KN-K個の総xorをまたxorすることで、KK個の総xorが求まります。このときN−KN-Kは十分小さくなるので、やはり全探索可能です。 提出

#[allow(unused_imports)]
use itertools::Itertools;
use proconio::input;
use cps::ChLibs;

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

    if n / 2 <= k {
        let all_xor = a.iter().fold(0, |acc, x| acc ^ x);
        let mut ans = 0;
        for v in a.iter().combinations(n-k) {
            let sub_xor = v.iter().fold(0, |acc, &x| acc ^ x);
            ans.chmax(all_xor ^ sub_xor);
        }
        println!("{}", ans);
    } else {
        let mut ans = 0;
        for v in a.iter().combinations(k) {
            let sub_xor = v.iter().fold(0, |acc, &x| acc ^ x);
            ans.chmax(sub_xor);
        }
        println!("{}", ans);
    }
}

D問題で引っかかったことで完全に気が動転しており、コンテスト終了直後の気が抜けたタイミングで気づきました。もったいない...

ということで、ABC最終回は負けという結果で終わりました。とはいえ、今のレートは自分の本来の実力からすると上振れていると感じており仕方がない部分もあるかなと思っていて、むしろD問題に時間をかけてしまったことのほうがよっぽど問題だなぁと思っているところです。

← 一覧へ