全完の夢を見た男の備忘録です
コンテスト概要
デンソークリエイトプログラミングコンテスト2025（AtCoder Beginner Contest 413）
開催日:2025年7月5日 21:00-22:40
A - Content Too Large
考察
こういうシンプルなA問題、好き。
シンプルに総和を取って比べればOK。
ただ、別途値を用意するのが面倒だったので愚直にmから引き足が出ていないかをチェック。
提出
#include <bits/stdc++.h>
using namespace std;
int main(){
int n,m;
cin >> n >> m;
for(int i=0;i<n;i++){
int x;
cin >> x;
m -= x;//残り容量を埋めていく
}
if(m < 0) cout << "No" << endl; //残り容量が負なら入りきっていない。
else cout << "Yes" << endl;
}
B - cat 2
考察
こういうごり押しのB問題、好き。
全部のパターンですら9900通りしかないので全て試す。
重複に関してだがsetを使えば勝手に重複を排除してくれる。
というわけで全探査してsetのサイズを出せば終わり。
提出
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
cin >> n;
vector<string>str (n);
for(int i=0;i<n;i++) cin >> str[i];
set<string>ans;
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
//どちらを前にするかは、両方試す。
string s = str[i] + str[j], t = str[j] + str[i];
ans.insert(s),ans.insert(t);//setに挿入して管理
}
}
cout << ans.size() << endl;
//重複は排除されてるので要素数がそのまま答え
}
C - Large Queue
考察
愚直にやるとTLEするやつを改善するC問題、好き。
とりあえずタイトルでも"Queue"と言っているのでqueueを使えば何とかなりそう。
だが、愚直にやろうとするとデータを最大$2\times 10^{14}$個管理しなくてはいけないので到底間に合わない。
なのでうまく情報を「圧縮」しながら管理していく。
C個のXを[x,c]と書くように値と個数の2つの変数で管理する。
そうすれば持つべきデータは最大でも$4\times 10^5$個と何とかなりそうな数字に収まる。
後はクエリごとに必要な個数を引き出せばOK。
提出
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
int n;
cin >> n;
queue<pair<ll,ll>>que;//値と個数を管理するqueue
for(int i=0;i<n;i++){
int x;
cin >> x;
if(x == 1){
ll s,t;
cin >> s >> t;
que.push({t,s});
//{値、個数}に情報を圧縮してqueueに入れる
}
if(x == 2){
ll k;
cin >> k;
ll ans = 0;
while(k != 0){//数をk個取り出すまで繰り返す
if(que.front().second > k){//の値の個先頭個数kより大きいとき
que.front().second -= k;//値をk個だけ抜き取る
ans += que.front().first * k;//抜き取った値を足す
k = 0;//k個全部抜き出しました。
}else{//先頭がk個以下の時
ans += que.front().first * que.front().second;
//先頭の値はすべて噴き出す必要があるので全部足す。
k -= que.front().second;
//残りの数を減らしておく
que.pop();
//用済みの情報は捨てる。
}
}
cout << ans << endl;
}
}
}
D - Make Geometric Sequence
考察
シンプルな数学考察D問題、嫌い。
正直、正の値と負の値が混ざっているのが厄介。
ここで公比が-2と2の数列を考えると、
公比 2: 1, 2, 4, 8, 16, 32...
公比-2: 1,-2, 4,-8, 16,-32...
と絶対値が同じでただ「符号が同じ」か「交互になっている」かしか違いがない。
というわけで、とりあえず符号は後で考えるとして、すべての値を正として考える。
今度は公比が2と$\frac{1}{2}$の数列を考える。
公比 2: 1, 2, 4, 8, 16, 32...
公比1/2: 32, 16, 8, 4, 2, 1...
とちょうど逆になっている。要するに公比の逆数は元の数列の真逆になることがわかる。
というわけで値を昇順にしてしまっても問題がない。
そして等比数列の判断は等比数列が
$A_{i-1}\times A_{i+1} = {A_i}^2$
を満たすことを利用すればいい。
ここまでくれば方針がはっきりとする。
〇値をすべてに絶対値をとる。
↓
〇数列をソートし昇順にする。
↓
〇数列が等比数列かの確認
↓
〇数列が「符号が同じ」もしくは「符号が交互」のどちらかになっているかの確認
これを順にやっていけばOK。
まあ最後が面倒くさいんですけどね。
提出
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
int n;
cin >> n;
for(int i=0;i<n;i++){
int t;
cin >> t;
vector<ll>mn (0),pn (0);
//符号が正のもの、負のものの2つを管理
for(int i=0;i<t;i++){
ll x;
cin >> x;
if(x < 0) mn.push_back(-x);
else pn.push_back(x);
}
sort(mn.begin(),mn.end()),sort(pn.begin(),pn.end());
//数列を昇順にしておく
string ans = "Yes";
if(mn.size() == 0){//全部が正の数の場合
for(int j=1;j<t-1;j++){
if(pn[j-1]*pn[j+1] != pn[j]*pn[j]) ans = "No";
}
//シンプルな等差数列の判定のみ
}else if(pn.size() == 0){//全部が負の数の場合
for(int j=1;j<t-1;j++){
if(mn[j-1]*mn[j+1] != mn[j]*mn[j]) ans = "No";
}
//シンプルな等差数列の判定のみ
}else{//それ以外の場合
ll p = pn.size(),m = mn.size();
if(abs(p-m) > 1)ans = "No";//交互に来ないといけないので差が2以上は論外
else if(p-m == 1 && pn[0] > mn[0])ans = "No";//差が１の時は多いほうが最小でなければ論外。
else if(m-p == 1 && mn[0] > pn[0])ans = "No";
else{
//ここでは正の値と負の値を交互に並べる
//その後それが等比数列化を確認。
if(pn[0] > mn[0]){
for(int j=1;j<m;j++){
if(j >= p)break;
if(pn[j-1]*pn[j] != mn[j]*mn[j]) ans = "No";
}
for(int j=0;j<p;j++){
if(j+1 >= m)break;
if(mn[j]*mn[j+1] != pn[j]*pn[j]) ans = "No";
}
}else{
for(int j=1;j<p;j++){
if(j >= m) break;
if(mn[j-1]*mn[j] != pn[j]*pn[j]) ans = "No";
}
for(int j=0;j<m;j++){
if(j+1 >= p)break;
if(pn[j]*pn[j+1] != mn[j]*mn[j]) ans = "No";
}
}
}
}
cout << ans << endl;
}
}
E - Reverse 2^i
考察
問題の設定からセグメントツリーっぽいものを使うことを推奨されていそう。
そして問題文がごちゃついてわかりずらいが要するに
この図の赤いところの数列だけひっくりかえせますよ。と言っている。
この時一番上をひっくり返したとする。すると
こうなる。下にある箱の要素が入れ替わるだけで前半と後半は交ざることはない。
なので、一番上から左右のうち小さいほうがあるものを優先的に処理していけばOK。
提出
#include <bits/stdc++.h>
using namespace std;
template <typename T>
struct ST_MIN{//セグメントツリーで管理
vector<T>num;
int siz;
T inf;
ST_MIN(int n){//セグ木を構築
int x = 1;
while(n > x) x <<= 1;
siz = x;
inf = numeric_limits<T>::max();
num = vector<T> ((x<<1),inf);
}
void Update(int x,T i){//値を入れていく
x = x + siz - 1;
num[x] = i;
while(x != 0){//最小のものを更新していく
x = (x-1)/2;
num[x] = min(num[x*2 + 1],num[x*2 + 2]);
}
}
void Sub_Serch(int n){//上から順番に処理
if(n >= siz - 1){//最後まで行ったら出力
if(num[n] != 1)cout << " ";
cout << num[n];
return;
}
n *= 2;
if(num[n+1] > num[n+2]){//より小さいほうから処理
Sub_Serch(n+2);
Sub_Serch(n+1);
}else{
Sub_Serch(n+1);
Sub_Serch(n+2);
}
return;
}
void Serch(){
Sub_Serch(0);
return;
}
};
int main(){
int t;
cin >> t;
for(int i=0;i<t;i++){
int n;
cin >> n;
int m = (1<<n);//全部で2^n個のデータ
ST_MIN<int>tree(m);
for(int i=0;i<m;i++){
int x;
cin >> x;
tree.Update(i,x);
}
tree.Serch();
cout << endl;
}
}
F - No Passage
考察
メモも疲れてきたので手短に。
まずはゴールできない時を考える。
ゴールへの道筋が1つしかないとき青木君はそこをふさげば高橋君はなすすべ無し。
逆に2つあれば塞がれなかったほうに向かえばゴールはできる。
というわけですべてのマスに対してルートが2パターン以上存在するかを確かめる。
では2パターン以上あるとき青木君はどう行動するか？
もちろん最短ルートを塞いでくる。なので、高橋君は2番目に短いルートを通る。
これを実装できればいい。
まぁゴールからのBFSが無難じゃないかな？
提出
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll inf = (1<<30);
int main(){
int h,w,k;
cin >> h >> w >> k;
vector<vector<ll>>mp (h+2,vector<ll>(w+2,inf));
//考えやすいように枠外にダミーを設ける。
queue<pair<int,int>>que;
for(int i=0;i<k;i++){
int x,y;
cin >> x >> y;
mp[x][y] = 0LL;//ゴールは0手
for(int j=-1;j<2;j+=2){
//上下左右は候補地(枠外注意)
if(j+x != 0 && j+x != h+1) que.push({j+x,y});
if(j+y != 0 && j+y != w+1) que.push({x,j+y});
}
}
while(!que.empty()){
auto [x,y] = que.front();
que.pop();
vector<ll>st (0);
for(int i=-1;i<2;i+=2){
st.push_back(mp[x+i][y]);
st.push_back(mp[x][y+i]);
}
sort(st.begin(),st.end());//上下左右のゴールまでの道のりを数える。
if(st[1] == inf) continue;//パターンが1つ以下なら負け
if(mp[x][y] <= st[1] + 1LL) continue;//すでにいい手があるならやり直し
mp[x][y] = st[1] + 1LL;//いい手に更新
for(int i=-1;i<2;i+=2){//まだ改善の余地がある上下左右を調べる。
if(i+x != 0 && i+x != h+1){
if(mp[x+i][y] > mp[x][y]) que.push({x+i,y});
}
if(i+y != 0 && i+y != w+1){
if(mp[x][y+i] > mp[x][y]) que.push({x,y+i});
}
}
}
ll ans = 0;
for(int i=1;i<=h;i++){
for(int j=1;j<=w;j++){
if(mp[i][j] == inf)continue;//負けなら足さない。
ans += mp[i][j];
}
}
cout << ans << endl;
}
G - Big Banned Grid
考察
障害物が盤面を分断したら行くことができない。なので障害物のつながりを高速に求められればよさそうですね。
10分じゃ無理っす。
結果
ABCD(1)EF 6完 94:40
順位 813位
パフォーマンス 1646
レート 1388(+33)
感想
ここまで余裕のある6完は初めて。うれしい。
そして時間があれば全完も可能だった。全完達成も見えてきた。うれしい。
いつか来る全完の夢へと頑張ります。