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