競プロ参加日記016 Codeforces Round #671 (Div. 2)
・はじめに
A,B,C,D1,D2の5つを出してAとD2がSystemTestで落ちて3完になりました。悲しい。
ただ、レートが+99で1476になりました。水色コーダーです！！
・A. Digit Game
Raze が奇数桁の任意の文字を消す→Breach が偶数桁の任意の文字を消す
を繰り返して行う。1つ数字が残るまで続けて、その数字が奇数ならRazeの勝ち。偶数ならBreachの勝ち。お互いが最善を尽くす場合、勝つのはどちらか？
交互に操作するため、桁数が奇数か偶数かによって奇数番目か偶数番目が残るかが決定します。
お互い、好きな順番で消せるため残る奇/偶数番目を操作するプレイヤーは自分が勝利する奇/偶数は消さずに最後まで置いておくのが最善です。
この問題の難しいところは
The digits of this integer are numerated from 1 to n from the highest-order digit to the lowest-order digit. After this integer is announced, the match starts. (問題文より引用)
で、最上位から桁数を数えて偶奇を決めます！！
数字だから最下位から桁数を求めてWAしました！！しかも、SampleやPreTestは通ります！！
#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
int main(){
int t;
cin>>t;
while(t-->0){
int rk=0,rg=0;
int bk=0,bg=0;
int k;
string n;
cin>>k>>n;
reverse(n.begin(),n.end());
int k2=k;
for(int i=0;i<k-n.size()+10;i++){
n="0"+n;
}
for(int i=0;i<k2;i++){
int n2=n[n.size()-1-i]-'0';
if(i%2==0){
if(n2%10%2==0){
rg++;
}
else{
rk++;
}
}
else{
if(n2%10%2==0){
bg++;
}
else{
bk++;
}
}
n2/=10;
}
if(k%2==0){
if(bg>0) cout<<"2"<<endl;
else cout<<"1"<<endl;
}
else{
if(rk>0) cout<<"1"<<endl;
else cout<<"2"<<endl;
}
}
}※母国語じゃない英語で、こういうのは辛い...。
・B. Stairs
噂のReadForces(多分)。
問題文の意味が分かんないので、貼られてる絵やSampleのIn/Outとnoteからエスパーしました。
以下の条件を満たす階段は美しい。
→1*1,2*2,3*3などの正方形でマスを分割した時に、階段の段数と同じ数に分割できる。
x個のマスを使って作れる、美しい階段の種類数を求めよ。
絵から見るに、1,3,7...と2^aを階差に持つ等差数列の段数が美しくなりそう。
未証明だけど、上記考えで実装したコードでSampleの1000000000000000000が正しく出たため問題なしと判断しました。
#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
int main(){
int t;
cin>>t;
while(t-->0){
long long x;
cin>>x;
long long ans=0;
long long c=1,c2=1;
while(1){
long long n=c2*(c2+1)/2;
if(n>x) break;
x-=n;
ans++;
c*=2;
c2+=c;
//cout<<c<<","<<c2<<","<<x<<endl;
}
cout<<ans<<endl;
}
}・C. Killjoy
各a[]を任意の数に変えて、xと同じ数字にしたことがあるようにする(n回目でxなら、その他回目でxじゃなくてもOK)場合の最小の手数を求めよ。
ただし、任意の数にする際にa[]の増減の和は0になるようにしなければならない。
ややこしそうですが、1回目はai以外をxにしてaiは増減が0になるよう調整。2回目はaiをxにして、ai以外で適当に増減を0にする。とすれば高々2回で達成できます。
Sampleの2つ目のように、全てxの場合は0回です。
また、aiが最初からxか、増減を調整した後にxになる場合、2回目の操作がいらなので1回になります。
#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
int main(){
int t;
cin>>t;
while(t-->0){
int n,x;
cin>>n>>x;
int r[n];
int sum=0;
bool f=true;
bool f2=false;
for(int i=0;i<n;i++){
cin>>r[i];
if(r[i]!=x) f=false;
if(r[i]==x) f2=true;
r[i]-=x;
//cout<<r[i]<<" ";
sum+=r[i];
}
//cout<<endl;
if(f) cout<<"0"<<endl;
else if(sum==0||f2) cout<<"1"<<endl;
else cout<<"2"<<endl;
}
}・D1. Sage's Birthday (easy version)
1～nの数字が1つずつからできる、n個のa[]を任意に並び替えて、a[i-1]>a[i]<a[i+1](i!=0,i!=n)を満たすiの個数を最大化する問題。
a[i-1]>a[i]<a[i+1]が満たされるとき、a[i-1]とa[i+1]は不等式が絶対に満たされなくなります。
満たされる可能性がある数字=o
絶対に満たされない数字=xとすると、
xoxoxoxo.....oxox
のように交互にするのが最大個数になります。また、交互になっているのでoには(n-1)/2以下の数字、xにはそれ以上の数字を入れることでoは必ず条件を満たすようになります。
#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
int main(){
int n;
cin>>n;
int a[n];
for(int i=0;i<n;i++){
cin>>a[i];
}
sort(a,a+n);
cout<<(n-1)/2<<endl;
int b[n];
int c=0;
for(int i=1;i<n;i+=2){
b[i]=a[c++];
}
for(int i=0;i<n;i+=2){
b[i]=a[c++];
}
for(int i=0;i<n;i++){
cout<<b[i];
if(i==n-1) cout<<endl;
else cout<<" ";
}
}・D2. Sage's Birthday (hard version)
D1と違い、a[]の要素が1～nの数字が任意個数になります。(数字の重複あり)
とはいっても、考え方はD1と同じでoxoxox...のように交互になるので、小さい数字をoに集めるのがBestです。
正直、何で分けたの？という感じですね...。
#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
int main(){
int n;
cin>>n;
int a[n];
for(int i=0;i<n;i++){
cin>>a[i];
}
sort(a,a+n);
int b[n];
int c=0;
for(int i=1;i<n;i+=2){
b[i]=a[c++];
}
for(int i=0;i<n;i+=2){
b[i]=a[c++];
}
int ans=0;
for(int i=1;i<n;i+=2){
if(b[i]<b[i-1]&&b[i]<b[i+1]&&i!=0&&i!=n-1) ans++;
}
cout<<ans<<endl;
for(int i=0;i<n;i++){
cout<<b[i];
if(i==n-1) cout<<endl;
else cout<<" ";
}
}ちなみにSystemTestで落とされた原因ですが、
if(b[i]<b[i-1]&&b[i]<b[i+1]&&i!=0&&i!=n-1) ans++;ここのi!=n-1が抜けてました。
これがないと、nが偶数の時にxoxoになります。(正しくはxoxx)
あと、このコードがっつり配列外参照して要るっぽいのでi!=n-1とかi!=0は条件文の先にしないと多分だめです。
AC貰ってるので直しませんが、業務だと指摘が絶対入りそうです。
・E. Decryption
nの約数で円を作る際に、隣にある要素が互いに素である個数を最小化する問題。
未証明＆疲れたので、ざっくり実装の概要だけ。
篩で√nまでの素数を列挙
→nを素因数分解
→素因数を並べて、一番後ろにはnを付ける。
ex.n=420の場合、
素因数を並べる 2,3,5,7
一番後ろにn追加 2,3,5,7,420
→素因数以外の約数列挙して、両隣が素でない場所に約数を適当に詰める。
ちなみにですが、2*3=6のように2つの素数からできる数字以外は答えが0になるそうです。証明だれかお願いします...。
※コードはリファクタリングを試みましたが、無理でした。
業務で書いたらレビューで怒られる....。
#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
int main(){
int t;
cin>>t;
vector<int> pr;
int s[100000]={0};
for(int i=2;i<100000;i++){
if(s[i]==0){
pr.push_back(i);
for(int j=i;j<100000;j+=i){
s[j]=1;
}
//cout<<i<<",";
}
}
while(t-->0){
int n;
cin>>n;
vector<int> ya,vc;
for(int i=0;i<pr.size();i++){
if(n%pr[i]==0) {
ya.push_back(pr[i]);
vc.push_back(0);
}
while(n%pr[i]==0){
n/=pr[i];
vc[vc.size()-1]++;
}
}
if(n!=1){
ya.push_back(n);
vc.push_back(1);
}
/*for(int i=0;i<vc.size();i++){
cout<<ya[i]<<","<<vc[i]<<endl;
}*/
vector<int> ku;
set<int> s;;
stack<int> st,st2;
st.push(1);
st2.push(0);
while(!st.empty()){
int sc=st2.top();
int sn=st.top();
st2.pop();
st.pop();
//cout<<sc<<","<<sn<<endl;
if(sc==vc.size()){
if(sn>1){
ku.push_back(sn);
s.insert(sn);
}
continue;
}
for(int i=0;i<=vc[sc];i++){
st.push(sn*pow(ya[sc],i));
st2.push(sc+1);
}
}
int ans[ku.size()];
int c=0;
sort(ku.begin(),ku.end());
for(int i=0;i<ya.size();i++){
ans[c++]=ya[i];
s.erase(ya[i]);
}
ans[c++]=ku[ku.size()-1];
s.erase(ku[ku.size()-1]);
while(!s.empty()){
auto as=s.begin();
/*cout<<*as<<","<<s.size()<<endl;
for(int i=0;i<c;i++){
cout<<ans[i]<<",";
}
cout<<endl;*/
while(as!=s.end()){
for(int i=0;i<c;i++){
int l=i;
int r=i+1;
if(r>=c) r=0;
if((*as%ans[l]==0||ans[l]%*as==0)&&
(*as%ans[r]==0||ans[r]%*as==0)){
for(int j=c;j>i;j--){
ans[j]=ans[j-1];
}
ans[i+1]=*as;
as=s.erase(as);
c++;
break;
}
if(r==0) as++;
}
}
}
int cnt=0;
//cout<<c<<","<<ku.size()<<endl;
for(int i=0;i<ku.size();i++){
int l=i;
int r=i+1;
if(r>=ku.size()) r=0;
if(!(ans[r]%ans[l]==0||ans[l]%ans[r]==0)){
cnt++;
}
cout<<ans[i];
if(i==ku.size()-1) cout<<endl;
else cout<<" ";
}
cout<<cnt<<endl;
}
}コンテスト中に解けてる842人天才すぎる。
・おわりに
余談ですが、Atcoderやcodeforceの参加記を書いて16回目になります。
この参加記がノイズになっていないかが心配です。ABCなんかは、Fを解かずにEまでしか書いてないものとか多いです...。
そこで、休日などに過去記事の未解答問題を解いて別記事にしてリンクを張ろうかと思っています。(最近上がらないレートを上げる意味もあります。)
中身が分かんないよって場合はごめんなさい！！参加記hogehoge回までお待ちください！！！
この記事が気に入ったらサポートをしてみませんか？