【Atcoder日記】ABC #336

こんにちはRockinWoolです。最近は結構頑張って活動できていると思います。頭痛も寒さに慣れたからか軽減できていますしね。
さて、1週間前の話になりますがABC#336を解いてみたので、解説と比較していこうと思います。今回は45分で3問も解けたので自分を褒めたい一方で、4問目で完全にスタックしたので解法を確認していこうと思います。それでは。

A問題 龍文字列

なんのことは無い平凡なA問題です。oをN個付ければ良いだけなのでかんたんでした。

#include<iostream>
#include<string>
using namespace std;

int main(){
    int N;
    cin >> N ;
    cout<<'L';
    for(int i=0;i<N;i++){
        cout<<'o';
    }
    cout<<"ng"<<endl;
}

B問題 CTZ

2進数化した時に、末尾に何個0が連続するかを算出する問題です。一般的に使われるc++のライブラリではstring型で出てこないため0の個数を確認することができませんでした。そこで、自作でstring型の2進数を返すtoBinaryを作ってやれば解決します。

#include <iostream>
#include <bitset>
using namespace std;

string toBinary(int n) {
  string r;
  while (n != 0) {
    r += (n % 2 == 0 ? "0" : "1");
    n /= 2;
  }
  return r;
}

int main(void){
	long long N;
	cin >> N;

    string BI;
	BI = toBinary(N);
    int ctx=0;
	for(int i=0;i<BI.size();i++){
        if(BI[i]=='0'){
            ctx +=1;
        }
        else{
            break;
        }
    }
    cout<<ctx<<endl;
    return 0;
}

ちなみに公式ではbitsライブラリを使って下記のように解いていました。

#include <bits/stdc++.h>
using namespace std;
int main() {
	int n;
	cin>>n;
	for(int i=0;;i++){
		if(n&(1<<i)){
			cout<<i<<endl;
			return 0;
		}
	}
}

まずint nがbitとして扱えることに驚き、次に1を左にi個シフトするのを1<<iと表現するのがびっくりですね。あとは、左にi桁シフトした1とnでandを取って0でなければ0がi個あることになるという仕組みです。1<<iの挙動に関しては下記プログラムで確認しました。

#include<iostream>
#include<string>
using namespace std;

int main(){
    int n;
    cin >> n;
    n = 1<<n;
    cout << n <<endl;
}

これだとn=3で8, n=2で4, n=1で2, n=0で1を出力します。左にn個シフトしていることがわかりますね。

C問題 EvenDigits

5個の数字{0,2,4,6,8}のみを使って低い順に並べて、i番目に低い数字を答えるという問題。これは{0,1,2,3,4}だったとしたら5進数を答えれば良いと気づけたので、B問題のtoBinaryを流用して5進数を算出する関数を作ればクリアです。

#include <iostream>
#include <unordered_map>
#include <string>

using namespace std;
// 7を入力すると21と変換されるように、実際とは逆順になる
string to5inary(long long n) {
  string r;
  if(n==0){return "0";}
  while (n != 0) {
    if(n%5 ==0){
        r +="0";
    }else if(n%5 ==1){
        r +="2";
    }else if(n%5 ==2){
        r +="4";
    }else if(n%5 ==3){
        r +="6";
    }else{
        r +="8";
    }
    n /= 5;
  }
  return r;
}


int main(){
    long long N;
    string Fifnary;
    cin >> N;
    Fifnary = to5inary(N-1);
    for(int i=Fifnary.size()-1;i>=0;i--){
        cout << Fifnary[i];
    }
    cout <<endl;
}

コードの質と量は全然違いますが、公式でもまったく同じ解き方をしていたので嬉しいですね。公式から学べることとしては、for(int i=Fifnary.size()-1;i>=0;i–)の部分をreverse(Fifnary.begin(),Fifnary.end())と書けたということでしょうか。

D問題 ピラミッド数列

ピラミッド数列を考えるときにまず困ったのは1,1,2,2,3,2,2,1のように、もともとの数列の中心を軸にピラミッドを作ると121が算出されるけれど、本当の最大ピラミッドは12321のパターンです。結局これが解けなかったのでこの問題でスタックしました。
さて、公式の回答をここで見てみましょう。

#include <bits/stdc++.h>
using namespace std;
int main(void){
	int n,ans=0;
	cin>>n;
	vector<int>a(n+2);
	vector<int>m1(n);
	vector<int>m2(n);
	for(int i=0;i<n;i++)cin>>a[i+1];
	m1[0]=min(a[0],a[1]-1);
	for(int i=1;i<n;i++)m1[i]=min(m1[i-1],a[i+1]-i-1);
	m2[n-1]=a[n+1]+n+1;
	for(int i=n-2;i>=0;i--)m2[i]=min(m2[i+1],a[i+2]+i+2);
	for(int i=0;i<n;i++)ans=max(ans,min(m1[i]+i+1,m2[i]-i-1));
	
	cout<<ans<<endl;
	return 0;
}

解説を読んだのですが、かなり複雑で難しいです。解説を写経してなんとか意味はわかったのですが、これを時間内に解くとなるとなにかが必要ですね。

まとめ

D問題に初めて挑戦してみましたが、かなり難しいですね。これからも精進していつかは解けるようになりたいものです。それではまた次回！