abc293_c
setとdfs
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
int h, w;
int happy = 0;
void route(int y, int x, set<int> chk){
//今いるマスの数字が過去に出てたら終了
if(chk.count(a[y][x])!=0) return;
chk.insert(a[y][x]);
//ゴール到達したらhappy+1
if(y==h-1 && x==w-1){
happy++;
return;
}
//ゴールまで来てなかったら、次のマスへ
if(y+1<h) route(y+1, x, chk);
if(x+1<w) route(y, x+1, chk);
return;
}
int main(){
cin >> h >> w;
rep(i,h){
rep(j,w) cin >> a[i][j];
}
//route(何ステップ目, y, x, 過去に踏んだ数字)
route(0, 0, set<int>());
cout << happy << endl;
return 0;
}
abc291_c
同じとこ2回来てたらyes
setはソート済み重複無し
mapは辞書
ので、今回はset
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using P = pair<int, int>;
int main(){
int n;
string s;
cin >> n >> s;
//set<pair<int, int>> s;
set<P> st;
int x=0, y=0;
st.insert(P(x, y));
rep(i,n){
if (s[i]=='R') x++;
else if (s[i]=='L') x--;
else if (s[i]=='U') y++;
else if (s[i]=='D') y--;
st.insert(P(x, y));
}
if(st.size() != n+1) cout << "Yes" << endl;
else cout << "No" << endl;
return 0;
}
abc279_c
ソートして比較するだけ。
2次元のvectorそのまま扱えるの知らなかった
#include <bits/stdc++.h>
#include <algorithm>
#define rep(i, n) for(int i=0; i<(n); ++i)
using namespace std;
int main(){
int h, w;
cin >> h >> w;
rep(i,h) cin >> s[i];
rep(i,h) cin >> t[i];
string tmp(h, 'a');
rep(i,w){
ss[i] = tmp;
tt[i] = tmp;
}
for(int i=0;i<w;i++){
for(int j=0;j<h;j++){
ss[i][j] = s[j][i];
tt[i][j] = t[j][i];
}
}
/*
rep(i,w){
sort(ss.begin(), ss.end());
sort(tt.begin(), tt.end());
}
*/
sort(ss.begin(), ss.end());
sort(tt.begin(), tt.end());
/*
rep(i,w){
if(ss[i]!=tt[i]){
cout << "No" << endl;
return 0;
}
}
cout << "Yes" << endl;
*/
if(ss==tt) cout << "Yes" << endl;
else cout << "No" << endl;
return 0;
}
abc277_c
問題:
解答:
#include <bits/stdc++.h>
#include <algorithm>
#define rep(i, n) for(int i=0; i<(n); ++i)
using namespace std;
int main(){
int n;
cin >> n;
rep(i,n){
int a, b;
cin >> a >> b;
to[a].push_back(b);
to[b].push_back(a);
}
set<int> reach;
queue<int> q;
reach.insert(1);
q.push(1);
while(!q.empty()){
int v = q.front();
q.pop();
for(int u:to[v]){
if(reach.count(u)) continue;
reach.insert(u);
q.push(u);
}
}
// setの末尾
cout << *reach.rbegin() << endl;
return 0;
}
方針:
隣接リストを作って、BFS。1階からのホップ数が少ない順にみて、行けた場所にチェック。
abc275_b
問題:
解答:
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using ll = long long;
using namespace std;
int main(){
int n = 6, p = 998244353;
rep(i,6) cin >> a[i];
ll b, d;
b = ((((a[0]%p)*(a[1]%p))%p)*(a[2]%p))%p;
d = ((((a[3]%p)*(a[4]%p))%p)*(a[5]%p))%p;
cout << (b-d+p)%p << endl;
return 0;
}
Submission #36085675 - AtCoder Beginner Contest 275
方針:
上の通り。頭悪いんだから全部に剰余つけろ
お気持ち:
abc274_c
問題:
解答:
#include <bits/stdc++.h>
#include <algorithm>
#define rep(i, n) for(int i=0; i<(n); ++i)
using namespace std;
int main(){
int n;
cin >> n;
int child = 2;
for(int i=1;i<=n;i++){
int a;
cin >> a;
p[i*2] = p[i*2+1] = a;
}
for(int i=2;i<=n*2+1;i++){
ans[i] = ans[p[i]]+1;
}
for(int i=1;i<=n*2+1;i++) cout << ans[i] << " ";
puts("");
return 0;
}
方針:
子の世代数が親+1。
お気持ち:
abc273_c
問題:
解答:
#include <bits/stdc++.h>
#include <algorithm>
#define rep(i, n) for(int i=0; i<(n); ++i)
using namespace std;
int main(){
int n;
cin >> n;
rep(i,n){
cin >> a[i];
b[i] = a[i];
}
sort(b.begin(), b.end());
int p = 0, last = -1;
rep(i,n){
if(b[i]!=last){
c[p] = b[i];
last = b[i];
p++;
}
}
/*
rep(i,p) cout << c[i] << endl;
cout << p << endl;
*/
map<int, int> lax;
rep(i,p){
lax[c[i]] = p-i-1;
//cout << c[i] << " " << p-i-1 << endl;
}
//cout << lax[1] << endl;
rep(i,n){
d[i] = lax[a[i]];
}
//rep (i,n) cout << d[i];
sort(d.begin(), d.end());
//rep (i,n) cout << d[i];
rep(i,n) ans[i] = 0;
rep(i,n){
ans[d[i]]++;
}
rep(i,n){
cout << ans[i] << endl;
}
return 0;
}
Submission #35685936 - Panasonic Programming Contest 2022(AtCoder Beginner Contest 273)
方針:
ソート繰り返して、いい辞書をつくる。途中で、ある数より大きい数は何種類あるっていうmapつくった。
ex) map[2]=3 →2より大きい数は3種類ある
お気持ち:
はじめてc解けた!