AtCoder Beginner Contest 004(ABC004) 解説

ABC

今回、ある理由からC問題はKotlinを使ってみました。

A – 流行

A - 流行
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

文章の通りです。入力*2を出力すればOKです。

#include<bits/stdc++.h>

using namespace std;

int main(){
    int N;
    cin>>N;
    cout<<2*N<<endl;
}

B – 回転

B - 回転
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

180度回転するということは、Y軸X軸ともに反転するということです。
なので、以下のように出力すればOKです。

c3,3 c3,2 c3,1 c3,0
c2,3 c2,2 c2,1 c2,0
c1,3 c1,2 c1,1 c1,0
c0,3 c0,2 c0,1 c0,0
#include<bits/stdc++.h>

using namespace std;

int main(){
    char c[4][4];

    for(int i=0;i<4;i++){
        for(int j=0;j<4;j++){
            cin>>c[i][j];
        }
    }

    for(int i=0;i<4;i++){
        for(int j=0;j<4;j++){
            cout<<c[3-i][3-j];
            if(j==3) cout<<endl;
            else cout<<" ";
        }
    }
}

C – 入れ替え

C - 入れ替え
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

一番簡単な方法は愚直にシミュレーションする方法ですが、O(N)のためTLEしてしまいます。
部分点のN<=50ではTLEしないため、部分点は取得できます。

#include<bits/stdc++.h>

using namespace std;

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

    int c[6]={1,2,3,4,5,6};
    for(int i=0;i<N;i++){
        swap(c[i%5],c[i%5+1]);
    }

    cout<<c[0]<<c[1]<<c[2]<<c[3]<<c[4]<<c[5]<<endl;
}

制限時間ギリギリでACしちゃいました\(^o^)/

さすがC++ですね。O(10^9)でも簡易な処理だと2s以内で終わっちゃうようです。
これだと消化不良感があるので、上記コードをKotlinで書きなおしました。

fun main(args: Array<String>) {
	val n = readLine()!!.toInt()
    val c = arrayOf(1,2,3,4,5,6)
  for(i in 0 until n){
    var tmp=c[i%5]
    c[i%5]=c[i%5+1]
    c[i%5+1]=tmp
  }
  for(i in 0 until 6){
    print(c[i])
  }
}

無事(?)TLEしました。
ここから速度改善をします。

Nを増やしたときの動きを観察します。

N=1 213456
N=2 231456
N=3 234156
...
N=29 123465
N=30 123456
N=31 213456

どうもN=30でループしているようです。
つまり、31回の操作後の配列=1回の操作後の配列となります。
30回操作することは無駄であるため、%30で剰余を取った数だけシミュレーションすればOKです。

fun main(args: Array<String>) {
    val n = readLine()!!.toInt()%30
    val c = arrayOf(1,2,3,4,5,6)
  for(i in 0 until n){
    var tmp=c[i%5]
    c[i%5]=c[i%5+1]
    c[i%5+1]=tmp
  }
  for(i in 0 until 6){
    print(c[i])
  }
}

D – マーブル

D - マーブル
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

R,G,Bそれぞれのマーブルを一番近い場所に愚直に置いていくやり方が良さそうです。
(Rなら、-100,-99,-101,-98,-102…と順に近いほうに送っていく)
この解法で1<=RGB<=40の30点はOKです。

#include<bits/stdc++.h>

using namespace std;

int main(){
    int R,G,B;
    cin>>R>>G>>B;
    int ans=0;

    R--;
    G--;
    B--;
    for(int i=1;R>0;i++){
        ans+=i*min(2,R);
        R-=2;
    }
    for(int i=1;G>0;i++){
        ans+=i*min(2,G);
        G-=2;
    }
    for(int i=1;B>0;i++){
        ans+=i*min(2,B);
        B-=2;
    }

    cout<<ans<<endl;
}

ただ、満点解法の場合NGです。というのもマーブルの数が多い場合、どこかでぶつかってしまうからです。

全探索を単純にするとTLEのため、一つ基準のマーブルを決め、それを全探索します。
真ん中のマーブルの位置が決まれば、左右のマーブルは簡単に決まりそうだったため、Gのマーブルをどこに置くかを全探索。それを元にR,Bのマーブルの位置を決めて最小を取る…
としたかったのですが、以下のACコードをご参照ください。

#include<bits/stdc++.h>

using namespace std;

int main(){
    int R,G,B;
    cin>>R>>G>>B;
    int ans=INT_MAX;

    //900,1000,1100で考える
    for(int i=1000-G;i<=1000+1;i++){
        int tR=R;
        int tB=B;
        int f[2000]={0};
        int c=0;
        for(int j=i;j<=i+G-1;j++){
            f[j]=1;
            c+=abs(1000-j);
        }
        if(f[900]==0) {
            f[900]=1;
            tR--;
        }
        bool tobi=true;
        for(int j=1;tR>0;j++){
            if(f[900+j]==0&&tobi){
                f[900+j]=1;
                tR--;
                c+=j;
            }
            else tobi=false;
            if(tR<=0) break;
            if(f[900-j]==0){
                f[900-j]=1;
                tR--;
                c+=j;
            }
            if(tR<=0) break;
        }
        if(f[1100]==0) {
            f[1100]=1;
            tB--;
        }
        tobi=true;
        for(int j=1;tB>0;j++){
            if(f[1100+j]==0){
                f[1100+j]=1;
                tB--;
                c+=j;
            }
            if(tB<=0) break;
            if(f[1100-j]==0&&tobi){
                f[1100-j]=1;
                tB--;
                c+=j;
            }
            else tobi=false;
            if(tB<=0) break;
        }
        ans=min(c,ans);
        c=0;
        for(int j=0;j<2000;j++) f[j]=0;
        for(int j=i;j<=i+G-1;j++){
            f[j]=1;
            c+=abs(1000-j);
        }
        tR=R;
        tB=B;
        if(f[900]==0) {
            f[900]=1;
            tR--;
        }
        for(int j=1;tR>0;j++){
            if(f[900+j]==0){
                f[900+j]=1;
                tR--;
                c+=j;
            }
            if(tR<=0) break;
            if(f[900-j]==0){
                f[900-j]=1;
                tR--;
                c+=j;
            }
            if(tR<=0) break;
        }
        if(f[1100]==0) {
            f[1100]=1;
            tB--;
        }
        for(int j=1;tB>0;j++){
            if(f[1100+j]==0){
                f[1100+j]=1;
                tB--;
                c+=j;
            }
            if(tB<=0) break;
            if(f[1100-j]==0){
                f[1100-j]=1;
                tB--;
                c+=j;
            }
            if(tB<=0) break;
        }
        ans=min(c,ans);
    }
    cout<<ans<<endl;
}

ヤバそうでしょ?実際ヤバいです。
Gは連続している(GGGRGGGみたいに割り込む配置や、GGG空GGGみたいに間に何も入っていない箱がない)のが最適と考え、連続区間を-G~Gの範囲内で動かしました。
残りのRとBは近いところにマーブルを置いていくのですが、この際、飛越を許容するかしないかの2パターン求めました。(RRRGGGRRBBBみたいなパターン)

全探索の場合、思いのほか考えるケースが多かったです。
Atcoderの公式解説を見たのですが、DPで求めるのが一番素直かな?と思いました。
(後で解いておきます> <)

コメント

  1. […] […]

タイトルとURLをコピーしました