序盤結構やばかったですが、後半でなんとか持ち直しました... 死ぬかと思った...
時計回りに配列を用意して、与えられた文字から+4して8で割ったあまりをとったインデックス、でよいです。ちょっと面倒くさいですが。 提出
use proconio::input;
fn main() {
input!{
d: String
}
let v = vec!["N", "NE", "E", "SE", "S", "SW", "W", "NW"];
let i = v.iter().position(|&s| s.to_string() == d).unwrap();
println!("{}", v[(i+4)%v.len()]);
}また、
N
と
S
,
E
と
W
を交換するようにswapすることでも解けるようです。こっちのほうが楽そう。
最大でも \(N=M=50\) と小さいので、愚直に4重ループで判定すれば良いです。 \(O(N^2M^2)\) で解くことができます。 提出
use itertools::iproduct;
use proconio::input;
use proconio::marker::Chars;
fn main() {
input!{
n: usize,
m: usize,
s: [Chars; n],
t: [Chars; m],
}
'ol: for (i, j) in iproduct!(0..n, 0..n) {
for (di, dj) in iproduct!(0..m, 0..m) {
let ni = i+di;
let nj = j+dj;
if ni >= n || nj >= n {
continue 'ol;
}
if s[ni][nj] != t[di][dj] {
continue 'ol;
}
}
println!("{} {}", i+1, j+1);
break;
}
}はじめの提出で、境界の条件付を
ni >= n && nj >= n
と書いておりREで1ペナしました。1ペナしてから先にCを解いたので正確ではないものの、これを見つけるのに約10分とかなり時間を掛けました。
鳩なので鳩の巣原理かと思いましたが全然違いました。悲しい(ほんとか？)。
解法自体はよくあるもので、「鳩iがどの巣にいるか」「巣iに何匹の鳩がいるか」「2匹以上の鳩がいる巣の集合」の3つを持ってシミュレーションすれば、各クエリに対して
\(O(\log N)\)
で処理が行えるので、全体で
\(O(N\log N)\)
となり十分高速です。
提出
use std::collections::BTreeSet;
use itertools::Itertools;
use proconio::input;
use proconio::marker::Usize1;
fn main() {
input!{
n: usize,
q: usize,
}
let mut set = BTreeSet::new();
let mut count = vec![1; n];
let mut pos = (0..n).collect_vec();
for _ in 0..q {
input! {
t: u8,
}
if t == 1 {
input! {
p: Usize1,
h: Usize1
}
let before = pos[p];
count[before] -= 1;
if count[before] == 1 {
set.remove(&before);
}
pos[p] = h;
count[h] += 1;
if count[h] == 2 {
set.insert(h);
}
} else {
println!("{}", set.len());
}
}
}HashSetは遅いことが知られているので、避けることが多い。要するにテトリスです。クエリを直接求めるよりは、各ブロックが消える時刻を調べるほうが簡単そうに見えるので、そちらを求めることにします。
まず列で分離して、各列の一番下のブロックの内一番高さが高いもの+1が一番下にあるブロック群が消える時刻になります。ただし、ブロックが存在しない列が1つ以上存在する場合はそれ以上消えないことに注意する必要があります。
提出
use std::cmp::Reverse;
use std::collections::BinaryHeap;
use itertools::Itertools;
use proconio::input;
use proconio::marker::Usize1;
fn main() {
input!{
n: usize,
w: usize,
v: [(Usize1, Usize1); n],
q: usize,
queries: [(usize, Usize1); q],
}
let mut g = vec![BinaryHeap::new(); w];
for (i, &(x, y)) in v.iter().enumerate() {
g[x].push(Reverse((y, i)));
}
let mut kieru_jikan = vec![None; n];
'lp: loop {
let mut mh = 0;
let mut list = vec![];
for i in 0..w {
if let Some(Reverse((y, p))) = g[i].pop() {
list.push(p);
mh = mh.max(y);
} else {
break 'lp;
}
}
let t = mh+1;
for i in list {
kieru_jikan[i] = Some(t);
}
}
let ans = queries.iter().map(|(t, a)| if let Some(tt) = kieru_jikan[*a] {
if tt <= *t {
"No"
} else {
"Yes"
}
} else {
"Yes"
}
).join("\n");
println!("{ans}");
}個人的にはかなり簡単に感じました。
まず、明らかな再帰構造が見えます。そして、操作の過程で現れる値に対して、「その値を変えるのに必要な最小の変更回数」を持っておけば、より上の階層においてその変更回数をうまくマージすることで問題を解けそうです。
これをうまく実装すると、実際にACを得ることができます。
提出
use itertools::Itertools;
use proconio::input;
use proconio::marker::Chars;
struct Node {
color: char,
cost: i32,
}
impl Node {
fn new(color: char, cost: i32) -> Self {
Self { color, cost }
}
fn vote(v: &Vec<Node>) -> (char, i32) {
let col = if v.iter().filter(|c| c.color == '0').count() >= 2 {
'0'
} else {
'1'
};
let other = if col == '0' {
'1'
} else {
'0'
};
let c = col;
let cost = v.iter()
.map(|c| if c.color == other { 0 } else { c.cost })
.sorted_unstable()
.enumerate()
.map(|(i, c)| if i == 2 { 0 } else { c })
.sum::<i32>();
(c, cost)
}
}
fn dfs(i: usize, n: usize, offset: usize, s: &Vec<char>) -> Node {
if i == n {
return Node::new(s[offset], 1);
}
let k = s.len() / 3usize.pow(i as u32+1);
let mut v = vec![];
for j in 0..3 {
v.push(dfs(i+1, n, offset + k*j, s));
}
let (c, cost) = Node::vote(&v);
Node::new(c, cost)
}
fn main() {
input!{
n: usize,
s: Chars,
}
let res = dfs(0, n, 0, &s);
println!("{}", res.cost);
}まず、
\(A, B, C\)
を降順ソートします。一番大きい値は明らかに
\(A_0, B_0, C_0\)
を使うものです。次に大きいものを考えると、
\((A_1, B_0, C_0)\)
,
\((A_0, B_1, C_0)\)
,
\((A_0, B_0, C_1)\)
のいずれかです。
計算する値を
\(f(i, j, k)\)
とかくと、
\(f(i, j, k)\)
の次に大きくなる可能性があるのは
\(f(i+1, j, k)\)
,
\(f(i, j+1, k)\)
,
\(f(i, j, k+1)\)
のいずれかになるので、候補をうまくheapで管理しながら
\(K\)
回popすることでこの問題を解くことができます。重複して数えることに注意。
提出
use std::collections::{BTreeSet, BinaryHeap};
use itertools::Itertools;
use proconio::input;
fn main() {
input!{
n: usize,
k: usize,
mut v: [[i64; n]; 3]
}
fn func(a: i64, b:i64, c:i64) -> i64 {
a*b + b*c + c*a
}
for i in 0..3 {
v[i].sort();
}
let mut seen = BTreeSet::new();
let mut heap = BinaryHeap::new();
let mut s = func(v[0][n-1],v[1][n-1], v[2][n-1]);
let mut count = k;
seen.insert(vec![n-1, n-1, n-1]);
heap.push((s, vec![n-1, n-1, n-1]));
while let Some((sum, vec)) = heap.pop() {
count -= 1;
if count == 0 {
println!("{}", sum);
return;
}
let mut new_v = vec;
for i in 0..3 {
if new_v[i] != 0 {
new_v[i] -= 1;
if seen.insert(new_v.clone()) {
heap.push((func(v[0][new_v[0]], v[1][new_v[1]], v[2][new_v[2]]), new_v.clone()));
}
new_v[i] += 1;
}
}
}
}