最高の出来だった気がした男の備忘録です
コンテスト概要
パナソニックグループ プログラミングコンテスト2025（AtCoder Beginner Contest 427
開催日:2025年10月11日 21:00-22:40
A - ABC -> AC
考察
A問題らしく言われた通りにやるだけの問題。
eraseつかってあらかじめ消してもいいし。順に出力しながら該当の個所を飛ばしてもいい。
まぁ、A問題なんで先に思いついたほうを実装でいいでしょう。
提出
#include <bits/stdc++.h>
using namespace std;
int main(){
string s;
cin >> s;
//飛ばしたいのは真ん中
int l = s.length() / 2;
for(int i=0;i<s.length();i++){
//真ん中でなければ出力。
if(i != l) cout << s[i];
}
cout << endl;
}
B - Sum of Digits Sequence
考察
なんか、最近B問題を理解するのにちょっと時間が掛かっちゃんですよね。
まずは問題文をもっと簡単な式にできないかと考える。すると
$A_{i-1} = f(A_{0}) + f(A_{1}) + f(A_{2}) + ... + f(A_{i-2})$
$A_{i} = f(A_{0}) + f(A_{1}) + f(A_{2}) + ... + f(A_{i-2}) + f(A_{i-1})$
と書ける。
ここで$A_i$に$A_{i-1}$を代入すると
$A_i = A_{i-1} + f(A_{i-1})$
となる。めっちゃシンプル。
というわけで今の値に、各桁の合計を足すことを続ければOK。
当時は混乱し無駄な引数をかませてる。何やってんでぃ。
提出
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
cin >> n;
//最初は1スタート
int ans = 1,bef = 1;
for(int i=0;i<n-1;i++){
int b = bef;
//合計値に各桁の和を足していく。
while(b != 0){
ans += b%10;
b /= 10;
}
bef = ans;
}
cout << ans << endl;
}
C - Bipartize
考察
前回同様350点のC問題。今回も拍子抜けパターンだった。
今回丁寧にも二部グラフの説明があるので少々閃きやすそう。
ここにもある通り「頂点を白と黒に塗り分けたとき、すべての辺が異なる色を結ぶ」ものが二部グラフである。
今ある状態から適当に辺を削除して二部グラフかどうかを確かめるのは少々大変。
ただ、今回極端なほどにNが小さい。これを利用したい。
というわけで発想の逆転をする。辺を削除してから頂点をぬるではなく、あらかじめ色を塗ってから、辺を付け加えることで二部グラフを作ってみる。
こうすれば判定も楽である。順番に辺を見ていき、頂点の色が同じなら付けない、違うならつける。と、判定も楽になる。
色の塗り方も1024通りしかないので時間もかなり余裕。
意外とあらかじめ決め打つと上手くいく問題って多かったりする。
提出
#include <bits/stdc++.h>
using namespace std;
int main(){
int n,m;
cin >> n >> m;
//辺がつないでいるところを管理
vector<pair<int,int>>path (m);
for(int i=0;i<m;i++){
int x,y;
cin >> x >> y;
path[i] = {x-1,y-1};
}
//2^nパターンの塗り分け
int ptn = (1<<n);
int ans = 100;
for(int i=0;i<ptn;i++){
int cnt = 0;
for(auto [x,y]:path){
//色の違いはbitで管理。
int c = (1<<x) + (1<<y);
int d = (i&c);
//cと同じ→両方とも1、cが0→両方とも0
//邪魔な辺の数を数える。
if(d == c || d == 0) cnt++;
}
ans = min(ans,cnt);
}
cout << ans << endl;
}
D - The Simple Game
考察
最近クエリが大量にくるタイプの問題が多くて困る。
クエリを1つでもミスったらトータルがWAになるから、ミスの度合いがわかりにくくなるんだよね。
愚痴はさておき、ゲームのシミュレーションをする問題。あまり得意じゃない。
定石としてはDFSでゲームを進めていき、すべてのパターンで勝てる1手があるかを確認すればいい。
ただ、今回はただDFSをするとTLEになってしまう。
例えば100の頂点があり、すべての頂点からすべての頂点に道があるとする。
そうすると毎回99個の選択肢があり、最悪の場合大体$10^{40}$パターンを見る必要がある。到底間に合わない。
ただXターン目に頂点Ｙにいるといった組み合わせはどんなに大きくても$4\times10^6$個しかない。ここに弱点がありそう。
あるルートでＸターン目に頂点Ｙに行くと勝てるとき、別のルートでたどり着いても必ず勝てるはずである。何度も同じ状況を確認する必要はない。
というわけで、一度確認したパターンをメモしておき、その状況になったら値を返せば計算量もかなりすっきりする。
これがメモ化再帰である。
ちなみにターン数を勘違いして1ペナです。
提出
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
//ゲームをシミュレーション
int DFS(int now,int pos,int rem,vector<int> &str,vector<vector<int>> &path,vector<vector<int>> &ptn){
//一回確認したことがあるパターンならそれを返す。
if(ptn[pos][rem] != -1) return ptn[pos][rem];
//ターンが終了したなら今いるマスが勝者。
if(rem == 0) return ptn[pos][rem] = str[pos];
bool check = false;
for(auto nex:path[pos]){
//とりあえずでたらめに動かす。
//1回でも勝てる手があるなら、ここに来れば勝てる。
if(DFS(1-now, nex, rem-1, str, path, ptn) == now) check = true;
}
//勝てる手があれば今動かしている人の勝利
if(check) return ptn[pos][rem] = now;
//勝機がないなら相手の勝利。
return ptn[pos][rem] = 1 - now;
}
int main(){
int t;
cin >> t;
for(int rp=0;rp<t;rp++){
int n,m,k;
cin >> n >> m >> k;
k *= 2;
vector<int>str (n);
for(int i=0;i<n;i++){
char x;
cin >> x;
//A,Bは扱いづらいので0と1に変換
if(x == 'A') str[i] = 0;
else str[i] = 1;
}
vector<vector<int>>path (n,vector<int>(0));
for(int i=0;i<m;i++){
int x,y;
cin >> x >> y;
path[x-1].push_back(y-1);
}
//結果のメモを用意
vector<vector<int>>ptn (n,vector<int>(k+1,-1));
//DFS(誰の手番、今の場所,残り回数、頂点の文字、つながり方、メモ)
int ans = DFS(0, 0, k, str, path, ptn);
//結果が0ならAliceの勝ち、1ならBobの勝ち。
if(ans == 0) cout << "Alice\n";
else cout << "Bob\n";
}
}
E - Wind Cleaning
考察
一言でいうなら「簡単に実装できますか？」という問題。重実装系はバグったときのショックがデカい。
高橋君は一歩も動かないので座標だけメモして消えてもらう。
後はBFSで盤面を確かめながらゴミを毎回上下左右に動かす。この時高橋君の座標にゴミが来た場合は飛ばす。
全部落ちたら回数を出力。
正直これだけではある。ただ正確に、簡素にやるのが難しい。
やった工夫でいえば、
盤面をmapで持って置き同じ状況を何度も見ない。
盤面を各行ごとに2進数で管理し、左右はbitシフトで管理できるようにする。
といったくらい。
重実装はなれるしかない。
提出
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int h,w;
//右に動かす場合
vector<int> mv1(vector<int> vec){
//右にシフトすれば勝手にゴミが消える。
for(int i=0;i<h;i++) vec[i] >>= 1;
return vec;
}
//左に動かす場合
vector<int> mv2(vector<int> vec){
int c = (1 << w);
//左にシフトして余りを取って一番左をカット
for(int i=0;i<h;i++){
vec[i] <<= 1;
vec[i] %= c;
}
return vec;
}
//上に動かす場合
vector<int> mv3(vector<int> vec){
//配列をずらす
for(int i=0;i<h-1;i++){
vec[i] = vec[i+1];
}
//一番下はゴミ無し
vec[h-1] = 0;
return vec;
}
//下に動かす場合
vector<int> mv4(vector<int> vec){
/配列をずらす
for(int i=h-1;i>0;i--){
vec[i] = vec[i-1];
}
/一番上はゴミ無し
vec[0] = 0;
return vec;
}
int main(){
cin >> h >> w;
//ゴミの場所を1として二進数で管理。
vector<int>now (h,0);
int x,y;
for(int i=0;i<h;i++){
for(int j=0;j<w;j++){
now[i] <<= 1;
char c;
cin >> c;
//ゴミの場所のbitを立てる
if(c == '#') now[i]++;
//高橋君の場所だけメモ
//列もbitで管理。
if(c == 'T') x = i,y = (1<<(w-j-1));
}
}
map<vector<int>,int>mp;
//目標は全部0
vector<int>gl (h,0);
mp[now] = 1;
queue<vector<int>>que;
que.push(now);
while(!que.empty()){
auto pos = que.front();
que.pop();
int cnt = mp[pos] + 1;
vector<int> nex;
//愚直に上下左右に動かす。
nex = mv1(pos);
if((nex[x]&y) == 0){
if(nex == gl){
//清掃完了なら今の値を出力
cout << cnt - 1<< endl;
return 0;
}
if(mp[nex] == 0){
mp[nex] = cnt;
que.push(nex);
}
}
nex = mv2(pos);
if((nex[x]&y) == 0){
if(nex == gl){
//清掃完了なら今の値を出力
cout << cnt - 1 << endl;
return 0;
}
if(mp[nex] == 0){
mp[nex] = cnt;
que.push(nex);
}
}
nex = mv3(pos);
if((nex[x]&y) == 0){
if(nex == gl){
//清掃完了なら今の値を出力
cout << cnt - 1<< endl;
return 0;
}
if(mp[nex] == 0){
mp[nex] = cnt;
que.push(nex);
}
}
nex = mv4(pos);
if((nex[x]&y) == 0){
if(nex == gl){
//清掃完了なら今の値を出力
cout << cnt - 1 << endl;
return 0;
}
if(mp[nex] == 0){
mp[nex] = cnt;
que.push(nex);
}
}
}
//清掃失敗
cout << "-1" << endl;
}
F - Not Adjacent
考察
条件下だと30個の選び方は大体$2\times10^6$になるので半分全列挙で行けそうということは築いたんですが、上手く列挙できませんでした。残念。
結果
ABCD(1)E 5完 68:41
順位 924位
パフォーマンス 1546
レート 1375(+21)
感想
とんでもない重実装回でした。運よくバグを埋め込むこともなかったので久々の3桁順位で勝利。
ただ、こういうときに限ってF問題の正解者のほうが多くて伸びが鈍化させられるこの現象、ちょっと気に食わない。
正解者と点数が反比例してたらより高みに行けたんですが。まあレートは伸びたので文句はこれぐらいに。