ABC278 A~DをRustで解く
A
問題
長さ
あなたは次の操作をちょうど
- 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
問題
高橋君は置き時計を買いました。
この時計は、現在の時刻が
例えば図 2 では、時計は
時刻の表示方法をより形式的に説明すると次のようになります。
現在の時刻が
h の 10 の位を
このとき時計は左上に
高橋君は、次の条件を満たす時刻を 見間違えやすい時刻 と呼ぶことにしました。
- 時計の表示の右上と左下を入れ替えても、それに対応する 24 時制の時刻が存在する。
例えば 図 3 は 20 時 13 分を示していますが、時計の表示の右上と左下を入れ替えると 21 時 3 分を意味する表示になります。よって 20 時 13 分は見間違えやすい時刻です。
今、時計は H 時 M 分を示しています。
(現時点も含めて)以降はじめて訪れる見間違えやすい時刻を 24 時制で答えてください。
制約
0≤H≤23 0≤M≤59 -
,H は整数M
解法
分と時間の組み合わせは高々
実際に時間の 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」にはユーザー
Twidai では、ユーザーは別のユーザーをフォローすることや、フォローを解除することができます。
Twidai がサービスを開始してから、Q 回の操作が行われました。
-
のとき:ユーザー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
と答える必要がある。
サービス開始時には、どのユーザーも他のユーザーをフォローしていません。
すべての
制約
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
問題
長さ
Q 個のクエリが与えられるので、順番にすべて処理してください。
-
1 :x_q のすべての要素にA を代入する。x_q -
2 i_q :x_q にA_{iq} を加える。x_q -
3 :i_q の値を出力する。A_{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 番目の形式のクエリが存在する- 入力される値はすべて整数
解法
クエリ
今までどのような操作を繰り返しても、
なので
- クエリ 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