日本語の難しさに躓いた男の備忘録です
コンテスト概要
AtCoder Beginner Contest 430
開催日:2025年11月1日 21:00-22:40
A - Candy Cookie Law
考察
読解が大事なＡ問題。
「飴をA個以上所持している人はクッキーをB個以上所持していなければならない」を正しく読み解く。
要するにダメなパターンは「飴がＡ個以上かつクッキーがＢ個未満」の時だけ。
これを実装できればＯＫ。
「してはいけない」と「しなければならない」を見間違えて時間ロス。
落ち着いて読みましょう。
提出
#include <bits/stdc++.h>
using namespace std;
int main(){
int a,b,c,d;
cin >> a >> b >> c >> d;
//飴がA以上かつクッキーがB未満の時だけ犯罪。
if(c >= a && d < b) cout << "Yes" << endl;
else cout << "No" << endl;
}
B - Count Subgrid
考察
身構えていたB問題。250点問題は面倒かクソ簡単の2択と思ってる。
今回は面倒。
種類数はsetに突っ込めば勝手に重複を消してくれるので簡単に求まる。
そしてsetは宣言さえすればvectorでも入れることができるので、任せてしまおう。
むやみにvectorを入れるのメモリ不足が心配だが、盤面も高々100マスなので心配はいらないだろう。
今回は少しでもメモリを確保するために2進表記で管理。
M×Mの範囲を全パターン調べ上げてsetに入れる。これでOK。
グリッド探索ってちょっと手間で嫌いなんだよね。
提出
#include <bits/stdc++.h>
using namespace std;
int main(){
int n,m;
cin >> n >> m;
set<vector<int>>st;
//グリッドを0と1に変換しておく
//#が1、.が0
vector<vector<int>>num (n,vector<int>(n,0));
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
char x;
cin >> x;
if(x == '#') num[i][j] = 1;
}
}
for(int i=0;i+m<=n;i++){
for(int j=0;j+m<=n;j++){
vector<int>vec (m,0);
//すべてのM×Mを探索する。
for(int s=0;s<m;s++){
for(int t=0;t<m;t++){
//bitをずらすことで2進表記を作る。
vec[s] <<= 1;
vec[s] += num[i+s][j+t];
}
}
//setに入れる。
st.insert(vec);
}
}
//setの要素数が答え。
cout << st.size() << endl;
}
C - Truck Driver
考察
ルールの説明いらなくない？
どんな方針にせよ、範囲内のaの個数、bの個数を高速で知りたいのでそれぞれの個数の累積和をあらかじめ求めておく。
ただ、これで高速にはなったが、全部の範囲を求めているようでは時間が足りない。どうにかまとめて計算したい。
ここで、具体例を出しながら様子を見てみる。
例えば$L$文字目から$R$文字目までの間にある$a$の個数が$A$個以上の時、当然$L$文字目から$(R+1)$文字目までの間にある$a$の個数はもちろん$A$個以上になる。これは$b$の時も言える。
$L$文字目を固定して$a$の個数が初めて$A$個になるところを$R_a$文字目、$b$の個数が初めて$B$個になるところを$R_b$文字目としてみる。
すると、$R_a$文字目以降は常に$A$個以上あり、$R_b$文字より手前は$B$個以上ある。
つまり$R_a \leq R \leq R_b$となる$R$が条件を満たすことになる。
その個数は$R_b - R_a$個となる。
方針をまとめると、
〇左端を固定する。
〇$R_a$の下限と$R_b$の上限を求める。(二分探査が使える。)
〇下限と上限の差を足す。
これでOK。
$R_b < R_a$になる可能性があるのでそこは注意。
提出
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
int n,a,b;
cin >> n >> a >> b;
//aとbごとに出現回数の累積和を取っておく
vector<int>na (n+1,0),nb (n+1,0);
for(int i=0;i<n;i++){
char x;
cin >> x;
na[i+1] += na[i],nb[i+1] += nb[i];
if(x == 'a') na[i+1]++;
if(x == 'b') nb[i+1]++;
}
ll ans = 0;
for(int i=0;i<n;i++){
int af = na[i],bf = nb[i];
//二分探査で範囲を求める。
//aの個数がA以上になるRの下限を求める。
ll ac = lower_bound(na.begin(),na.end(),af+a) - na.begin();
//bの個数がB未満になるRの上限を求める。(引き算しやすいように上限+1)
ll bc = lower_bound(nb.begin(),nb.end(),bf+b) - nb.begin();
//上限と下限の差を足す
//値が負になるなら無視。
ans += max(0LL,bc - ac);
}
cout << ans << endl;
}
D - Neighbor Distance
考察
二問連続二分探査だね。ちょっと怖いね。
C問題同様、毎回距離を求めているようでは到底時間が足りない。
また、具体例を出して考えてみる。
Cさんが列に入る。AさんとBさんの間に割り込んだとする。
この時のそれぞれの最短距離の変化を考えると、AさんとBさん以外の距離は変化しない。
なぜなら、最短距離は「左隣の人との距離」と「右隣の人との距離」より短いほうのはず。となると、自分の両隣に変化がないのに最短距離も変わりようがない。
なのでAさんとBさんの変化量にだけ注目すればいい。
もし、最短距離が短くなればその分合計から減らせばいいし、変わらないんだったら何もしなければいい。
というわけで、あらかじめ距離の合計を出して置き、都度変化するところだけを見ればよい。
ちなみに、右端の人がいないとバグりやすいので、あらかじめ果てしなく遠い場所に一人おいておくと実装しやすい。
提出
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
//果てしなく遠い場所。
ll inf = (1LL<<35);
int main(){
int n;
cin >> n;
//各人のいる場所。勝手に昇順に並んでくれるのでsetで管理。
set<ll>st;
st.insert(0),st.insert(inf);
//距離iにいるのが誰なのかを管理。
map<ll,int>mp;
mp[0] = 0, mp[inf] = n+1;
//全員の最短距離を管理。
vector<ll>dist (n+2,inf);
//最初は右端と左端の二人の合計。
ll sum = inf*2LL;
for(int i=1;i<=n;i++){
ll x;
cin >> x;
//一番近い右隣の人の距離。
ll a = *st.lower_bound(x);
//一番近い左隣の人の距離。
ll b = *prev(st.lower_bound(x));
//そこに誰がいるのか
int ad = mp[a],bd = mp[b];
//差分の変更
//今の値を引いて更新後を足すのが楽。
sum -= dist[ad];
dist[ad] = min(a-x,dist[ad]);
sum += dist[ad];
sum -= dist[bd];
dist[bd] = min(x - b,dist[bd]);
sum += dist[bd];
//iさんの距離も足し忘れない。
dist[i] = min(a-x,x-b);
sum += dist[i];
//バグ防止にはるか遠くに置いた人の値は引いておく。
cout << sum - dist[n+1] << endl;
//iさんを追加しておく。
st.insert(x);
mp[x] = i;
}
}
E - Shift String
考察
最近のE問題、問題文が簡素すぎる。
文字列Aを実際に動かしていると時間が足りなので動かした振りをしたい。
こういう時は文字列を2つ連結して先頭の番号をずらせばいい。
こうなれば2つの文字列は簡単に求まるので2つを比べればいい。
が、たぶんTLEになる。文字列の抜き出し、照合には時間が掛かるから。
さっと抜き出し、さっと比べたい。
こういうニーズにこたえてくれるのがローリングハッシュである。
簡単に言うと文字列をデカい数字としてとらえたうえで引き算で文字列を抜き出す方法である。
今回であれば、文字列を2進表記の数字としてとらえればいい。
もちろんそのままだと大きすぎてオーバーフローするのでいい感じの素数で割った余りを使う。
こうすれば数字を照合するだけなのでまぁまぁ早くなる。
ここで、問題になるのがハッシュ衝突である。違う数なのに余りが偶然一致してしまうと比較が無意味になってしまう。どうしようか。
解決策はパワー。いっぱい素数を用意すればいい。
ということで今回は大事を取って10個の素数を用意して実装。
初めてローリングハッシュ本番で通したなぁ。
提出
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
//いい感じの素数10個
vector<ll>mods = {117679291,171899227,192066599,214544917,235497281,246741221,307905769,327907667,384420923,508044877};
int main(){
int t;
cin >> t;
int lim = 1000001;
//あらかじめ2の累乗をそれぞれの素数で割った余りを求める。
vector<vector<ll>>div (10,vector<ll>(lim,1));
for(int i=1;i<lim;i++){
for(int j=0;j<10;j++){
div[j][i] = (div[j][i-1]<<1);
div[j][i] %= mods[j];
}
}
for(int rp=0;rp<t;rp++){
string s,t;
cin >> s >> t;
//とりあえず文字列を倍に
s += s;
int n = t.length();
//文字列Aをハッシュ化
vector<vector<ll>>num (n*2+1,vector<ll>(10,0));
for(int i=0;i<n*2;i++){
ll x = 0;
if(s[i] == '1') x = 1;
for(int j=0;j<10;j++){
num[i+1][j] = (num[i][j] << 1);
num[i+1][j] %= mods[j];
num[i+1][j] += x;
num[i+1][j] %= mods[j];
}
}
//文字列Bもハッシュ化
vector<ll>check (10,0);
for(int i=0;i<n;i++){
ll x = 0;
if(t[i] == '1') x = 1;
for(int j=0;j<10;j++){
check[j] <<= 1;
check[j] %= mods[j];
check[j] += x;
check[j] %= mods[j];
}
}
int ans = -1;
for(int i=n;i<=n*2;i++){
bool che = true;
for(int j=0;j<10;j++){
//ハッシュ値は1,12,123,1234と後ろに数字を追加する形で生成している
//1234から34だけを抜き取るには
//1234 - 12*100 と計算する感覚で文字列を抜き出す。
ll mn = num[i-n][j] * div[j][n];
mn %= mods[j];
ll c = num[i][j] + mods[j] - mn;
c %= mods[j];
//1つでも違ったらNG
if(c != check[j]) che = false;
}
//10個のハッシュ値が一致したなら多分OK
if(che){
ans = i-n;
break;
}
}
cout << ans << endl;
}
}
F - Back and Forth Filling
考察
6個も振り返るのはしんどいので簡潔に書き記す。
1文字目がLの時位置関係は[2→1],Rなら[1→2]となる。この右矢印の位置関係をいい感じにまとめてあげると数字の関係をDAGとしてとらえることができる。
あとは各数字において初めてどの矢印からも刺されなくなる最短のタイミング、どうしても選ばざる負えなくなる最長のタイミングを求めたい。
これが求まればその数字が使える場所が[最短～最長]の範囲になり、imos法とかで個数が求まる。
さてこのタイミングだが最短のタイミングは矢印を逆走したどり着ける頂点の数に等しく、最長は矢印をたどりたどり着けない頂点の個数に等しい。
証明は分からないが、図を描くと直感的にそうなる。
というわけでBFSとかで求めればおしまい。
図がないとわかりにくいですね。気が向いたら追記します。
提出
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
int t;
cin >> t;
for(int rp=0;rp<t;rp++){
int n;
cin >> n;
//dep:右向きの矢印、arr:左向きの矢印。
vector<vector<int>>dep (n,vector<int>(0)),arr (n,vector<int>(0));
for(int i=0;i<n-1;i++){
char c;
cin >> c;
//正しい向きに矢印を指す。
if(c == 'L') dep[i+1].push_back(i),arr[i].push_back(i+1);
if(c == 'R') dep[i].push_back(i+1),arr[i+1].push_back(i);
}
//bg:最短のタイミング、ed:最長のタイミング
vector<int>bg (n,0),ed (n,1);
vector<int>cnt (n,0);
queue<int>qb,qe;
for(int i=0;i<n;i++){
if(arr[i].size() == 0) qb.push(i);
if(dep[i].size() == 0) qe.push(i);
}
//最短を求める。
while(!qb.empty()){
int now = qb.front();
qb.pop();
for(auto nex:dep[now]){
//刺されている頂点の個数分遅れる。
cnt[nex]++;
bg[nex] += bg[now] + 1;
if(arr[nex].size() == cnt[nex]) qb.push(nex);
}
}
vector<int>ct (n,0);
//最長を求める。
while(!qe.empty()){
int now = qe.front();
qe.pop();
for(auto nex:arr[now]){
//後ろにある頂点分早まる。
ct[nex]++;
ed[nex] += ed[now];
if(dep[nex].size() == ct[nex]) qe.push(nex);
}
}
vector<int>ans (n+1,0);
//imos法で足し合わせる。
for(int i=0;i<n;i++) ans[bg[i]]++,ans[n-ed[i]+1]--;
for(int i=0;i<n;i++){
if(i != 0){
ans[i] += ans[i-1];
cout << " ";
}
cout << ans[i];
}
cout << endl;
}
}
結果
ABCDEF 6完 83:12
順位 357位
パフォーマンス 1791
レート 1484(+40)
感想
得意分野+最近勉強したところが出て大勝利！
この勝ちが続くように苦手を徹底的につぶしたい。
rateの改変もあり今年度中の入青も見えてきたな。