いつも通りだったはず男の備忘録です
コンテスト概要
AtCoder Beginner Contest 404（Promotion for Engineer Guild）
開催日:2025年5月3日 21:00-22:40
A - Not Found
考察
高々25文字なので何をやっても許されそう。
とりあえずvectorで文字が出た回数をメモ。その後回数が0だったものを出力。
チョイっとめんどくさいA問題
提出
#include <bits/stdc++.h>
using namespace std;
int main(){
string s;
cin >> s;
//vectorで文字の出現回数を管理
vector<int>num (26,0);
for(auto x:s){
num[x-'a']++;
}
for(int i=0;i<26;i++){
//一回も出なかった文字を出力
if(num[i] == 0){
char ans = 'a' + i;
cout << ans << endl;
return 0;
}
}
}
B - Grid Rotation
考察
グリッドが2つあるやつはちょっと難易度上がりがちだよね。
もし、グリッドが回せないなら色の異なるマスの数が答え。
じゃあ回すとどうなるか？結局色の異なるマスの数が答え。
なので4方向に関してマス目の異なる数を数えればOK。
ただ回す回数も1手なのでそれを足し忘れないように。
提出
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
//グリッドを90度回転させる関数
void trn(vector<vector<char>> &s,int n){
vector<vector<char>>k (n,vector<char>(n));
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
//90ど回すとどこを参照するかちゃんと考える
k[i][j] = s[n-1-j][i];
}
}
s = k;
return;
}
int main(){
int n;
cin >> n;
vector<vector<char>>s (n,vector<char>(n)),t (n,vector<char>(n));
for(int i=0;i<n;i++){
for(int j=0;j<n;j++) cin >> s[i][j];
}
for(int i=0;i<n;i++){
for(int j=0;j<n;j++) cin >> t[i][j];
}
//デカい値を仮置き
int ans = 1e6;
for(int i=0;i<4;i++){
int cnt = 0;
//色の違うマスを全探査
for(int x=0;x<n;x++){
for(int y=0;y<n;y++){
if(s[x][y] != t[x][y]) cnt++;
}
}
//回転させた回数も忘れずにansを更新
ans = min(ans,cnt+i);
//グリッドを回転させる。
trn(s,n);
}
cout << ans << endl;
}
C - Cycle Graph?
考察
ガチャガチャ言ってるが要するに「一直線に進んですべてのマスを通り元の場所に戻って来れるか？あと無駄な辺もないか？」が分かればよい。
なので、頂点数Nと辺の数Mが異なっている場合話にならない。
N=Mを前提とし、ある頂点から進みNマス後に元の場所に居ればOK。
実装がめんどいんだなこれが。
提出
#include <bits/stdc++.h>
using namespace std;
int main(){
int n,m;
cin >> n >> m;
//N≠Mは論外
if(n != m){
cout << "No" << endl;
return 0;
}
//辺のつながりをメモ
vector<vector<int>>num (n,vector<int>(0));
for(int i=0;i<m;i++){
int x,y;
cin >> x >> y;
num[x-1].push_back(y-1);
num[y-1].push_back(x-1);
}
//頂点を通ったかを確認
vector<bool>che (n,false);
//とりあえず頂点１(0-indexで０)から始める
int now = 0;
while(now != -1){
int nex = -1;
for(auto x:num[now]){
//辺のうち通ってないほうに向かう
if(!che[x]){
nex = x;
che[x] = true;
break;
}
}
now = nex;
}
string ans = "Yes";
//通ってない場所があったらNO
for(auto x:che){
if(!x) ans = "No";
}
cout << ans << endl;
}
D - Goin' to the Zoo
考察
もし動物を見る回数が1回以上ならbit全探査でおしまい。
だが、今回は2回以上見る必要がある。
ある動物園にしかいない動物がいたとき、この動物園は2回通う必要がある。逆に言えば特殊な動物園でも最大でも2回しか通わない。
ということでそれぞれの動物園について0回、1回、2回通った場合をすべて探査できればよい。
2進数を使えば0回を1回を全探査できるなら、3進数を使えば0回、1回、2回を調べられる。
というわけで、3進数を使ったbit全探査(?)を行えばOK。
提出
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
int n,m;
cin >> n >> m;
//動物園ごとにいる動物を管理
vector<vector<int>>num (n,vector<int>(0));
//動物園の入場料を管理
vector<ll>cst (n);
for(int i=0;i<n;i++)cin >> cst[i];
for(int i=0;i<m;i++){
int k;
cin >> k;
//動物園ごとに動物を追加
for(int j=0;j<k;j++){
int x;
cin >> x;
num[x-1].push_back(i);
}
}
//bit全探査の範囲は(0,2^n]なので、応用して(0,3^n]
int pt = pow(3,n);
ll ans = (1LL<<60);
for(int i=0;i<pt;i++){
int c = i;
vector<int>ct (m,0);
ll fe = 0;
for(int j=0;j<n;j++){
//iを三進数で見たときのj桁目が通う回数
int s = c%3;
fe += cst[j] * s;
//通う回数分だけ動物を見る
if(s!=0) for(auto x:num[j])ct[x] += s;
//次の桁をチェック
c /= 3;
}
int cnt = 0;
for(auto x:ct){
if(x > 1) cnt++;
}
//ちゃんと全部の動物を見れたら答えを更新
if(cnt == m) ans = min(ans,fe);
}
cout << ans << endl;
}
E - Bowls and Beans
考察
何をしたいのかわかりづらい問題。しっかりとかみ砕いていく。
「まず茶碗を一列に並べる。」
「ある茶碗の豆を最大C個前の茶碗に移動させれる。」
「豆を一番前に集めるのに最大何手必要か？」というのが概要。
ここで移動させる豆の数は任意という設定。だが、例えば3つの豆を1つずつ3手で送るより一気に1手で送るほうがいいに決まってる。なので豆は全部一気に送ることにする。
さて、ここで豆はちまちま送るより一気に送るほうが効率がいいはず。なので、豆は後ろから順に合わせていくのが最短手っぽい。これを端的に言えば「茶碗0と豆のある茶碗を最短ですべて通れ」という問題になる。ここまでくればあとは最短経路問題になる。
茶碗０から「豆のある手前の茶碗」に最短で向かう。その茶碗から「豆のある手前の茶碗」に最短で向かい...を最後までやって経由した茶碗の個数が答え。
とまあ簡単に言ってますがこの考察までに50分くらいかかってます...
提出
#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(){
int n;
cin >> n;
//豆が送られてくる茶碗のリスト
vector<vector<bool>>path (n,vector<bool>(n,false));
for(int i=1;i<n;i++){
int x;
cin >> x;
//茶碗iから手前x個の茶碗は、茶碗iは豆が送られてくる。
for(int j=0;j<x;j++){
path[i-1-j][i] = true;
}
}
//豆のある場所だけに興味がある
queue<int>bn;
for(int i=1;i<n;i++){
int x;
cin >> x;
if(x == 1) bn.push(i);
}
int now = 0;
int ans = 0;
while(!bn.empty()){
//今の茶碗と最も手前の茶碗の最短距離を考える
int nex = bn.front();
bn.pop();
vector<int>gone (n,1e6);
gone[now] = 0;
//茶碗iから茶碗jまでの最短距離をダイクストラで
p_que<pair<int,int>> que;
que.push({0,now});
while(!que.empty()){
auto[x,p] = que.top();
que.pop();
if(gone[p] != x) continue;
//現在地から目的地までで経路がある場所を確認
for(int i=p+1;i<=nex;i++){
if(!path[p][i]) continue;
if(gone[i] > gone[p] + 1){
gone[i] = gone[p] + 1;
que.push({gone[i],i});
}
}
}
ans += gone[nex];
now = nex;
}
cout << ans << endl;
}
結果
ABCD(1)E(2) 5完 105:34
順位 1708位
パフォーマンス 1290
感想
んー。ペースはいつも通りだったんですがちょっと成績が振るわなかった。
タイムも回答数もここ4回のABCと変わらないんですがねぇ。
やっぱり早解きは苦手だ。