久々に記事を書く男の備忘録です
コンテスト概要
AtCoder Beginner Contest 441 (Promotion of Engineer Guild Fes)
開催日:2026年1月17日 21:00-22:40
A - Black Square
考察
まさかA問題で$10^100$を見るとは思ってなかった。
要するに範囲内に指定されたマスがあるかないかを判定したい。
こういうのは基本的にX軸とY軸に分けて両方で範囲内化を確かめればいい。
例えばX軸については黒く塗られている範囲が P~P+99 の範囲にあればいい。
Pから100マス塗るとき、P+100は塗られないことに注意。
こういうの急いでるときほどミスりやすいから困る。
提出
#include <bits/stdc++.h>
using namespace std;
int main(){
int p,q,x,y;
cin >> p >> q >> x >> y;
//xが範囲内、かつyが範囲内かをチェック。
if(p <= x && x < p+100 && q <= y && y < q + 100) cout << "Yes" << endl;
else cout << "No" << endl;
}
B - Two Languages
考察
単語の文字数は高々$10^4$文字しかないので丁寧に見ても問題ない。
なので、単語がすべて高橋語の文字かを1文字ずつチェック。同様に青木語でも行う。
言ってしまえばこれをやるだけだが、ただ面倒。
まぁ美しく決めようとすればドツボにはまるので泥臭くやりましょう。
提出
#include <bits/stdc++.h>
using namespace std;
int main(){
int n,m;
cin >> n >> m;
//言語ごとに使われている文字をリストアップ。
vector<vector<bool>>check (2,vector<bool>(26));
//まず高橋語
for(int i=0;i<n;i++){
char x;
cin >> x;
//文字コードを利用して、aからの距離をインデックスに変換。
//使われているならtrueに
check[0][x - 'a'] = true;
}
//次に青木語
for(int i=0;i<m;i++){
char x;
cin >> x;
//文字コードを利用して、aからの距離をインデックスに変換。
//使われているならtrueに
check[1][x - 'a'] = true;
}
int q;
cin >> q;
for(int rp = 0;rp <q;rp++){
string str;
cin >> str;
//2言語を調べる。
//
vector<bool>ans (2,true);
for(int i=0;i<2;i++){
for(auto c:str){
//一文字でも使われない文字があったらその言語ではない。
if(!check[i][c- 'a']) ans[i] = false;
}
}
//両方trueなら判別不能、そうでなければtrueの言語
if(ans[0] && ans[1]) cout << "Unknown" << endl;
else if(ans[0]) cout << "Takahashi" << endl;
else cout << "Aoki" << endl;
}
}
C - Sake or Water
考察
考察一本勝負な問題。沼りやすいので心してかかる。
運が良ければ最初の1杯で達成できる可能性だってある。あらゆる可能性を考えるのはナンセンス。
なので、この手の問題は考えうる最悪のケースで考えると上手くいく。
では、今回の場合最悪のケースとは何か？もちろんそれはハズレを全部引いてしまうこと。
言い換えれば「最初に選んだ$N-K$個のコップがすべて水だった。」ということ。
確率的には低そうだが想定される以上ここを基準としなければならない。
ということで、最低でも$N-K$個を選ぶことは確定した。ではどういった戦略で飲むべきか？
もちろんそれは「多い順に飲む」に限る。
もし手当たり次第に飲んだ場合、一番量の多い酒1杯で事足りたはずがちびちびと飲んで最後の1杯で到達なんて場合が起こりえる。
どうせどれがアタリか分からない以上、とりあえずたくさん飲むに越したことはない。当たればラッキーだし。
というわけで方針が決まった。
- とりあえず多い順に飲む。
- 最初の$N-K$個は水と仮定する。
- $N-K+1$個めから加算してXml以上になるまで飲み続ける。
これを実装すればOK。
提出
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
ll n,k,x;
cin >> n >> k >> x;
vector<ll>num (n);
for(int i = 0;i<n;i++){
cin >> num[i];
}
//コップを多い順にソート
sort(num.begin(),num.end(),greater<ll>());
//最初のN-K杯はハズレってことにする。
ll ans = n-k,sum = 0;
while(ans < n){
//アタリを量の多い順に足していく。
sum += num[ans];
ans++;
//規定に達したらブレイク
if(sum >= x) break;
}
//そもそも最悪ケースの合計がXml未満の可能性あり。
if(sum < x) cout << -1 << endl;
else cout << ans << endl;
}
D - Paid Walk
考察
普通にDFSをすると最短経路しか求められないので、遠回りして目標達成っていう可能性なんかを潰してしまう。どうしたものか？
改めて制約を確認してみると、各頂点は最大でも4か所しか指さないことがわかる。
さらにターン数も10回ととても少ない。
これはかなりの弱点に違いない。あり得るパターン数を考えてみよう。
まず0ターン目は頂点1にいるだけなので1通り。
次のターンではそこから4方向に向かえるので4通り。
また次のターンではそれぞれから4方向に向かえるので4*4 = 16通り。
...とやっていくと10ターン目では$4^{10}\fallingdotseq 10^6$通りになる。
これはコンピューターにとって大分余裕のある数字。
というわけで、コンピューターのパワーを信じて全パターンを調べつくせばOK。
提出
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
ll n,m,l,s,t;
cin >> n >> m >> l >> s >> t;
//辺の向きと重さを管理
vector<vector<pair<int,ll>>>path (n,vector<pair<int,ll>>(0));
for(int i=0;i<m;i++){
ll x,y,c;
cin >> x >> y >> c;
x--,y--;
path[x].push_back({y,c});
}
vector<bool>ans (n,false);
queue<pair<int,pair<ll,ll>>> que;
//{今いる場所,{コストの和,現在のターン}}を管理。
que.push({0,{0,0}});
while(!que.empty()){
auto [pos,aaa] = que.front();
auto [cst,tim] = aaa;
que.pop();
//もし現在のターン数が規定に達しているなら範囲内かをチェック。
if(tim == l){
if(s <= cst && cst <= t) ans[pos] = true;
continue;
}
//まだ規定まで行っていないなら次の頂点に。
for(auto [nxt,c]:path[pos]){
//コストが範囲を超えているならもう見る意味がない。
if(c + cst > t) continue;
que.push({nxt,{c+cst,tim+1}});
}
}
//空白区切りにするためのやつ
vector<int>idx (0);
for(int i=0;i<n;i++){
if(ans[i]) idx.push_back(i+1);
}
for(auto x:idx){
if(x != idx[0]) cout << " ";
cout << x;
}
cout << endl;
}
E - A > B substring
考察
いろいろ同時に考えるとややこしいので簡単なケースから考える。
「左側を1文字目と固定したときr文字目までの部分文字列はこれを満たすか？」これを考えていく。
これは結構シンプル。要するにAの個数とBの個数の差が知りたいので、Aを+1,Bを-1,Cを0として順に足していき「合計が0より大きいとき」条件を満たすことがわかる。
では、左端の固定を外すとどうなるか？つまり「l文字目からr文字目まではこれを満たすか？」を考える。できれば左端を固定したときの考え方を利用できればうれしい。
もし、(l-1)番目までの差がX、r番目までの差がyだとすると、l番目からr番目までの差はy-xで求まる。このy-xが0を超えてほしい。
言い換えればyがxよりも大きければいい。
つまりは「r番目より前で合計がy未満だったときの回数」が右端をr番目としたときの条件を満たす個数となる。
方針をまとめると
- 左から順番にAを+1,Bを-1,Cを0として合計値を出す。
- これまでの中で合計値が「今の合計値」未満だった回数を数える。
範囲の個数を知りたいのでセグメントツリーに任せてみる。
なお、マイナスが面倒なのであらかじめ$5 \times 10^5$を足すという暴挙。
提出
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template <typename T>
//一点変更、区間取得のセグメントツリー
struct ST_SUM{
vector<T>num;
int siz;
ST_SUM(int n){
int x = 1;
while(n > x) x <<= 1;
siz = x;
num = vector<T> ((x<<1),0LL);
}
void Update(int x,T i){
x = x + siz - 1;
num[x] += i;
while(x != 0){
x = (x-1)/2;
num[x] = num[x*2 + 1]+num[x*2 + 2];
}
}
T Sub_Serch(int n,int m,int k,int l,int r){
if(r <= n || m <= l) return 0;
if(n <= l && r <= m) return num[k];
k *= 2;
T lx = Sub_Serch(n, m, k+1, l, (r+l)/2);
T rx = Sub_Serch(n, m, k+2, (l+r)/2, r);
return lx + rx;
}
T Serch(int n){
//0以上n未満の個数を返す。
return Sub_Serch(0, n, 0, 0, siz);
}
};
int main(){
int n;
cin >> n;
//差は-5*10^5~5*10^5を取る
//マイナスだと管理しにくいので、あらかじめ基準点を5*10^5とする。
//そうすると範囲が0~10^6になって管理しやすい。
int bs = 500000;
//うっかり範囲外にならないように下駄をはかせる。
int lim = 1000005;
ST_SUM<ll> tree(lim);
tree.Update(bs,1);
int now = bs;
ll ans = 0;
for(int i=0;i<n;i++){
char x;
cin >> x;
//前から順に数値計算
if(x == 'A') now++;
if(x == 'B') now--;
tree.Update(now,1);
//これまでの合計値が「今の合計値」未満のときの回数を取得。
ans += tree.Serch(now);
}
cout << ans << endl;
}
F - Must Buy
考察
見た目のわりに基礎の積み重ねのような問題。
とりあえず個数、金額ともに余裕があるので,DP[i個目まで見たとき][合計j円の時]=(価値の最大値)として動的計画法。
こうすれば価値の最大値がわかる。ここから経路を復元する。
問題はこの品物は、絶対必要、絶対不要、どちらでもないのどれなのかを判定しなければならない。どうするか。
例えばDP[i][j]が最大値のルート上にいるとき、DP[i-1][j]が同じ値ならばここは最大値ルートになる。一方DP[i-1][j-(i-1の価格)]が同じ値段ならここも最大値ルートとなる。
何もしないなら絶対不要、操作するなら絶対必要、どちらのルートも進めるならどちらでもないということになる。
各商品ごとに最大値ルートがどう分岐しているのかを確認すればOK。
提出
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
int n,m;
cin >> n >> m;
vector<ll>val (n),pr (n);
for(int i=0;i<n;i++) cin >> pr[i] >> val[i];
//基本的なDPの準備
vector<vector<ll>>dp (n+1,vector<ll>(m+1,-1));
dp[0][0] = 0;
//基本的なDPを行う。
for(int i=0;i<n;i++){
for(int j=0;j<=m;j++){
if(dp[i][j] == -1) continue;
dp[i+1][j] = max(dp[i][j],dp[i+1][j]);
if(j+pr[i] <= m){
dp[i+1][j+pr[i]] = max(dp[i][j] + val[i],dp[i+1][j+pr[i]]);
}
}
}
//価値の最大値を求める。
ll mx = 0;
for(int i=1;i<=m;i++){
mx = max(dp[n][i],mx);
}
//各商品、各金額において最大値となりえるものにtrue
vector<vector<bool>>check (n+1,vector<bool>(m+1,false));
for(int i=0;i<=m;i++){
if(dp[n][i] == mx) check[n][i] = true;
}
stack<char>ans;
for(int i=n-1;i>=0;i--){
//ps:買わなくても最大値、us:買うと最大値
bool ps = false,us = false;
for(int j=0;j<=m;j++){
if(!check[i+1][j]) continue;
//買わなくても最大値に行けるか?
if(dp[i+1][j] == dp[i][j]){
ps = true;
check[i][j] = true;
}
//買うと最大値に行けるか?
if(j >= pr[i]){
if(dp[i+1][j] == dp[i][j-pr[i]] + val[i]){
us = true;
check[i][j-pr[i]] = true;
}
}
}
//両方ならB、スルーしかできないならC、必ず買うならA
if(ps && us) ans.push('B');
else if(ps) ans.push('C');
else ans.push('A');
}
while(!ans.empty()){
cout << ans.top();
ans.pop();
}
cout << endl;
}
G - Takoyaki and Flip
考察
ちえんせぐきわからない
結果
ABCDEF(1) 6完 1ペナ 80:34
順位 867位
パフォーマンス 1680
レート 1570(+13)
感想
6完して定位置なのは少々納得いかない。
まあ、全体的に早解き回だったことは間違いないので仕方ないか。
あと、遅延セグ木をちゃんとものにしてれば可能性あったのかな？
今年度中に青に行きたいね。