A – ABC333
Cが3通りしかないため、全通り判定する。でもいいのですが、偶奇の性質を使うことでスラっと書けます。
偶奇同士の掛け算の答えは以下のようになります。
偶*偶=偶 偶*奇=偶 奇*奇=奇
つまり、A*B*Cが奇になるには3つが奇である必要があります。
Cは1,2,3好きに選べるので無視して、A,Bの2つ両方が奇かどうかを見ればOKです。
#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
int main(){
int A,B,C;
cin>>A>>B>>C;
if(A%2==0||B%2==0) cout<<"No"<<endl;
else cout<<"Yes"<<endl;
}
B – Shiritori
ちょっとややこしめ、YESの条件文としては以下です。
- W2～WNにおいて、Wiの最初の文字とWi-1の最後の文字が等しい
- W1～WNにおいて、同じ文字が出現しない
N=100なので書き方は色々あると思いますが、私は条件を満たすものをsetに放り込んで、setのsizeがNと等しいかで判定しました。(setは重複が登録されないので、2の条件がサボれます。)
#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
int main(){
int N;
cin>>N;
set<string> s;
string befS;
cin>>befS;
s.insert(befS);
for(int i=0;i<N-1;i++){
string S;
cin>>S;
if(befS[befS.size()-1]==S[0]) s.insert(S);
befS=S;
}
if(s.size()==N) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
C – Skip
Xを0とした場合、+D,-Dして移動して辿り着ける場所は、D,2D,3D,4D…-D,-2D,-3D,-4D….とDの倍数になります。
なので、この問題は各x[i]とXの距離に対して、最大の約数を求めるものとなります。
#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
int main(){
int N,X;
cin>>N>>X;
int sx[N];
for(int i=0;i<N;i++){
int x;
cin>>x;
sx[i]=abs(X-x);
}
vector<int> ans;
for(int i=2;i<sqrt(sx[0])+2;i++){
while(sx[0]%i==0){
sx[0]/=i;
ans.push_back(i);
}
}
if(sx[0]!=0) ans.push_back(sx[0]);
for(int i=1;i<N;i++){
vector<int> tmp;
for(int j=0;j<ans.size();j++){
if(sx[i]%ans[j]==0){
sx[i]/=ans[j];
tmp.push_back(ans[j]);
}
}
ans=tmp;
}
int b=1;
for(int i=0;i<ans.size();i++) b*=ans[i];
cout<<b<<endl;
}
かなり面倒なコードを書きましたが、”最大の約数を求める”場合、最大公約数を使うと楽です。
#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
int gcd(int a,int b){
if(a<b) return gcd(b,a);
if(b==0) return a;
return gcd(b,a%b);
}
int main(){
int N,X;
cin>>N>>X;
int gc;
cin>>gc;
gc=abs(gc-X);
for(int i=0;i<N-1;i++){
int x;
cin>>x;
gc=gcd(gc,abs(X-x));
}
cout<<gc<<endl;
}
D – Make Them Even
D – Make Them Even (atcoder.jp)
偶数枚コインが置かれた場所を最大化する問題です。
任意の一筆書きのルートで、奇数枚なら1枚次に送る。ということを繰り返せば良さそうです。
1 2 3 4 5 6 7 8 9 左から右に見ていく i=0 0 3 3 4 5 6 7 8 9 奇数なので右に送る i=1 0 2 4 4 5 6 7 8 9 奇数なので右に送る i=2 0 2 4 4 5 6 7 8 9 偶数なのでそのまま i=3 0 2 4 4 5 6 7 8 9 偶数なのでそのまま i=4 0 2 4 4 4 7 7 8 9 奇数なので右に送る i=5 0 2 4 4 4 6 8 8 9 奇数なので右に送る i=6 0 2 4 4 4 6 8 8 9 偶数なのでそのまま i=7 0 2 4 4 4 6 8 8 9 偶数なのでそのまま i=8 0 2 4 4 4 6 8 8 9 奇数だけどゴールなので無視
最後が奇数になりますが、コインの総量が奇数なのでどうやっても残ります。(すべてのマスが偶数枚の場合、偶数同士の足し算は偶数なので総量も偶数になるはず)
最後を除く一筆書きのルートが全て偶数で均せるため最大化できます。
#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
int gcd(int a,int b){
if(a<b) return gcd(b,a);
if(b==0) return a;
return gcd(b,a%b);
}
int main(){
int H,W;
cin>>H>>W;
int a[H][W];
for(int i=0;i<H;i++){
for(int j=0;j<W;j++){
cin>>a[i][j];
}
}
vector<int> a1,a2,a3,a4;
for(int i=0;i<H;i++){
if(i%2==0){
for(int j=0;j<W-1;j++){
if(a[i][j]%2==1){
a1.push_back(i);
a2.push_back(j);
a3.push_back(i);
a4.push_back(j+1);
a[i][j+1]++;
}
}
if(i!=H-1&&a[i][W-1]%2==1){
a1.push_back(i);
a2.push_back(W-1);
a3.push_back(i+1);
a4.push_back(W-1);
a[i+1][W-1]++;
}
}
else{
for(int j=W-1;j>=1;j--){
if(a[i][j]%2==1){
a1.push_back(i);
a2.push_back(j);
a3.push_back(i);
a4.push_back(j-1);
a[i][j-1]++;
}
}
if(i!=H-1&&a[i][0]%2==1){
a1.push_back(i);
a2.push_back(0);
a3.push_back(i+1);
a4.push_back(0);
a[i+1][0]++;
}
}
}
cout<<a1.size()<<endl;
for(int i=0;i<a1.size();i++){
cout<<a1[i]+1<<" "<<a2[i]+1<<" "<<a3[i]+1<<" "<<a4[i]+1<<endl;
}
}
コメント