道筋が光って見えた男の備忘録です
コンテスト概要
東京海上日動プログラミングコンテスト2025（AtCoder Beginner Contest 402)
開催日:2025年4月19日 21:00-22:40
A - CBC
考察
大文字だけをより分ければOK。久々に単純でうれしい。
A-Zは65‐90,a-zは97-122の数値が割り当てられているので、90以下かどうかで振り分ける。
提出
#include <bits/stdc++.h>
using namespace std;
int main(){
string s;
cin >> s;
//全ての文字を見る
for(auto x:s){
//文字が90以下なら出力
if(x < 91) cout << x;
}
cout << endl;
}
B - Restaurant Queue
考察
タイトルからQueueを使えという圧かすごいのでおとなしく使おう。
クエリ１の時queueに食券番号を追加して、クエリ２の時queueの先頭を出力してpop。
分かりやすい練習問題かも。
提出
#include <bits/stdc++.h>
using namespace std;
int main(){
queue<int>que;
int n;
cin >> n;
for(int i=0;i<n;i++){
int q;
cin >> q;
if(q == 1){
//クエリ１ならqueueに追加
int x;
cin >> x;
que.push(x);
}else{
//クエリ２なら先頭を出してpop
cout << que.front() << endl;
que.pop();
}
}
}
C - Dislike Foods
考察
最近のC問題読解力が求められて困る。かみ砕ければ簡単なんですが...
要するに苦手をつぶし切ったときにカウンターを上げればよさそう。
なのでまず「素材が使われている料理のリスト」と「料理ごとの現在の苦手素材数」を用意する。そして、素材を克服したときにその素材を使った料理の苦手素材数を1減らす。この時苦手素材数が０になったらカウンターを上げる。
TLEに関して不安だが、素材を減らす回数はKの数と同じなので心配はない。
提出
using namespace std;
int main(){
int n,m;
cin >> n >> m;
vector<set<int>>fd (n);//素材ごとの使われてる料理リスト
vector<int>num (m);//料理ごとの現在の苦手素材数
for(int i=0;i<m;i++){
cin >> num[i];
for(int j=0;j<num[i];j++){
int x;
cin >> x;
x--;
fd[x].insert(i);
}
}
int ans = 0;
for(int i=0;i<n;i++){
int x;
cin >> x;
x--;
//素材ごとに料理を少し克服する
for(auto y:fd[x]){
num[y]--;
if(num[y] == 0) ans++;//苦手が０になったらカウンターを増やす
}
cout << ans << endl;
}
}
D - Line Crossing
考察
数学×円＝目を背けたい問題。
全ての直線の組から、平行のものを除けばいい。といえば簡単だが平行同士の管理が難問。
いろいろこねくり回してたら突如ひらめきが降ってきた。
まず頂点数を2倍にして頂点番号も2倍する。そうすると2点の平均が整数値で表せる。それをmodNで管理すればOK。
...なんだこの解法？コンテスト後に考えたのだが、これは要するに直線ごとの対称軸を探していることになる。
あとは、各対称軸ごとの組み合わせを出してフィニッシュ。
ちょっとしたエスパーでAC。
提出
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
ll n,m;
cin >> n >> m;
//(i,i+n)を対称軸とする直線の個数を管理
vector<ll>pr (n,0);
for(int i=0;i<m;i++){
int x,y;
cin >> x >> y;
//値を0はじめかつ2倍に
x = (x-1)*2,y = (y-1)*2;
//対称軸を求める
int s = (x+y)/2;
if(s >= n) s -= n;
pr[s]++;
}
//直線の全組み合わせを出す。
ll ans = m*(m+1)/2LL;
for(auto x:pr){
//平行の組み合わせを引く
ans -= x*(x+1)/2LL;
}
cout << ans << endl;
}
E - Payment Required
考察
確率は勉強します。はい。
F - Path to Integer
考察
残り時間をすべて捧げた問題。
正直に値をつなげてmodを出すのはいろいろとダメそう。ここでいろいろと実験すると各マスごとに使われる桁は決まっていることがわかる。具体的にはあらかじめ$10^{2N-i-j}$倍してよさそう。そうとなれば足し算で事足りるように。
後はどのようにしてmodを出すかだが普通にやるとルートは$\binom{2n-2}{n-1}$なので40では明らかにTLE。
ここでもう一度ひらめきが降ってくる。
半分に分割すればそれぞれ$2^{N}$で済むのでは？中央で合流させれば少し計算量を減らせそう！
というわけでBFSで全探査しちゃうぞ！あとは全通り試してTLE。なんで？
よくよく考えたら上側、下側それぞれ$2^N$通りあるので全通りチェックするとそりゃTLEだよね。
なので二分探査で効率を上げてAC！
提出
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
//高速で累乗のmodを求める関数
ll fuc(ll n,ll mod){
ll now = 10,ans = 1;
while(n != 0){
if(n%2 == 1) ans *= now;
ans %= mod;
now *= now;
now %= mod;
n >>= 1;
}
return ans;
}
int main(){
ll n,m;
cin >> n >> m;
vector<vector<ll>>num (n,vector<ll>(n));
ll pw = (n-1)*2;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
ll x;
cin >> x;
//あらかじめデータを足し算にできるよう加工
num[i][j] = x*fuc(pw-i-j,m);
num[i][j] %= m;
}
}
vector<vector<ll>>upd (n,vector<ll>(0)),dwd (n,vector<ll>(0));
queue<pair<pair<int,int>,ll>>que;
que.push({{0,0},num[0][0]});
//まずは上側からBFS
while(!que.empty()){
auto [aaa,cst] = que.front();
auto [x,y] = aaa;
que.pop();
//中央に来たら打ち切り
if(x+y == n-1){
upd[x].push_back(cst);
continue;
}
//右もしくは下に移動(mod計算を忘れない)
ll sum = cst + num[x+1][y];
sum %= m;
que.push({{x+1,y},sum});
sum = cst + num[x][y+1];
sum %= m;
que.push({{x,y+1},sum});
}
que.push({{n-1,n-1},num[n-1][n-1]});
//今度は下側からBFS
while(!que.empty()){
auto[aaa,cst] = que.front();
auto[x,y] = aaa;
que.pop();
//中央に来たら打ち切り
if(x+y == n-1){
//二回中央の値を足してるので調整
cst = m + cst - num[x][y];
dwd[x].push_back(cst%m);
continue;
}
//左もしくは上に移動
ll sum = cst + num[x-1][y];
sum %= m;
que.push({{x-1,y},sum});
sum = cst + num[x][y-1];
sum %= m;
que.push({{x,y-1},sum});
}
ll ans = 0;
for(int i=0;i<n;i++){
sort(dwd[i].begin(),dwd[i].end());
//すべてのXについて最も大きな値になれるYを二分探査
for(auto x:upd[i]){
ll mx = m - x - 1;
int p = upper_bound(dwd[i].begin(),dwd[i].end(),mx) - dwd[i].begin();
ll a;
if(p != 0){
a = x + dwd[i][p-1];
}else{
a = dwd[i].back();
a = (a+x)%m;
}
//答えを更新
ans = max(ans,a);
}
}
cout << ans << endl;
}
結果
ABCDF(2) 5完 105:33
順位 832位
パフォーマンス 1614
感想
ひらめきが冴えわたる調子のいい回だった。
あとは確率ができれば更なる高みに行けたが、まぁ上出来ということで。
運ではなく実力で進めるようにできれば青は近い