JOI過去問で臥薪嘗胆していた男の備忘録です
コンテスト概要
AtCoder Beginner Contest 395
開催日:2025年3月1日 21:00-22:40
A - Strictly Increasing?
考察
前から2項ずつ調べればOK。$A_i = A_{i+1}$は狭義単調増加ではないことだけに注意。
提出
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
cin >> n;
string ans = "Yes";
//先頭に明らかに小さい数字(今回は0)を置いておく
int bef = 0;
for(int i=0;i<n;i++){
int x;
cin >>x;
//ひとつ前が大きいならNo
if(bef >= x) ans = "No";
bef = x;
}
cout << ans << endl;
}
B - Make Target
考察
高々制約が50なので50X50マスを黒で塗って48X48マスを白く塗って...とやっても多分間に合う。
ただサイズが決まっていれば座標(i,j)の色は偶奇のみで決まるので二重ループでのその色を出題すればOK。
類題はこれ(https://atcoder.jp/contests/abc264/tasks/abc264_b)
提出
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
cin >> n;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
//上から、下から、右から、左から数えたときの最小値の探す
int x = min(i,n-1-i),y=min(j,n-1-j);
//最小値が奇数なら白、偶数なら黒
if(min(x,y) %2 == 1) cout << '.';
else cout << '#';
}
cout << endl;
}
}
C - Shortest Duplicate Subarray
考察
前から順番に見て、同じ数が出るまで調べていると$O(N^2)$なので当然ダメ。
ここで数ごとに出現したタイミングをメモしておく。この時ある数が2回出る長さは [n回目に出たタイミング]-[n-1回目に出たタイミング] になる。これなら$O(N)$で済みそう。
提出
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
int n;
cin >> n;
//数ごとに出現タイミングをメモ。
vector<vector<int>>num (1000001,vector<int>(0));
for(int i=0;i<n;i++){
int x;
cin >> x;
num[x].push_back(i);
}
int ans = lim;
for(auto che:num){
int siz = che.size();
//出てきた回数が2回未満なら無視
if(siz < 2) continue;
//出現間隔の最小値が答え
for(int i=1;i<siz;i++){
ans = min(ans,che[i]-che[i-1]+1);
}
}
if(ans == lim) ans = -1;
cout << ans << endl;
}
D - Pigeon Swap
考察
これの応用問題っぽいし、別物っぽくもある。
鳩ごとにどこの巣に居るかの住所録を作っておけば、操作1は住所を書き換えるだけでおしまいだし、操作３は住所録をそのまま出力すればいい。
ただ操作2が面倒。鳩の巣を入れ替えるとそこの鳩の住所をすべて書き換えなければいけない。最悪N羽すべての鳩を入れ替える可能性がある。何とかここを簡略化したい。
なら、入れ替えたことにすればいい。鳩の巣ではなく鳩ノ巣の番号が書かれた表札だけを入れ替えれば高々2つの入れ替えで済む。
実装がややこしく、ひぃひぃ言いながらAC。
提出
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
int n,q;
cin >> n >> q;
//鳩ノ巣のある住所とそこにかかっている表札を管理
map<int,int>kan,pos;
vector<int>pg (n);
for(int i=0;i<n;i++){
//鳩はiにいるし、住所iの巣には表札iがかかっている。
pg[i] = i,kan[i] = i,pos[i] = i;
}
for(int i=0;i<q;i++){
int x;
cin >> x;
if(x == 1){
int a,b;
cin >> a >> b;
a--,b--;
//表札bのかかった巣に移動
pg[a] = pos[b];
}
if(x == 2){
int a,b;
cin >> a >> b;
a--,b--;
//表札aと表札bを付け替える。住所も入れ替え
int s = pos[a],t = pos[b];
kan[s] = b,kan[t] = a;
pos[a] = t,pos[b] = s;
}
if(x == 3){
int a;
cin >> a;
a--;
//鳩aがいる住所にかかっている表札の数字を出力
cout << kan[pg[a]] + 1 << endl;
}
}
}
E - Flip Edge
考察
矢印が正の向きの「0の世界」と矢印が負の向きの「1の世界」があり、最初「1の世界」の１マス目にいる。このマスから「矢印の向きに進む」「別世界に行く」の２つの行動をし、それぞれのマスのコストが小さい順に次の行動をする。
これを繰り返す。要するにダイクストラをしろってことになる。
実装がちょっと複雑だがD問題に比べれば見やすいはず。(なお、カッコつけて1ペナを食らう)
提出
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll inf = (1LL<<60);
template<typename T> using p_que = priority_queue<T,vector<T>,greater<T>>;
int main(){
ll n,m,c;
cin >> n >> m >> c;
//世界ごとにルートを管理。
vector<vector<vector<int>>>path (n,vector<vector<int>>(2,vector<int>(0)));
for(int i=0;i<m;i++){
int x,y;
cin >> x >> y;
x--,y--;
path[x][0].push_back(y);
path[y][1].push_back(x);
}
vector<vector<ll>>dp (2,vector<ll>(n+1,inf));
dp[0][0] = 0;
p_que<pair<ll,pair<int,int>>>que;
que.push({0,{0,0}});
while(!que.empty()){
//今いるマスの内最もコストが小さいものから順に考える
auto [cst,aaa] = que.top();
auto [mod,pos] = aaa;
que.pop();
if(cst > dp[mod][pos]) continue;
int ch = (mod+1)%2;
//別世界の同じマスに行ってないなら行く
if(dp[ch][pos] == inf){
dp[ch][pos] = dp[mod][pos] + c;
que.push({dp[ch][pos],{ch,pos}});
}
//同世界の隣マスに行ってないなら行く
for(auto x:path[pos][mod]){
if(dp[mod][x] > dp[mod][pos] + 1LL){
dp[mod][x] = dp[mod][pos] + 1LL;
que.push({dp[mod][x],{mod,x}});
}
}
}
//「0の世界」と「1の世界」のうち小さいものが答え
cout << min(dp[0][n-1],dp[1][n-1]) << endl;
}
F - Smooth Occlusion
考察
まず何とかして上の歯を整形したい。歯は伸ばせず削ることしかできないので短い歯に合わせれば低コストで成形できる(はず)。
短い歯から順番に歯を整形していく。隣の歯との差がXcm以下なら何もしない。そうでないなら差がXcmになるまで隣の歯を削る。これを繰り返せばきれいな上の歯ができる。
後は上の歯と下の歯の合計が一番小さいものに合わせて下の歯を削る。
答えは[最初の歯の長さの合計] - [最終的な歯の長さの合計]
提出
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<typename T> using p_que = priority_queue<T,vector<T>,greater<T>>;
int main(){
ll n ,c;
cin >> n >> c;
vector<ll>ut (n),dt (n);
ll sum = 0;
p_que<pair<ll,int>> que;
for(int i=0;i<n;i++){
cin >> ut[i] >> dt[i];
sum += ut[i] + dt[i];
que.push({ut[i],i});
}
vector<ll>aft = ut;
while(!que.empty()){
//歯を短い順に取り出す。
auto [len,pos] = que.top();
que.pop();
if(len != aft[pos]) continue;
//隣の歯が長ければ差がc以下になるまで削る。
if(pos != 0){
if(aft[pos-1] > len + c){
aft[pos-1] = len + c;
que.push({aft[pos-1],pos-1});
}
}
if(pos != n-1){
if(aft[pos+1] > len + c){
aft[pos+1] = len + c;
que.push({aft[pos+1],pos+1});
}
}
}
ll tl = (1LL<<60);
//上と下の歯の合計の最小値を探る。
for(int i=0;i<n;i++){
tl = min(aft[i]+dt[i],tl);
}
//元あった歯の長さ-今の長さ
cout << sum - tl*n << endl;
}
結果
ABCDE(1)F 6完 71:59
順位 668位
パフォーマンス 1686
感想
ここ2回で92ものレートを溶かしており背水の陣。何とか70ものレートをもぎ取った。
重実装の練習としてJOIの過去問をやりこんだのが効いたのかもしれない。少なくともD以降の問題には効いている。
JOI様様でやんす。次回再入水頑張るぞ。