何も見えなくなった男の備忘録です
コンテスト概要
ミラティブ プログラミングコンテスト2025（AtCoder Beginner Contest 414
開催日:2025年7月12日 21:00-22:40
A - Streamer Takahashi
考察
視聴者全員に活動時間があるので、それぞれの活動時間中に配信が行われるのは何人か？ということ。
ifを使って簡便に
提出
#include <bits/stdc++.h>
using namespace std;
int main(){
int n,l,r;
cin >> n >> l >> r;
int ans = 0;
for(int i=0;i<n;i++){
int x,y;
cin >> x >> y;
if(x <= l && r <= y) ans++;
//配信時間が活動時間に完全に含まれるならカウントを増やす
}
cout << ans << endl;
}
B - String Too Long
考察
前回の復習って感じ。
とりあえず長さの制限を無視すれば、ポンポンqueueに入れて復元するだけ。
復元はforを使えば簡単。
あとは長すぎるときの判断をしたい。
シンプルに長さを足すとオーバーフローする。
なので
〇そもそも文字数が100を超えてたらX。
〇100以下なら足して、合計が100超えたらX
というように明らかにダメなやつをはじいておく。
提出
#include <bits/stdc++.h>
using namespace std;
int main(){
ll n;
cin >> n;
vector<pair<char,ll>>num (n);
bool che = false;
ll sum = 0;
for(int i=0;i<n;i++){
cin >> num[i].first >> num[i].second;
if(num[i].second > 100LL) che = true;//デカすぎるならはじく
else sum += num[i].second;//小さいものをチェック
}
if(sum > 100 || che) cout << "Too Long";//結局100を超えたらはじく
else{
for(int i=0;i<n;i++){
auto[c,x] = num[i];
for(int j=0;j<x;j++) cout << c;
//forを使って復元
}
}
cout << endl;
}
C - Palindromic in Both Bases
考察
ボロボロにされました。
とりあえず10進数の回文数を考える。前半分を決めれば後ろも決まる。なので$10^7$個試せばOK。
なので、回文数は最大でも$2\times10^7$個なので何とかなる。
後はそれら全部にA進数の時に回文になってるかを試せば...TLE。
これの時間短縮を頑張ったが60分が無駄に。
10進で$10^7$個、だったらA進数でも$10^7$個ぐらい。
後は簡単A進数でも全部確認すればよい。
さっさとやればよかったね。
(7/14追記)
とんでもない勘違いをしていました。
これ$10^7$じゃなくて$10^6$で十分です。
$10^6$なら回文になっているか試しても余裕で間に合います。
「1e7」を「1e6」に変えるだけでACできました。
提出
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
bool check(ll n,ll m){
string s = "";//A進数を文字列に変換
while(n != 0){
char x = '0' + (n%m);
s += x;
n /= m;
}
string t = s;
reverse(s.begin(),s.end());//片方をひっくり返す
if(s == t) return true;//同じかを判定。
return false;
}
int main(){
ll a,n;
cin >> a >> n;
set<ll> st;
ll lim = 1e6;//最大値は10^6乗で十分。
for(int i=1;i<lim;i++){
ll m = i;
vector<ll>num (0);//数字をそれぞれ受け取る。
while(m != 0){
num.push_back(m%10LL);
m /= 10LL;
}
ll x=i,y=i;
x *= 10LL;
x += num[0];
//ｘは完全な折り返し。yは中心が１つの回文
for(int j=1;j<num.size();j++){
x *= 10LL;
y *= 10LL;
x += num[j];
y += num[j];
}
if(check(x,a)) st.insert(x);
if(check(y,a)) st.insert(y);
}
ll ans = 0;
//setで管理しているがそもそもその場で確認したほうがスマート。
for(auto x:st){
if(x > n) break;
ans += x;
}
cout << ans << endl;
}
コンテスト中に提出したごちゃごちゃしたほう
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
ll a,n;
cin >> a >> n;
ll ans = 0;
map<ll,bool>mp;
ll lim = (1<<21);//2進数の最大を考えておく
//10進数の回文を求める。
for(int i=1;i<lim;i++){
ll m = i;
vector<ll>num (0);
while(m != 0){
num.push_back(m%10LL);
m /= 10LL;
}
//前半分を決めたら折り返しに注意して2パターン作る
ll x=i,y=i;
x *= 10LL;
x += num[0];
//値をどんどん後ろに追加
for(int j=1;j<num.size();j++){
x *= 10LL;
y *= 10LL;
x += num[j];
y += num[j];
}
//できたやつをmapに入れておく
if(x <= n) mp[x] = true;
if(y <= n) mp[y] = true;
}
//A進数でも同じようにやる
for(int i=1;i<lim;i++){
ll m = i;
vector<ll>num (0);
while(m != 0){
num.push_back(m%a);
m /= a;
}
//折り返しに注意して2パターン
ll x=i,y=i;
x *= a;
x += num[0];
//値をどんどん後ろに追加
for(int j=1;j<num.size();j++){
x *= a;
y *= a;
x += num[j];
y += num[j];
}
if(mp[x]) ans += x;
if(mp[y]) ans += y;
}
cout << ans << endl;
}
D - Transmission Mission
考察
一旦C問題を飛ばしてDをやる。
二分探査を考えるが上手くいかず、撤退。
ボロボロになりながらD問題にたどり着く。
よくよく考えたら近い家をまとめたほうがいい。
なので近くの家をどんどん併合すればおしまい。
5分でAC。冷静さが欲しい。
提出
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<typename T> using p_que = priority_queue <T,vector<T>,greater<T>>;
int main(){
ll n,m;
cin >> n >> m;
vector<ll> num (n);
for(int i=0;i<n;i++) cin >> num[i];
sort(num.begin(),num.end());//家を西から並べておく
p_que<ll>que;
for(int i=1;i<n;i++) que.push(num[i] - num[i-1]);//隣接する家ごとの距離を出す。
m = n-m;//足りない分だけ家を併合する。
ll ans = 0;
while(m != 0){
m--;
ans += que.top();
//家の距離を払い家同士を併合。
que.pop();
}
cout << ans << endl;
}
E - Count A%B=C
考察
残り2分。グデグデしながら考えたら解法が思いついて絶望。
一旦条件は無視。
とりあえずBを中心に考えると。すべてのAに対して1つのCが決まるので全部で$N^2$通りある。ここから条件を加味する。
B以下のAはA=Cになるので省く。
AがBで割り切れるとき、C=0なので省く。
この2つを考えればOK。
AがB以下になるのは$\frac{(N+1)\times N}{2}$個
c=0になるのは$\sum_{K=1}^N \lbrack \frac{N}{K} \rbrack$個(中身はガウス記号)
この二つを重複に気を付けて引けばよかったんですね。
提出
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll mod = 998244353LL;
int main(){
ll n;
cin >> n;
//n^2を計算
ll ans = n;
ans %= mod;
ans *= ans;
ans %= mod;
//1~Nまでの総和を計算。
ll sum = 0;
ll a = n,b = n+1LL;
if(a%2 == 0) a/=2LL;
else b/=2LL;
a %= mod,b %= mod;
sum = a*b;
sum %= mod;
ans = mod+ans-sum;
ans %= mod;
//N/Kの値を求める
ll now = 1LL;
while(n/now != 1){
ll x = n/now;
ll y = n/x +1LL;
x = (x-1LL)%mod;//かぶりを消すため1減らす。
ll z = (y-now) % mod;
now = y;
z *= x;
z %= mod;
ans = mod+ans - z;
ans %= mod;
}
cout << ans << endl;
}
結果
ABC(1)D(1) 4完 107:15
順位 3143位
パフォーマンス 979
レート 1353(-35)
感想
完全に冷静さを欠きました。
深呼吸すれば何とかなっただろうか？
今後は冷静に行きます。