ミスで夢が覚めた男の備忘録です
コンテスト概要
AtCoder Beginner Contest 420
開催日:2025年8月24日 21:00-22:40
A - What month is it?
考察
$X$月の$Y$か月後が何月か？
何も考えないなら$(X+Y)$月と答えればいい。
ただ$(X+Y)$が12以上の時WAになる。なので12で割った余りを出す。
この時$(X+Y)=12$の時0月と表示されるのでそこだけ例外処理をしておく。
「まあ、A問題か」っていう印象。
提出
#include <bits/stdc++.h>
using namespace std;
int main(){
int x,y;
cin >> x >> y;
x = (x+y)%12;//Yか月後を求める
if(x == 0) x = 12;//12の時だけ例外処理。
cout << x << endl;
}
B - Most Minority
考察
まず、どっちに投票したらポイントがもらえるかを知りたい。
データを受け取るついでに少数派がどっちなのかを調べておく。
投票結果をもとに各人のポイントを清算していく。
全員分記憶して後から抜き出すのでもいい。
が、今回はsetを使い、トップの得票が上回ったときに前トップのことは忘れる方針で実装。
まぁ、どっちが楽かは大差なさそうですが。
提出
#include <bits/stdc++.h>
using namespace std;
int main(){
int n,m;
cin >> n >> m;
vector<vector<int>>num (n,vector<int>(m));//各人の投票履歴
vector<vector<int>>bt (m,vector<int>(2,0));//それぞれの得票数。
vector<int>win (m);//ポイントがもらえるのはどっちか？
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
//投票結果を配列に入れていく。
char x;
cin >> x;
if(x == '0'){
num[i][j] = 0;
bt[j][0]++;
}else{
num[i][j] = 1;
bt[j][1]++;
}
//最後まで見たら結果を確認
if(i == n-1){
if(bt[j][0] == 0) win[j] = 1;
else if(bt[j][1] == 0) win[j] = 0;//どっちかが0ならもう一方に
else if(bt[j][0] < bt[j][1]) win[j] = 0;
else win[j] = 1;//0じゃなければ小さいほうに
}
}
}
set<int>ans;
int mx = 0;//トップの得票数。
for(int i=0;i<n;i++){
int cnt = 0;
for(int j=0;j<m;j++){
if(num[i][j] == win[j]) cnt++;
}
if(cnt > mx){
//暫定トップを抜いた場合
ans.clear();//今までのことは忘れる
ans.insert(i+1);//今確認した人が暫定トップに
mx = cnt;
}else if(cnt == mx) ans.insert(i+1); //トップタイなら追加
}
for(auto x:ans) cout << x << endl;
}
C - Sum of Min Query
考察
毎回変更するごとに合計を調べてるようじゃ到底間に合わない。
ただ、よく考えれば各番号の最小値は変更した場所以外変わるはずがない。
なので、変更ポイントの増減だけを確認すればいい。
要するに、あらかじめ合計を出して置く。その後値の変更があった場合、その番号の増減だけ合計に手を加えればいい。
脱・初心者の導入みたいな問題だなぁ。
提出
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
int n,q;
cin >> n >> q;
vector<ll>numa (n),numb (n);//配列Aと配列Bを用意
for(int i=0;i<n;i++) cin >> numa[i];
ll sum = 0;
for(int i=0;i<n;i++){
cin >> numb[i];
//あらかじめ小さいほうの合計を出しておく。
sum += min(numa[i],numb[i]);
}
for(int i=0;i<q;i++){
char x;
ll y,z;
cin >> x >> y >> z;
y--;
//まず、合計から変更ポイントの値を引いておく。
sum -= min(numa[y],numb[y]);
//値を変更する。
if(x == 'A')numa[y] = z;
else numb[y] = z;
//変更後の値を足しなおす。
sum += min(numa[y],numb[y]);
cout << sum << endl;
}
}
D - Toggle Maze
考察
よく、グリッドで多彩な問題がつくれるなぁ。
条件が多く見えるが要するに
?を踏んだ回数が偶数回→Oが道で、Xが壁
?を踏んだ回数が奇数回→Oが壁で、Xが道
になる迷路を最短で進めってこと。
考え方に好みがあるだろうが今回は「偶数踏んだ世界」と「奇数踏んだ世界」の二つを作り出しこれを行き来する幅優先探索で実装。
?を踏むたびに別世界に移動すればよくて、答えは「偶数世界」と「奇数世界」のゴールマスのうちより近いほうになる。
+を付け忘れて30分ぐらいバグらせる。
お前早解き回なめてんだろ。
提出
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
int h,w;
cin >> h >> w;
//偶数世界と奇数世界を作る。
//うっかり範囲外を探索しないように周りを壁でかこむ。
vector<vector<vector<char>>>maz (2,vector<vector<char>>(h+2,vector<char>(w+2,'#')));
int sx,sy,gx,gy;
for(int i=1;i<=h;i++){
for(int j=1;j<=w;j++){
char c;
cin >> c;
if(c == 'S'){
//スタート地点をメモして道にする。
sx = i,sy = j;
maz[0][i][j] = maz[1][i][j] = '.';
}else if(c == 'G'){
//スタート地点をメモして道にする。
gx = i,gy = j;
maz[0][i][j] = maz[1][i][j] = '.';
}else if(c == 'o') maz[0][i][j] = '.';//偶数世界の時道
else if(c == 'x') maz[1][i][j] = '.';//奇数世界の時道
else maz[0][i][j] = maz[1][i][j] = c;//それ以外はそのまま
}
}
int inf = (1<<30);
vector<vector<vector<int>>>stp (2,vector<vector<int>>(h+2,vector<int>(w+2,inf)));
stp[0][sx][sy] = 0;//スタート地点は偶数世界。
queue<pair<int,pair<int,int>>>que;
que.push({0,{sx,sy}});
while(!que.empty()){
auto[wld,xy] = que.front();
auto[x,y] = xy;
que.pop();
for(int i=-1;i<2;i+=2){
if(maz[wld][x+i][y] != '#'){
if(maz[wld][x+i][y] == '?'){
//？を踏んだら別世界に
if(stp[1-wld][x+i][y] > stp[wld][x][y] + 1){
stp[1-wld][x+i][y] = stp[wld][x][y] + 1;
que.push({1-wld,{x+i,y}});
}
}else{
//道ならそのまま
if(stp[wld][x+i][y] > stp[wld][x][y] + 1){
stp[wld][x+i][y] = stp[wld][x][y] + 1;
que.push({wld,{x+i,y}});
}
}
}
if(maz[wld][x][y+i] != '#'){
if(maz[wld][x][y+i] == '?'){
//？を踏んだら別世界に
if(stp[1-wld][x][y+i] > stp[wld][x][y] + 1){
stp[1-wld][x][y+i] = stp[wld][x][y] + 1;
que.push({1-wld,{x,y+i}});
}
}else{
//道ならそのまま
if(stp[wld][x][y+i] > stp[wld][x][y] + 1){
stp[wld][x][y+i] = stp[wld][x][y] + 1;
que.push({wld,{x,y+i}});
}
}
}
}
}
//両方無限大なら到達不能。
if(stp[0][gx][gy] == inf && stp[1][gx][gy] == inf) cout << "-1" << endl;
else cout << min(stp[0][gx][gy],stp[1][gx][gy]) << endl;
}
E - Reachability Query
考察
見た瞬間に分かる。D問題よりこっちのほうが簡単。
問題からしてUnionFindを使えという圧が強い。なのでおとなしくUnionFindで実装。
この時グループ化された頂点同士は自由に行き来できるので、この中に黒が含まれているかどうかが問題となる。
毎回、知りたい頂点と黒の頂点が同じかをすべて試してはUnionFindを使った意味がないほどに時間が掛かる。
じゃあ、どうするか？そもそも、「知りたい頂点から黒に行けるか？」だけが知りたいことであり、「どの黒に行くか？」には興味がない。
なので、グループごとに含まれている黒の数を持っておけば万事解決。
正直この問題を見て負けを確信しました。
こんなんめっちゃ解かれるやん。
提出
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct UF{
vector<int>par;
vector<int>clr;//グループの黒の数を管理
UF(int n):par(n),clr(n,0){
for(int i=0;i<n;i++) par[i] = i;
}
int root(int n){
if(par[n] == n) return n;
return par[n] = root(par[n]);
}
void unite(int n,int m){
int rn = root(n),rm = root(m);
if(rn == rm) return;
par[rn] = rm;
clr[rm] += clr[rn]//黒の数を親に伝達
return;
}
void cg(int n,int m){
int rn = root(n);
clr[rn] += m;
}
void ans(int n){
int rn = root(n);
//グループに黒が含まれるか?
if(clr[rn] == 0) cout << "No" << endl;
else cout << "Yes" << endl;
}
};
int main(){
int n,q;
cin >> n >> q;
UF tree(n);
vector<int>now (n,0);//各頂点の色を管理
for(int i=0;i<q;i++){
int x;
cin >> x;
if(x == 1){
int y,z;
cin >> y >> z;
//頂点Yと頂点Zを結合
tree.unite(y-1,z-1);
}
if(x == 2){
int y;
cin >> y;
y--;
//黒になるならグループの数を増やす、そうでないなら減らす。
if(now[y] == 0) tree.cg(y,1);
else tree.cg(y,-1);
//色を変更
now[y] = 1 - now[y];
}
if(x == 3){
int y;
cin >> y;
tree.ans(y-1);
}
}
}
G - sqrt(n²+n+X)
考察
順位表を見ると[F:AC33人][G:AC200人]という状況。
どう考えても勝機はG問題なのでこっちに飛び込む。
はい、数学問題です。閃けば勝てます。
$\sqrt{n^2 + n+X} = K$
と置いて両辺を二乗して移項すると
$n^2+n+X-K^2 = 0$
となる。ここに解の公式を使えば
$n=\frac{-1\pm\sqrt{1-4\times(X-K^2)}}{2}$
となる。
この時、ルートの中身が平方数じゃないとnも整数でなくなるので
$1-4\times(X-K^2) = S^2$
と置く。さらに式変形をすると、
$1-4X = S^2 - 4K^2 ⇔ 1-4X = (S-2K)(S+2K)$
となる。
ここで$1-4X = a\times b(a \leq b)$となる$a,b$を用意する。
この時$0 \leq S,K$より$a = S-2K,b = S+2K$となる。
$a+b = 2S ⇔ S=\frac{a+b}{2}$となる。これを解の公式に代入すると、
$n = \frac{-1\pm \frac{a+b}{2}}{2} ⇔ n = \frac{-2\pm(a+b)}{4}$
nが整数になるには$(a+b)\equiv2(mod4) $となればいい。
Q.E.D
証明が完了したところで方針を整理すると、
$1-4X = a\times b(a \leq b)$となるすべての$a,b$について$(a+b)\equiv2(mod4) $となるものを全列挙できればいい。
$4\times10^{14}$以下で約数が最も多いもので25000個位なので何とかなる。
15分オーバーでAC。
迷路のせいですね！
提出
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<vector<ll>>num;
vector<ll>pri;
set<ll>st;
ll siz;
//高速で素数求めるやつ
void rrp(ll n){
vector<bool>num (n);
pri.resize(0);
for(ll i=2;i<n;i++){
if(num[i]) continue;
pri.push_back(i);
for(ll j=2;j*i<n;j++) num[i*j] = true;
}
return;
}
//約数を全列挙するやつ
void DFS(ll x,ll now){
if(now == siz){
st.insert(x);
return;
}
for(auto y:num[now]){
DFS(x*y,now+1LL);
}
return;
}
int main(){
//2*10^7以下の総数があればOK
rrp(2e7+2);
ll n;
cin >> n;
num.resize(0);
n = 1LL - 4*n;//主役
bool ng = false;//マイナスは後で考えるので負の数だったかをチェック
if(n < 0){
ng = true;
n = -n;
}
for(auto x:pri){
if(n == 1) break;
if(n%x == 0){
vector<ll>check (1,1LL);
//割れるだけp^0,p^1,p^2...を追加
while(n%x == 0){
check.push_back(check.back() * x);
n /= x;
}
num.push_back(check);
}
}
//デカい素数は直接挿入
if(n != 1) num.push_back({1,n});
siz = num.size();
DFS(1LL,0);//約数を全列挙。
ll mx = *st.rbegin();
set<ll>ans;
for(auto a:st){
//小さい順に取り出す
//(b<a)の時には興味がないので終了。
if(mx / a < a) break;
ll b = mx/a;
if(ng) a = -a;
//マイナスはaに着ける。
//bに着けるとSが負になるので。
if((a+b)%4LL == 2LL){
//4で割ると2余るとき。
ll s = a+b;
//ｎの値を求める。
ans.insert((-2LL+s)/4LL);
ans.insert((-2LL-s)/4LL);
}
}
cout << ans.size() << endl;
for(auto x:ans) cout << x << endl;
}
結果
ABCDE 5完 58:46
順位 2037位
パフォーマンス 1177
レート 1350(-18)
感想
5完したら水パフォは担保してほしいのです。
ケアレスミスがなければG問題にも手が届いたというこのが何よりも悔しい。
やっぱりJOIから逃げるべきではないのか。