脳がオーバーヒートした男の備忘録です
コンテスト概要
ユニークビジョンプログラミングコンテスト2025 秋（AtCoder Beginner Contest 425
https://atcoder.jp/contests/abc425
開催日:2025年9月27日 21:00-22:40
A - Sigma Cubes
考察
ここまで工夫のしようがない問題もないよね。
言われた通りに$(-1)^i\times i^3$をコツコツ足していくだけ。
累乗はpow関数を使えば万事解決。
知らなくても$i\times i\times i$でごり押せばいい。
提出
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
cin >> n;
int sum = 0;
for(int i=1;i<=n;i++){
//奇数番目は引く、偶数番目は足す。
if(i%2 == 0) sum += pow(i,3);
else sum -= pow(i,3);
}
cout << sum << endl;
}
B - Find Permutation 2
考察
出力したい数列は1からNを1つずつ使ったもの。なので与えられた時点で同じ数字を2回使っているなら目標は達成できない。
裏を返せば、それ以外は達成可能。
達成可能なのを前提としてどうやって数列を作るか。答えはシンプル。使ってないものを前からおいていけばいい。
数字を1回ずつ使いさえすればいいので何も考えずおいていこう。
こんなにシンプルな問題なのに15分もかかった。ほんとになんで？
提出
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
cin >> n;
vector<bool>num (n,false);//使ったことある数字リスト
vector<int>ans (n);//答えの列
string str = "Yes";
for(int i=0;i<n;i++){
int x;
cin >> x;
ans[i] = x;
if(x == -1) continue;
if(num[x-1]){
//数字を2回使っちゃったら達成不可
str = "No";
}
num[x-1] = true;
}
queue<int>que;
for(int i=0;i<n;i++){
//使ったことのない数字を列挙
if(!num[i]) que.push(i+1);
}
cout << str << endl;
if(str == "No") return 0;
int now = 0;
for(int i=0;i<n;i++){
if(ans[i] != -1){
//使う数字が決まっているならそれ
cout << ans[i] << endl;
}else{
//決まってないなら未使用を前から
cout << que.front() << endl;
que.pop();
}
}
}
C - Rotate and Sum Query
考察
350点問題ってめっちゃめんどくさいか、拍子抜けするほど簡単かの二極化してるよね。
今回は拍子抜け。
まず、数字を移動させるというクエリを無視した場合、ただの累積和だけで事足りる。
問題は数列を移動させる必要があるということ。
もちろん、毎回数字を後ろに動かしてしまうと到底時間が足りない。
こういう時は動かしたふりをすると上手くいく。
今、先頭がどこかのを管理する値hを持っておく。当然最初は0。
その後c回移動させたなら先頭は(h+c)番目ということにしておけばいい。
このままだとhが際限なく大きくなるので適宜余りを取っておく。
ここまでできれば(l+h)番目から(r+h)番目までの累積和を見ればOK。
範囲外を参照しないように累積和を2倍まで作っておけば安心。
提出
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
int n,q;
cin >> n >> q;
vector<ll>sum (2*n+1,0);//2倍の長さの累積和。
for(int i=0;i<n;i++){
ll x;
cin >> x;
//1週目と2週目の二か所に足しておく。
sum[i+1] = sum[n+i+1] = x;
}
for(int i=0;i<2*n;i++){
sum[i+1] += sum[i];
}
int h = 0;//先頭を管理する変数。
for(int rp = 0;rp<q;rp++){
int x;
cin >> x;
if(x == 1){
ll c;
cin >> c;
//先頭をc個ずらす。
h += c;
h %= n;
}
if(x == 2){
int l,r;
cin >> l >> r;
//ずれた先頭を考慮した範囲に直す。
l += h-1,r += h;
cout << sum[r] - sum[l] << endl;
}
}
}
D - Ulam-Warburton Automaton
考察
なんかフワフワしてて雑なコードだと思う。
$10^{100}$回とか仰々しい数が出ているが、要するに変化がなくなるまで動かすといってるだけ。
白マスが黒マスになれるチャンスは隣接が1つ黒になるときだけ。
黒が白になることはないので黒が2マス以上になった段階でその白マスが黒になることは永遠にない。
なのですべての白マスはチャンスが来た時だけ見ればいい。
では、いつチャンスが訪れたことにするのか？それは新たに黒マスができたとき、その隣接の白マスにチャンスが訪れる。
初めてチャンスが来た時だけ見ればいいので白マスを2回チェックなんてこともない。
というわけで黒マスを起点としてBFSをして、周りの黒マスの数を数えて色を変えればいい。
グリッドって実装めんどい。
提出
#include <bits/stdc++.h>
using namespace std;
int main(){
int h,w;
cin >> h >> w;
ll inf = 1e6;
//周囲をダミーで囲う
//それぞれのマスで黒になるタイミングを管理。
vector<vector<int>>mp (h+2,vector<int>(w+2,inf));
for(int i=1;i<=h;i++){
for(int j=1;j<=w;j++){
char x;
cin >> x;
if(x == '#'){
mp[i][j] = 0;
}
}
}
queue<pair<int,int>>que;
for(int i=1;i<=h;i++){
for(int j=1;j<=w;j++){
if(mp[i][j] == 0){
//黒マスの周りの白マスをキューに入れる。
for(int k=-1;k<2;k+=2){
if(mp[i+k][j] != 0){
que.push({i+k,j});
mp[i+k][j] = 1;
}
if(mp[i][j+k] != 0){
que.push({i,j+k});
mp[i][j+k] = 1;
}
}
}
}
}
while(!que.empty()){
auto [x,y] = que.front();
que.pop();
//範囲外は無視。
if(x==0 || x == h+1 || y == 0 || y == w+1){
mp[x][y] = inf+1;
continue;
}
int cnt = 0;
for(int i=-1;i<2;i+=2){
//黒になるタイミングが自分より早いものをカウント
if(mp[x+i][y] < mp[x][y]) cnt++;
if(mp[x][y+i] < mp[x][y]) cnt++;
}
//黒が2マス以上なら永劫白
if(cnt != 1){
mp[x][y] = inf+1;
continue;
}
//ここまでくれば晴れて黒マス
//周りにチャンスを与える。
for(int i=-1;i<2;i+=2){
if(mp[x+i][y] == inf){
que.push({x+i,y});
mp[x+i][y] = mp[x][y] + 1;
}
if(mp[x][y+i] == inf){
que.push({x,y+i});
mp[x][y+i] = mp[x][y] + 1;
}
}
}
int ans = 0;
//黒マスを丁寧に数える。
for(int i=1;i<=h;i++){
for(int j=1;j<=w;j++){
if(-1 < mp[i][j] && mp[i][j] < inf) ans++;;
}
}
cout << ans << endl;
}
E - Count Sequences 2
考察
ちゃんと理解をしていないと罠にかかる問題。
数列{a,b,c,d}が与えられたとき、前から順番に数字を置いていく。
a個の1を置く方法は当然1通り。あえて書くなら$\frac{a!}{a!\times0!}$になる。
次にそこにb個の2を置く方法は合計(a+b)個のものを並べるわけだから、$\frac{(a+b)!}{a!\times b!}$通り。
続けて$\frac{(a+b+c)!}{(a+b)!\times c!}$通り、$\frac{(a+b+c+d)!}{(a+b+c)!\times d!}$通りになる。
求める値はこれを全部掛け合わせるので、
$\frac{a!}{a!} \times \frac{(a+b)!}{a!\times b!} \times \frac{(a+b+c)!}{(a+b)!\times c!} \times \frac{(a+b+c+d)!}{(a+b+c)!\times d!} = \frac{(a+b+c+d)!}{a!\times b!\times c!\times d!}$
と思ったより簡単な式になる。
後はモジュラ逆数をフェルマーの小定理とかで求めてしまえばおしまい。
....
というのが、罠である
モジュラ逆数は「modと互いにその時しか使えない」のである。
よって例えばMが8のとき、1/16とか1/80とかを求められない。
上手く回避する必要がある。
ここで与えられる値が高々5000であることを利用する。
5000!を素因数分解したところで5000以下の素数しか出てこない。669個しかない。
ということは1~5000の階乗についてすべての素因数の数を持っていても余裕があるのではないか？
というわけで1~5000までにおいて階乗が素因数をいくつ持つのかをすべて保持しておく。
後は上手く約分できれば自然数の掛け算だけに持ち込める。
なんとなくモジュラ逆数を使ってませんか？という警鐘を投げかける問題だった。
提出
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<ll>pri;
//素数を列挙するやつ
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;
}
ll mod = 998244353ll;
//a^bを高速で計算するやつ
ll rec(ll a,ll b,ll mod){
ll ans = 1;
while(b != 0){
if((b&1LL)) ans *= a;
ans %= mod;
a *= a;
a %= mod;
b >>= 1;
}
return ans;
}
int main(){
rrp(5000);
int siz = pri.size();
//階乗の素因数を求める
vector<vector<ll>>sum (5001,vector<ll>(siz,0));
for(int i=0;i<siz;i++){
ll p = pri[i];
while(p < 5000){
for(int j=1;j*p<=5000;j++) sum[j*p][i]++;
p *= pri[i];
}
}
//累積和の感覚で全部足す。
for(int i=0;i<5000;i++){
for(int j=0;j<siz;j++){
sum[i+1][j] += sum[i][j];
}
}
ll t,mod;
cin >> t >> mod;
for(int rp = 0;rp<t;rp++){
int n;
cin >> n;
ll c = 0;
vector<int>num (n);
for(int i=0;i<n;i++){
cin >> num[i];
c += num[i];
}
//分子は和の階乗
vector<ll>che = sum[c];
//個数を引けば約数になる。
for(int i = 0;i<n;i++){
int d = num[i];
for(int j=0;j<siz;j++){
che[j] -= sum[d][j];
}
}
ll ans = 1;
//あとはシンプル掛け算
for(int i=0;i<siz;i++){
ans *= rec(pri[i],che[i],mod);
ans %= mod;
}
cout << ans << endl;
}
}
結果
ABCDE 5完 76:44
順位 1189位
パフォーマンス 1422
レート 1351(+8)
感想
何でB問題でフリーズしちゃったんだろう？
なんかうまくかみ合わずパフォを伸ばせずにいる。
でもまあ、苦手を潰す努力はしているので機を待つしかないか。