コンテスト
A問題
感想
$k$を任意の正の整数として、i日目に満月が見られる条件は$i=M+k*P$になっていることである。
$(i-M)%P$を計算して、0であればカウントする。
$(i-M)$がマイナスの場合は対象外。
コンテスト中提出コード
int main() {
ll n = in_ll();
ll m = in_ll();
ll p = in_ll();
ll cnt = 0;
rep1(i,n){
ll t = i-m;
if(t<0) continue;
if(t%p==0) cnt++;
}
print(cnt);
return 0;
}
B問題
感想
ぱっと見難しそうな問題だった。
しかし、入力の制約が小さいので簡単な方法で解ける。
シートが張られる範囲は、$100100$のサイズになる。
そこで$100100$の配列を用意して、そこにシートが覆われるかを記録する。
$A_i,B_i,C_i,D_i$の入力で最大で$100100$の計算量が必要になる。
これが最大で100回あるので、$100100*100$の計算量になる。
$10^6$程度の計算量になるので、間に合う。
コンテスト中提出コード
int main() {
ll n = in_ll();
vvll m(100,vll(100,0));
rep(i,n){
ll a,b,c,d;
cin >> a >> b>> c>>d;
reps(x,a,b) reps(y,c,d) m[x][y]++;
}
ll ans = 0;
rep(x,100) rep(y,100) if(m[x][y] >= 1) ans ++;
print(ans);
return 0;
}
C問題
感想
$F_i$を値段でソートして、大きい方から$D$個ずつの和を計算する。
大きい方から$D$個ずつの和を$W_i$とする。
$W_i>P$なら、周遊パスを使うことにする、そうでなければ通常料金を払う。
実装方面での話
$N%D!=0$のとき計算しづらいので、$N%D==0$になるように$0$を追加することにした。
0を追加しても、計算結果は変わらない。
また、実装を見てわかるようにバグりやすそうなコードを書いてしまった。
実際、実装に手間取り時間がかかってしまった。
rustならchunkを使えば簡単に実装できるが、c++にはchunkがなさそう。
c++23で使えることにはなっているが、時期の問題かAtCoder環境では使えなかった。
https://atcoder.jp/contests/abc318/submissions/45211442
chunkはたまに使いたくなるので、スニペットとして持っておこうと思う。
コンテスト中提出コード
int main() {
ll n = in_ll();
ll d = in_ll();
ll p = in_ll();
vll f = in_vll(n);
rep(i, (d-n%d)%d) f.pb(0);
sort(all(f));
dbg(f);
ll ans = 0;
rep(i, f.size()/d) {
ll t = 0;
rep(j,d){
t+=f[j+i*d];
}
if(t>p)ans +=p;
else ans+=t;
dbg(ans);
}
print(ans);
return 0;
}
スニペット使用版
int main() {
ll n = in_ll();
ll d = in_ll();
ll p = in_ll();
vll f = in_vll(n);
sort(all(f),greater<ll>());
ll ans = 0;
ll chunk_size = d;
vll v = f;
rep(i, (v.size()+chunk_size-1)/chunk_size) {
ll t = 0;
rep(j,chunk_size){
if(j+i*chunk_size>=v.size()) break;
t+=v[j+i*chunk_size];
}
if(t>p)ans+=p;
else ans+=t;
}
print(ans);
return 0;
}
vscodeのスニペット
"chunk": {
"prefix": "chunk",
"body": [
" ll chunk_size = $1;",
" vll v = $2;",
" rep(i, (v.size()+chunk_size-1)/chunk_size) {",
" vll tmp(chunk_size);",
" rep(j,chunk_size){",
" if(j+i*chunk_size>=v.size()) break;",
" tmp[j] = v[j+i*chunk_size];",
" }",
" }",
],
"description": ""
},
D問題
感想
同様の問題を以前見たことがあった。
全探索することを考える。
この問題は、$N$個の頂点の中でペアを作り、ペア同士の辺の重みの総和を計算する問題と考える。
すると、全探索すべきは頂点のペアである。
以下のように頂点ペアを全探索する。
- $1$とのペアを全探索する。
- これ以前に使っていない頂点の中で最小の頂点とのペアを探索する。
- 2を繰り返す。
1とのペアの候補は$N-1$個ある。
1とそのペア以外の中で最小の頂点は1個のみ。
その頂点とのペアは$N-3$個ある。
このように考えると、計算量は最大で、$15×13×11×…=2027025$となり、間に合う。
$N$が偶数の時は、これでうまくいくが、奇数の時には少し工夫が必要になる。
$N$が偶数の時、全ての頂点は必ず選ばれるが、奇数の時には選ばれない頂点が1つできることになる。
つまり、最初に$1$から始めているが、奇数のときには$1$が選ばれないこともある。
そこで、$N$が奇数の時はダミーの頂点を一つ加えて偶数として計算することにする。
ダミーの頂点と他の頂点との重みを0とすると、一つ選ばないことと同等になる。
実装後に奇数ではうまくいかないことに気づいたので、ちょっと汚いコードになっている。
公式解説を見ると、bitDPで解けるらしいので、こちらでも解いてみる。
コンテスト中提出コード
int main() {
ll n = in_ll();
vvll d;
if(n%2==0) d.resize(n, vll(n));
else d.resize(n+1, vll(n+1));
rep(i,n-1) reps(j,i+1,n){
ll t; cin >> t;
d[i][j] = t;
d[j][i] = t;
}
vll done;
if(n%2==0) done.resize(n);
else {done.resize(n+1); n++;}
set<pii> s;
auto dfs = [&](auto &self, ll x) -> ll{
if(s.size()==n/2){
ll t = 0;
fore(si,s){
t+= d[si.first][si.second];
}
return t;
}
ll ret = 0;
done[x] = true;
rep(i,n) if(done[i]==false){
done[i] = true;
s.insert({x,i});
ll nx = -1;
rep(j,n) if(done[j]==false){nx=j;break;}
chmax(ret,self(self,nx));
done[i] = false;
s.erase({x,i});
}
done[x] = false;
return ret;
};
print(dfs(dfs,0));
return 0;
}
E問題
感想
Dまでで時間を使いすぎてしまったので、ほとんど手をつけることができず。
あとで解説見ないでACした。
ある数字がどのインデックスで現れるかを保存する。
例えば入力例1の場合だと、以下のようになる。
$1:0,2$
$2:1,4$
$3:3$
例えば1番目の場合、$0,2$の間には1つ数字が入ることになり、それは$1$ではないことがわかる。
つまり、各インデックスの間に数字がいくつ入るか数えると答えに近づきそうである。
次に、ある数字が3つ以上出てくることを考える。
例えば、入力例3の11に着目してみる。
$11: 2,8,9,10$
$(2,8)$の間には5つの数字がある。
$(8,9)$の間には数字はない。
なので、$9$まで見た時条件を満たす数は5つと思わせて、実は$(2,9)$の組み合わせでも良い。
$(2,9)$間の数を考えると、$(2,8)$間の数+$(8,9)$間の数になる。
よって、$9$まで見た時の条件を満たす数は10になる。
即ち、インデックスの数が3つ以上になるとインデックス間の数が重複してカウントされることになる。
重複がどのようになっているか考える。
例えば、インデックスの数がk個あるとし、それぞれのインデックスを$i_1,i_2…i_k$とする。
まず、$(i_1,i_2)$間の数がどれだけ重複するか考える。
$(i_1,i_2)$間の数をカウントするタイミングは、以下のインデックスの組み合わせがあり得る。
$(i_1,i_2)$,$(i_1,i_3)$,…$(i_1,i_k)$
つまり、$(i_1,i_2)$間の数は$k-1$回重複する。
次に$(i_2,i_3)$間の数がどれだけ重複するか考える。
$(i_2,i_3)$をカウントする必要があるのは、$i_1$から$i_3$以降のインデックスと、$i_2$から$i_3$以降のインデックスになる。
$i_1$から$i_3$以降のインデックスは$k-2$個ある。
$i_2$から$i_3$以降のインデックスも$k-2$個ある。
つまり、$(i_2,i_3)$間の数は$(k-2)×2$回重複する。
次に$(i_3,i_4)$間の数がどれだけ重複するか考える。
$(i_2,i_3)$をカウントする必要があるのは、$i_1$から$i_4$以降のインデックスと、$i_2$から$i_4$以降のインデックスと、$i_3$から$i_4$以降のインデックスになる。
$i_1$から$i_4$以降のインデックスは$k-3$個ある。
$i_2$から$i_4$以降のインデックスも$k-3$個ある。
$i_3$から$i_4$以降のインデックスも$k-3$個ある。
つまり、$(i_2,i_3)$間の数は$(k-3)×3$回重複する。
$(i_j,i_{j+1})$間の数がどれだけ重複するかを考えると、$i_1$から$i_{j+1}$以降のインデックス、$i_2$から$i_{j+1}$以降のインデックス、…$i_{j}$から$i_{j+1}$以降のインデックスになる。
$i_1$から$i_{j+1}$以降のインデックスは、$k-j$個ある。
$i_2$から$i_{j+1}$以降のインデックスは、$k-j$個ある。
…
$i_j$から$i_{j+1}$以降のインデックスは、$k-j$個ある。
よって、$(i_j,i_{j+1})$間の数は$(k-j)×j$回重複する。
後日提出コード
int main() {
ll n = in_ll();
vll a = in_vll(n);
vvll id(n);
rep(i,n){
id[a[i]-1].pb(i);
}
dbg(id);
ll ans = 0;
rep(i,n){
if(id[i].size() >=2){
ll t = 0;
rep(j,id[i].size()-1){
t=id[i][j+1]-id[i][j]-1;
ans += t*(id[i].size()-j-1)*(j+1);
}
dbg(ans);
}
}
print(ans);
return 0;
}
コメント