🕌

ABC278 A~DをRustで解く

2022/11/20に公開

A

問題

長さNの数列 A=(A_1,A_2,…,A_N)が与えられます。
あなたは次の操作をちょうどK回行います。

  • A の先頭の要素を取り除き、A の末尾に 0 を挿入する。
    操作を行った後の A の要素をすべて出力してください。

制約

  • 1≤N≤100
  • 1≤K≤100
  • 1≤A_i≤100
  • 入力される値はすべて整数

解法

両端キューを使えば解けそうです。

use std::collections::VecDeque;

use proconio::{fastout, input};
#[fastout]
pub fn main() {
    input! {
    n:usize,
    k:usize,
    a:[usize;n]
        }

    let mut b = VecDeque::from(a);

    for _ in 0..k {
        b.pop_front();
        b.push_back(0);
    }

    for i in b {
        print!("{} ", i);
    }
}

B

問題

高橋君は置き時計を買いました。
この時計は、現在の時刻が 24 時制で ABCD 分であるときに図 1 のように時刻を表します。
例えば図 2 では、時計は 758 分を示しています。
時刻の表示方法をより形式的に説明すると次のようになります。
現在の時刻が 24 時制で hm 分であるとします。ここで 24 時制とは、時間を 0 以上 23 以下の整数で、分を 04 以上 $59 以下の整数で表す時刻の表現方法を言います。
h の 10 の位を A, 1 の位を B, m の 10 の位を C, 1 の位を D とします。(ただし h,m が 1 桁である場合は先行ゼロを追加して考えます。)
このとき時計は左上に Aを、左下に B を、右上に C を、右下に D を表示します。
高橋君は、次の条件を満たす時刻を 見間違えやすい時刻 と呼ぶことにしました。

  • 時計の表示の右上と左下を入れ替えても、それに対応する 24 時制の時刻が存在する。
    例えば 図 3 は 20 時 13 分を示していますが、時計の表示の右上と左下を入れ替えると 21 時 3 分を意味する表示になります。よって 20 時 13 分は見間違えやすい時刻です。
    今、時計は H 時 M 分を示しています。
    (現時点も含めて)以降はじめて訪れる見間違えやすい時刻を 24 時制で答えてください。

制約

  • 0≤H≤23
  • 0≤M≤59
  • H,M は整数

解法

分と時間の組み合わせは高々 24 * 60 = 1440通りなので、愚直に問題文に書いてあるとおりに判定します。
実際に時間の 2 桁めと分の 1 桁目を swap し、24 時制として成り立つかチェックします。

use proconio::{fastout, input};
#[fastout]
pub fn main() {
    input! {
    mut h:usize,
    mut m:usize
        }

    loop {
        let mut hs = format!("{:0>2}", h.to_string());
        let mut ms = format!("{:0>2}", m.to_string());

        let sh = format!(
            "{}{}",
            hs.chars().next().unwrap(),
            ms.chars().next().unwrap()
        );
        let sm = format!(
            "{}{}",
            hs.to_string().chars().nth(1).unwrap(),
            ms.to_string().chars().nth(1).unwrap()
        );

        if sh.parse::<usize>().unwrap() < 24 && sm.parse::<usize>().unwrap() < 60 {
            println!("{} {}", h, m);
            return;
        }
        m += 1;
        if m == 60 {
            m = 0;
            h += 1;
        }
        if h == 24 {
            h = 0;
        }
    }
}

C

問題

高橋君が運営する SNS「Twidai」にはユーザー 1 からユーザー N4 までの $N 人のユーザーがいます。
Twidai では、ユーザーは別のユーザーをフォローすることや、フォローを解除することができます。
Twidai がサービスを開始してから、Q 回の操作が行われました。 i 回目 (1≤i≤Q) の操作は 3 つの整数 T_i,A_i,B_i表され、それぞれ次のような操作を表します。

  • T_i=1 のとき:ユーザー A_iがユーザー B_iをフォローしたことを表す。
    この操作の時点でユーザー A_iがユーザー B_iをフォローしている場合、ユーザーのフォロー状況に変化はない。
  • T_i=2 のとき:ユーザー A_iがユーザー B_iのフォローを解除したことを表す。
    s この操作の時点でユーザー A_iがユーザー B_iをフォローしていない場合、ユーザーのフォロー状況に変化はない。
  • T_i=3 のとき:ユーザー A_i とユーザー B_i が互いにフォローしているかをチェックすることを表す。
    この操作の時点でユーザー A_i がユーザー B_i をフォローしており、かつユーザー B_i がユーザー A_i をフォローしているとき、このチェックに対して Yes と答え、そうでないときこのチェックに対して No と答える必要がある。
    サービス開始時には、どのユーザーも他のユーザーをフォローしていません。

すべての T_i=3 であるような操作に対して、i が小さいほうから順番に正しい答えを出力してください。

制約

  • 2≤N≤10^9
  • 1≤Q≤2×10^5
  • T_i=1,2,3 (1≤i≤Q)
  • 1≤A_i≤N (1≤i≤Q)
  • 1≤B_i≤N (1≤i≤Q)
  • A_i \neq B_i(1≤i≤Q)
  • T_i=3 となる i (1≤i≤Q) が存在する
  • 入力される値はすべて整数

解法

Twitter の動静を受けての問題ですかね...笑
実際の Twitter 社のデータベースの構造はどうなってるんでしょう。
少し前に読んだデータ指向アプリケーションデザインに、Twitter の初期の DB 設計における意思決定が少しだけ載ってたと思います。
この本キャリアの早いうちに読んどいて良かったと思える一冊なので、まだよんでない方はぜひ。


ユーザー数 N、ユーザー間の辺 Q が大きいので、連想配列を使って管理します。
また、rust の HashMap は存在しないキーに対してremoveを読んでも false を返すのみで未定義動作とはならないので、
気にせずよびます。

use proconio::{fastout, input};
use std::collections::HashMap;
#[fastout]
pub fn main() {
    input! {
    _n:usize,
    q:usize,
        }
    let mut trees = HashMap::new();
    for i in 0..q {
        input! {t:usize}

        match t {
            1 => {
                input! {a:usize,b:usize}
                trees.entry(a).or_insert_with(HashMap::new).insert(b, i);
            }
            2 => {
                input! {a:usize,b:usize}
                if let Some(x) = trees.get_mut(&a) {
                    x.remove(&b);
                }
            }
            _ => {
                input! {a:usize,b:usize}
                let mut ans = "No";
                if let Some(x) = trees.get(&a) {
                    if x.get(&b).is_some() {
                        if let Some(z) = trees.get(&b) {
                            if z.get(&a).is_some() {
                                ans = "Yes";
                            }
                        }
                    }
                }
                println!("{}", ans);
            }
        }
    }
}

D

問題

長さ Nの数列 A=(A_1,A_2,…,A_N) が与えられます。
Q 個のクエリが与えられるので、順番にすべて処理してください。
q 番目 (1≤q≤Q) のクエリは以下の 3 つのいずれかの形式で、それぞれ次のようなクエリを表します。

  • 1 x_qA のすべての要素に x_qを代入する。
  • 2 i_q x_qA_{iq}x_qを加える。
  • 3 i_qA_{iq} の値を出力する。

制約

  • 1≤N≤2×10^5
  • 1≤Q≤2×10^5
  • 0≤A_i≤10^9(1≤i≤N)
  • q 番目 (1≤q≤Q) のクエリが 2 番目もしくは 3 番目の形式のとき、1≤i_q≤N
  • q 番目 (1≤q≤Q) のクエリが 1 番目もしくは 2 番目の形式のとき、0≤x_q≤10^9
  • 3 番目の形式のクエリが存在する- 入力される値はすべて整数

解法

クエリ2は O(1)で済む処理なので大丈夫そうですが、クエリ1は毎回 O(N)かかるのでこのままだと TLE しそうです。

今までどのような操作を繰り返しても、1のタイプのクエリが来たら数列の全ての要素がx_qになります。
なので1のクエリが来た場合はその値を保持しておきます。
2のクエリは別途連想配列で記憶しておき、クエリ1が来た場合は保持している値を削除します。

  • クエリ 1 が既に実行されていたらその値x_qを見る。実行されてないなら元の配列を見る。
  • クエリ 2 を管理している連想配列に問い合わせに行って、そこにレコードがあればそれも別途足す
  • 出力する

でうまくいきそうです。

use std::collections::HashMap;

use proconio::{fastout, input, marker::Usize1};
#[fastout]
pub fn main() {
    input! {
    n:usize,
    a:[usize;n],
    q:usize
        }
    let mut q1 = -1;
    let mut q2 = HashMap::new();
    for _ in 0..q {
        input! {
        i:usize
        }
        match i {
            1 => {
                input! {s:i64}
                q1 = s;
                q2.clear();
            }
            2 => {
                input! {
                k:Usize1,
                x:usize
                }
                let v = q2.entry(k).or_insert(0);
                *v += x;
            }
            _ => {
                input! {r:Usize1}
                let mut l = a[r];
                if q1 != -1 {
                    l = q1 as usize;
                }
                if let Some(x) = q2.get(&r) {
                    l += x;
                }
                println!("{}", l);
            }
        }
    }
}

総括

E 問題は解けそうで TLE が 2 個取れず撤退...
最終的な結果はぎりぎり緑パフォでした。

最近レートの伸びが鈍化してきている && 精進グラフがレートのはるか下なのでもう少し精進の量あげようかな...
10~11 月は 90 問解いているようなので、100 問くらい解けるよう頑張ります。

最後まで読んでいただいてありがとうございました。

Discussion