この名前は既に使われていた男の備忘録です
コンテスト概要
日本最強プログラマー学生選手権～Advance～ -予選- （AtCoder Beginner Contest 412）
開催日:2025年6月28日 21:00-22:40
A - Task Failed Successfully
考察
A問題で区間スケジュール問題!?!?って思ったけど全然そんなことなかった。
Bのほうが多い日の個数を数えればOK。
「以上」じゃなくて「より多い」であることに注意。
提出
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
cin >> n;
int ans = 0;//カウンター
for(int i=0;i<n;i++){
int x,y;
cin >> x >> y;
if(y > x) ans++;//後者のほうが多いならカウント＋１
}
cout << ans << endl;
}
B - Precondition
考察
なんかごちゃごちゃしているが大事なのは、
「文字列Sの大文字の前にある文字は、文字列Tにすべて含まれてますか？」
ということ。先頭がどうのこうのというのは「先頭より前の文字はないから気を付けてね」ってだけ。
なので、
まず大文字の前の文字をすべて拾う。
↓
拾った文字がTにあるかを丁寧に調べる。
↓
全部あればYes、そうでなければNo。
を順番に実装すればおしまい。
提出
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
string s,t;
cin >> s >> t;
int len = s.length();
vector<char>che (0);//大文字の前の文字を格納
for(int i=1;i<len;i++){//先頭より前に文字はないのでi=0の時は飛ばす
if(s[i] <= 'Z') che.push_back(s[i-1]);
//i番目の文字が大文字なら(i-1)番目の文字を拾う
//文字は大文字、小文字の順で数字がついているので
//Z以下で大文字を網羅。
}
string ans = "Yes";
for(auto x:che){//文字を一つずつチェック
bool c = false;
for(auto y:t){
if(y == x) c = true;//文字が使われているならOK
}
if(!c) ans = "No";//一つでも使われてないならNo。
}
cout << ans << endl;
}
C - Giant Domino
考察
ちょっと骨のあるC問題。落ち着いて対処したい。
次のドミノについて、今の大きさがnの時2n以下の大きさのドミノならどれを使ってもいい。じゃあどれを使おうか？
答えは最小値が求められている。ならちまちま並べるよりデカいのをバンバン並べるほうが効率がいいに決まっている。なのでそれぞれのドミノごとにできるだけデカいドミノを選んでいく。
要するに、
スタートのドミノの大きさの２倍以下で最大のドミノを探す。
↓
ドミノを置きそのドミノの２倍以下で最大のドミノを探す。
↓
これを繰り返す。
↓
あるドミノの２倍がゴールのドミノより大きくなったらストップ
↓
置いたドミノを数える
の順で処理すればいい。
最大のドミノを毎回探すと大変なのでupper_boundとか良い関数を使おう。
提出
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
int q;
cin >> q;
for(int i=0;i<q;i++){
int n;
cin >> n;
ll f,b;//スタートとゴールを管理
set<ll>st;
for(int i=0;i<n;i++){
if(i == 0) cin >> f;
else if(i == n-1) cin >> b;
else {//スタート、ゴール以外は小さい順になる袋に入れる
ll x;
cin >> x;
st.insert(x);
}
}
int ans = 1;
st.insert(f);//検索用にスタートのドミノを入れておく
while(f*2LL < b){//今のドミノの2倍がゴールのドミノ未満である限り続ける。
ans++;
ll c = *prev(st.upper_bound(f*2LL));
//ドミノの大きさ２倍以下で最大のものを返す。
//upper_boundで２倍「より大きい」最小のものを検索。
//prevでその１つ前を出力
if(f == c){
//最大が今のドミノならもう置けるものがないので無理。
ans = -2;//最後に1を足して出力するので調整のため-2
break;
}
f = c;
}
cout << ans + 1 << endl;
//ゴールのドミノを置いて終了。
}
}
D - Make 2-Regular Graph
考察
Nが8。十中八九、順列全探査だね。
グラフの頂点がすべて2なのはどんな時だろうか？
1と2をつなぎ、2と3をつなぎ、3と1をつなぐ。こうすれば頂点がすべて2になる。
つまりは、グラフが無駄のない輪になるときが条件を満たす。
というわけで順列全探査で実装できそうですね。
例えば$[1,2,...,n]$の並び替え$[P_1,P_2,...,P_n]$について
$P_1$と$P_2$を結ぶ。$P_2$と$P_3$を結ぶ。...$P_n$と$P_1$を結ぶ。
これで出来上がったグラフと元のグラフを見比べて不要・必要な辺の数を数えればいい。
ただし、この問題トラップが1つある。
誰もこのグラフが連結であるとは言っていないのである。
というわけで例えば8頂点の場合[3頂点のサイクル][5頂点のサイクル]と[4頂点のサイクル][4頂点のサイクル]の分割したパターンも考えなければならない。
順列全探査をしつつ、大きいnの時に分割も考慮すればOK。
なんでトラップ回避しておきながら名前つけ間違えて40分ロスしてるんですか？
反省してください。
提出
#include <bits/stdc++.h>
using namespace std;
int main(){
int n,m;
cin >> n >> m;
vector<vector<int>>path (n,vector<int>(n,0));
//元のグラフを二次元配列で管理
//結んでいたら１、そうでなければ０
for(int i=0;i<m;i++){
int x,y;
cin >> x >> y;
x--,y--;
path[x][y]=1;
path[y][x]=1;
}
vector<int>num (n);
for(int i=0;i<n;i++) num[i] = i;//順列の準備
int ans = 100;//仮置きで大きい数字
do{
//まずは大きい1つの輪を考える
vector<vector<int>>che (n,vector<int>(n,0));
for(int i=0;i<n;i++) che[num[i]][num[(i+1)%n]] = 1,che[num[(i+1)%n]][num[i]] = 1;
//順列の隣どうしを結んでみる。
int cnt = 0;
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
if(path[i][j] != che[i][j]) cnt++;
//元のグラフと辺が一致しないならカウンー＋１
}
}
ans = min(ans,cnt);
//頂点を[3つ][3つ以上]に分ける
if(n-3 > 2){
vector<vector<int>>ch (n,vector<int>(n,0));
vector<vector<int>>vec (2,vector<int>(0));
for(int i=0;i<3;i++) vec[0].push_back(num[i]);
for(int i=3;i<n;i++) vec[1].push_back(num[i]);
//とりあえず順列を分割
for(auto x:vec){
int s = x.size();
for(int i=0;i<s;i++) ch[x[i]][x[(i+1)%s]] = 1,ch[x[(i+1)%s]][x[i]] = 1;
}
//それぞれのグラフごとに結んでみる。
cnt = 0;
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
if(path[i][j] != ch[i][j]) cnt++;
//元のグラフと辺が一致しないならカウンー＋１
}
}
ans = min(ans,cnt);
}
//頂点を[4つ][3つ以上]に分ける
if(n-4 > 2){
vector<vector<int>>ch (n,vector<int>(n,0));
vector<vector<int>>vec (2,vector<int>(0));
for(int i=0;i<4;i++) vec[0].push_back(num[i]);
for(int i=4;i<n;i++) vec[1].push_back(num[i]);
//とりあえず順列を分割
for(auto x:vec){
int s = x.size();
for(int i=0;i<s;i++) ch[x[i]][x[(i+1)%s]] = 1,ch[x[(i+1)%s]][x[i]] = 1;
}
//それぞれのグラフごとに結んでみる。
cnt = 0;
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
if(path[i][j] != ch[i][j]) cnt++;
//元のグラフと辺が一致しないならカウンー＋１
}
}
ans = min(ans,cnt);
}
}while(next_permutation(num.begin(),num.end()));
//すべての順列を試す。
cout << ans << endl;
}
E - LCM Sequence
考察
数学一本勝負。悪くないね。
数が変化するのはどんなときかをまず考えたい。
まずはテストケースを観察。
- $A_4 = 12$
- $A_5 = 60$
- $A_6 = 60$
- $A_7 = 420$
- $A_8 = 840$
- $A_9 = 2520$
- $A_{10} = 2520$
- $A_{11} = 27720$
- $A_{12} = 27720$
少なくとも素数の時に値が増えてそう。でも8番目9番目でも増えている。
これらの共通点は？そう素因数が1つだけ！
言い換えれば$(素数)^n$の時に値が増える。まあそれ以外の時小さい数で代用できそうだもんね。
正確に証明はできてないけど方針は決まった。
$A_L$は必ず含まれるのでカウント
↓
$(L+1) \leqq N \leqq R$のうち$(素数)^k$のものをカウント
でOK。
後は高速に求める方法だがエラトステネスの篩かなんかであらかじめ素数表を作っておけば短時間で済む。
提出
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<ll>pri;
//素数作るやつ
void rpp(){
int d = 1e7;
vector<bool>num (d,false);
pri.resize(0);
for(ll i=2;i<d;i++){
if(num[i]) continue;
pri.push_back(i);
for(ll j=2;i*j<d;j++) num[i*j] = true;
}
}
int main(){
rpp();
ll x,y;
cin >> x >> y;
x++;
vector<int>num (y-x+1,0);//素因数の数を数えるやつ
vector<bool>che (y-x+1,false);//素因数が1つだけか確かめるやつ
for(auto p:pri){
ll b = (x-1LL)/p + 1LL,e = y/p;
for(ll i = b;i <= e;i++){
ll s = i*p;
num[s-x]++;
}
//素因数にチェックを付ける
//TLEになりそうだが調和級数なので実は間に合う。
ll q = 1;
while(true){
if(y/q < p)break;
q*=p;
if(q <= y && x <= q) che[q-x] = true;
}
//素因数をかけていく
//TLEになりそうだが2ですら高々50回しか計算しないので間に合う
}
ll ans = 1;
//最初はどうやってもカウント
for(int i=0;i < y-x+1;i++){
if(num[i] == 0 || che[i]) ans++;
//num[i]==0 10^7より大きい素数。
//che[i] = true 10^7以下の素数の1つだけが素因数
}
cout << ans << endl;
}
結果
ABCDE 5完 97:20
順位 809位
パフォーマンス 1645
レート 1354(+37)
感想
解けば解くだけ順位が上がる回は良いですね。こういうのもっとちょうだい。
まぁ気を抜くと冷えるので引き締めていきまっしょい。