AtCoder Beginner Contest 355
結果
A - Who Ate the Cake? : AC(4:05)
B - Piano 2 : AC(12:33)
C - Bingo 2 : AC(28:57)(1ペナ)
D - Intersecting Intervals : AC(53:24)
E - Guess the Sum : 提出無し
A - Who Ate the Cake?
高橋君のケーキが誰かに食べられていた
容疑者が$${3}$$人いて、りんごさんとすぬけくんが犯人でない人をそれぞれ一人挙げる
犯人が特定できたなら犯人を、特定できなければ-1を出力する問題
自分の回答
int main() {
int A, B;
cin >> A >> B;
vector<bool> H(4, true);
if(A == B){
printf("-1\n");
}
else{
H[A] = false;
H[B] = false;
for(int i = 1; i < 4; i++){
if(H[i]){
printf("%d\n", i);
}
}
}
}そのままだけどもっといい感じにできないものか
公式解説
省略
B - Piano 2
長さ$${N}$$の数列$${A=(A_{1},A_{2},…,A_{N})}$$と長さ$${M}$$の数列$${B=(B_{1},B_{2},…,B_{N})}$$がある
要素が昇順になるように$${2}$$つの数列を結合した時$${A}$$からの要素が$${2}$$つ連続することがあるか判定する問題
自分の回答
int main() {
int N, M;
cin >> N >> M;
vector<int> A(N), B(M);
for(int i = 0; i < N; i++){
cin >> A[i];
}
for(int i = 0; i < M; i++){
cin >> B[i];
}
sort(A.begin(), A.end());
sort(B.begin(), B.end());
int i = 0, j = 0;
vector<bool> ma;
while(i < N || j < M){
if(i < N && j < M){
if(A[i] < B[j]){
ma.push_back(true);
i++;
}
else{
ma.push_back(false);
j++;
}
}
else if(i < N){
ma.push_back(true);
i++;
}
else{
ma.push_back(false);
j++;
}
}
for(int i = 1; i < N + M; i++){
if(ma[i] && ma[i - 1] == ma[i]){
printf("Yes\n");
return 0;
}
}
printf("No\n");
}そのまま
公式解説
省略
C - Bingo 2
$${N×N}$$マスのビンゴがあり、番号は左から右、上から下へ$${1,2,…,N^2}$$である
$${T}$$回番号が言われるため、初めてビンゴになったら何回目の番号でなったか、$${T}$$回でビンゴにならなかったら-1を出力する問題
自分の回答
int main() {
int N, T;
cin >> N >> T;
vector<int> A(T);
for(int i = 0; i < T; i++){
cin >> A[i];
A[i]--;
}
vector<int> row(N, 0), line(N, 0), dia(2, 0);
for(int t = 0; t < T; t++){
int i = A[t] / N;
int j = A[t] % N;
row[i]++;
line[j]++;
if(i == j){
dia[0]++;
}
if(i == N - j - 1){
dia[1]++;
}
if(row[i] == N || line[j] == N || dia[0] == N || dia[1] == N){
printf("%d\n", t + 1);
return 0;
}
}
printf("-1\n");
}番号を-1した上でNで割った値がi行目、Nで割った余りがj列目にその番号があることを示すため、各行列で何回番号を言われたかを記録してNになったら出力
斜め部分の判定を間違えてWA
公式解説
省略
D - Intersecting Intervals
$${N}$$個の実数の区間$${[l_{i},r_{i}]}$$が与えられる
区間が共通部分を持つペアが何通りあるか求める問題
自分の回答
int main() {
int N;
cin >> N;
vector<pair<int, int>> sec;
for(int i = 0; i < N; i++){
int l, r;
cin >> l >> r;
sec.push_back({l, r});
}
sort(sec.begin(), sec.end());
int64_t ans = 0, now = -1;
priority_queue<int, vector<int>, greater<int>> nr;
for(int i = 0; i < N; i++){
auto [l, r] = sec[i];
now++;
nr.push(r);
while(l > nr.top()){
now--;
nr.pop();
}
ans += now;
}
printf("%ld\n", ans);
}
lの小さい順に見て行って自分と自分より前の区間が何個重なっているかの総和が答え
根本は区間スケジューリング問題みたいな感じよね
公式解説
省略
E - Guess the Sum
システムが数列$${A=(A_{0},A_{1},…,A_{2^N-1})}$$を持っている
システムに対して非負整数$${i,j}$$を選び$${l=2^ij,r=2^i(j+1)-1}$$として$${A_{l}+A_{l+1}+…+A_{r}}$$を$${100}$$で割った余りを聞くことができる
整数$${L,R(L \leqq R)}$$が与えられるため、質問を最小回数にして$${A_{L}+A_{L+1}+…+A_{R}}$$を$${100}$$で割った余りを求める問題
自分の回答
ijで九九表みたいなものを作ったら連続した形で聞きたい時どう聞けばいいかがグラフみたいになったからそのあたりを上手くできないかと思ったけどコードにまとめられなかった
公式解説
from collections import deque
N, L, R = map(int, input().split())
n = 1 << N
edge = [[] for i in range(n + 1)]
for i in range(N + 1):
for l in range(0, n, 1 << i):
r = l + (1 << i)
edge[l].append(r)
edge[r].append(l)
parent = [None] * (n + 1)
parent[R + 1] = -1
dq = deque([R + 1])
while dq:
v = dq.popleft()
for u in edge[v]:
if parent[u] == None:
parent[u] = v
dq.append(u)
ans = 0
now = L
while parent[now] != -1:
p = parent[now]
sgn = 1
l, r = now, p
if l > r:
sgn = -1
l, r = r, l
i = (r - l).bit_length() - 1
j = l >> i
print("?", i, j, flush=True)
T = int(input())
ans += sgn * T
now = p
print("!", ans % 100)
https://atcoder.jp/contests/abc355/editorial/10079より
そうか聞ける範囲はセグメント木の形か
それで範囲の始点と終点を繋いだグラフができるからそれを求める範囲で最短探索してその通りに聞けばいいのか
なるほど