2024-01-02 神戸どうぶつ王国へ / PAST #2 G

子どもと神戸どうぶつ王国へ。上の子はテンションが高かった。下の子は電車に乗って帰ると主張し抱っこの時間が長かった。

PAST #2 第二回アルゴリズム実技検定過去問

G - ストリング・クエリ https://atcoder.jp/contests/past202004-open/tasks/past202004_g
- 提出: https://atcoder.jp/contests/past202004-open/submissions/48987977
- 先頭・末尾への追加があるので VecDeque を使う
- 愚直に x 個追加・削除をすると間に合わない
- 代わりに (c, x) で c が x 個を表すものとして追加・削除する

use std::collections::VecDeque;

use proconio::input;

fn main() {
    input! {
        q: usize,
    };
    let mut deque = VecDeque::new();
    for _ in 0..q {
        input! {
            t: usize,
        }
        match t {
            1 => {
                input! {
                    c: char,
                    x: usize,
                }
                deque.push_back((c, x));
            }
            2 => {
                input! {
                    mut d: usize,
                }
                let mut del = vec![0_usize; 26];
                while let Some((c, x)) = deque.pop_front() {
                    if x <= d {
                        del[(c as u8 - b'a') as usize] += x;
                        d -= x;
                    } else {
                        del[(c as u8 - b'a') as usize] += d;
                        deque.push_front((c, x - d));
                        break;
                    }
                }
                println!("{}", del.iter().map(|del_i| del_i.pow(2)).sum::<usize>());
            }
            _ => unreachable!(),
        }
    }
}

今日のコミット。