予習範囲"は"かぶっていた男の備忘録です
コンテスト概要
パナソニックグループ プログラミングコンテスト2025（AtCoder Beginner Contest 406）
開催日:2025年5月17日 21:00-22:40
A - Not Acceptable
考察
提出時間と締め切り時間が同じではないことが保証されているので丁寧に見ていく。
hourが提出のほうが早いか？同じならminutesが提出のほうが早いか？をifで確認。
ほかのやり方だと、時間に60をかけて5月17日から何分後かに値を整形させるとスマート。
まあ、ゆったり考察する時間はないよね。
提出
#include <bits/stdc++.h>
using namespace std;
int main(){
int a,b,c,d;
cin >> a >> b >> c >> d;
if(c < a) cout << "Yes" << endl;// ”時”が提出のほうが早いならYes
else if(a < c) cout << "No" << endl;// ”時”が締め切りのほうが早いならNo
else{//”時”が同じ場合
if(d < b) cout << "Yes" << endl;//”分”が提出のほうが早いならYes
else cout << "No" << endl;//”分”が締め切りのほうが早いならNo
}
}
B - Product Calculator
考察
なんか制約B問題っぽくないですよね？オーバーフローケア必須ですよ、これは。
とりあえずシンプルに掛け算を実装していきたいところ。けれど、今の値が$10^{17}$かける値も$10^{17}$だったらlong long型でも手に負えない。
なので、かける前に値がオーバーするかを見極めたい。
桁の限界をkとするとき、表示できる最大の数字は$10^k-1$(9をk個並べた数)になる。
今の値をNとすれば、表示可能なかける値の最大値は$\frac{10^k-1}{N}$になる。
かけたい値がこの数を超えてるなら１に、そうでないなら普通に掛ければOK。
ここ最近で1番難しいB問題かも。凡ミスもしたし。
提出
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
ll n,k;
cin >> n >> k;
ll now = 1LL;
ll lim = pow(10LL,k)-1;//表示できる限界の数字
for(int i=0;i<n;i++){
ll x;
cin >> x;
ll s = lim/x;//画面に正しく表示できるかける数の限界
if(s < now) now = 1LL;//限界を超えたらリセット
else now *= x;//行けるならそのまま掛ける
}
cout << now << endl;
}
C - ~
考察
問題文から癖のすごさが匂う。まあ350点問題だし、こんな複雑かぁ。
とりあえず$A_{i-1}<A_i>A_{i+1}$を満たす$A_i$を「山」、$A_{i-1}>A_i<A_{i+1}$を満たす$A_i$を「谷」と呼ぶとする。
この時、定義上山と谷が交互に出現する。
探したい数列の形は
...〇〇〇山〇〇〇谷〇〇〇〇...
となる数列である（これがチルダ数列と定義されてる）。さて、山と谷の組み合わせを固定したときこの部分を含むチルダ数列の数が知りたい。値を求めるのは簡単で「山より左にある〇の数」Ｘ「谷より右にある〇の数」で元もある。
問題は一体山より左にいくつ〇があるかである。チルダ数列は初項、末項ともに山谷を定義できない。これを利用して谷から山まで持ってくれば最長のチルダ数列が作れる。
要するに
$谷_{i-1}〇〇〇〇山_i〇〇〇〇谷_i〇〇〇〇山_{i+1}$
と$山_i$と$谷_i$を含む最長のチルダ数列を探し出し、「$谷_{i-1}$から$山_i$までの個数」Ｘ「$谷_i$から$山_{i+1}$までの個数」をそれぞれ計算すればOK。
説明も大変。
提出
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
int n;
cin >> n;
vector<int>num (n);
for(int i=0;i<n;i++) cin >> num[i];
vector<ll>upn (0),dwn (1,0);//upn=山の番号、dwn=谷の番号を管理
for(int i=1;i<n-1;i++){
if(num[i-1] < num[i] && num[i+1] < num[i]) upn.push_back(i);
if(num[i-1] > num[i] && num[i+1] > num[i]) dwn.push_back(i);
}
upn.push_back(n-1);
//便宜上初項を谷、末項を山ということにしておく。
//(範囲外を参照してしまうのを防ぐ)
ll ans = 0;
for(int i=0;i<upn.size();i++){
ll x = upn[i];
auto ite = lower_bound(dwn.begin(),dwn.end(),x);
if(ite == dwn.end()) break;//そもそも山より右に谷がないならおしまい
ll y = *ite;//山iの右にある谷iの番号
ll l = *prev(ite);//山iの左にある谷(i-1)の番号
ll r = upn[i+1];//谷iのみぎにある山(i+1)の番号
ans += (x-l)*(r-y);//左右それぞれの数をかける
}
cout << ans << endl;
}
D - Garbage Removal
考察
やっとさほど複雑でもない問題が出てきた。一安心。
安直なコードとしては二次元配列ですべてのマス目を管理し、操作ごとに見ていくというもの。ただＨもＷも最大値が$2\times10^5$だから最大で$4\times10^{10}$マスを管理しないといけない。しかも1操作ごとに$10^5$回の計算をする可能性がある。間違いなくメモリも時間も足りないので他の方法にするしかない。
高々ゴミは$2\times10^{5}$個しかないのでそれぞれのゴミを監視したほうが現実的っぽい。なのでsetを使って縦と横のどこにゴミがあるかを管理する。方法としては列iにおいてゴミがある場所の列番号をinsert。行でも同じことをする。
例えば列iのゴミを捨てたいとき、まずsizeでゴミの個数を出力。次に列iに含まれるすべての行番号から列iを除いていく。最後にclearで列iのsetを初期化
これを順にやればOK。
ずっと複雑だったから簡単に見える。
提出
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
int h,w,n;
cin >> h >> w >> n;
vector<set<int>>hn (h),wn(w);
for(int i=0;i<n;i++){
int x,y;
cin >> x >> y;
x--,y--;
hn[x].insert(y);//行のsetに列番号を入れる
wn[y].insert(x);//列のsetに行番号を入れる
}
int q;
cin >> q;
for(int i=0;i<q;i++){
int x,y;
cin >> x >> y;
y--;
if(x == 1){
cout << hn[y].size() << endl;//行にあるごみの数を出力
for(auto z:hn[y]){
wn[z].erase(y);//列から行にあったゴミを除く
}
hn[y].clear();//行のゴミをすべて捨てる
}else{
cout << wn[y].size() << endl;//列にあるごみの数を出力
for(auto z:wn[y]){
hn[z].erase(y);//行から列にあったゴミを除く
}
wn[y].clear();//列のゴミをすべて捨てる
}
}
}
E - Popcount Sum 3
考察
桁DPを使う問題。たまたま今日桁DPの問題(ABC387_C)を復習していた私にはとてもタイムリーな問題！
結果ですか？結局ABC387_Cが解けなかったのに解けるわけないじゃないですか！
はい。桁DPが今週の宿題です。頑張ります。
結果
AB(1)CD 4完 46:29
順位 2117
パフォーマンス 1197
感想
桁DPさえ解けていれば...
というかコンテスト直前でVSCodeぶっこわれるというハプニングがあった割に何とかなったかなぁ
とりあえずE問題を安定させないとな。