ABC 004

abc004.contest.atcoder.jp

A問題

#include <bits/stdc++.h>
 
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
typedef long long int ll;
using namespace std;
 
int main(void) {
    int N;
    cin >> N;
    cout << 2*N << endl;
}

Submission #1024943 - AtCoder Beginner Contest 004 | AtCoder

B問題

#include <bits/stdc++.h>
 
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
typedef long long int ll;
using namespace std;
 
int main(void) {
    char c[4][4];
    REP(i, 4) REP(j, 4) cin >> c[i][j];
    for(int i=3; i>=0; --i) {
        for(int j=3; j>0; --j) cout << c[i][j] << " ";
        cout << c[i][0] << endl;
    }
}

Submission #1024944 - AtCoder Beginner Contest 004 | AtCoder

C問題

観察すると30回ごとに同じパターンになることからNを30で割った余りを求めてからシミュレーション

#include <bits/stdc++.h>
 
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
typedef long long int ll;
using namespace std;
 
int main(void) {
    int N;
    cin >> N;
    int c[6];
    N %= 30;
    REP(i, 6) c[i] = i+1;
    REP(i, N) {
        swap(c[i%5], c[i%5+1]);
    }
    REP(i, 6) cout << c[i];
    cout << endl;
}

Submission #1024949 - AtCoder Beginner Contest 004 | AtCoder

D問題

dp[pos][remain]を「0からposまでの箱を使ってマーブルを配置したときに必要な最小の移動数」として動的計画法を行う（ただしposは-400を0とするようにずらしてある）

  • 初期化はdp[i][R+G+B]=0、その他は大きい数。
  • 漸化式はdp[i][j] = min(dp[i-1][j], dp[i-1][j+1] + cost(i, j))。（コメントの指摘を受けて修正しました）
  • cost(i, j)はj個残っているときにi番目の箱に入れるための最小の移動数を表す。左から順に入れているので、残りの数によってどの色を入れるのが移動数最小になるのかは一意に定まり、その色の箱の位置とposの差の絶対値が移動量になる。
#include <bits/stdc++.h>
 
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
typedef long long int ll;
using namespace std;
 
int R, G, B;
int dp[1000][1000]; // dp[pos][remain] = number of move
 
int cost(int pos, int remain) {
    if(remain >= G+B) return abs(400-pos);
    else if(remain >= B) return abs(500-pos);
    else return abs(600-pos);
}
 
int main(void) {
    cin >> R >> G >> B;
    int total = R + G + B;
    REP(i, 1000) REP(j, 1000) dp[i][j] = 1e9;
    REP(i, 1000) dp[i][total] = 0;
    FOR(i, 1, 1000) {
        REP(j, total) {
            dp[i][j] = min(dp[i-1][j], dp[i-1][j+1] + cost(i, j));
        }
    }
    int ans = 1e9;
    REP(i, 1000) {
        ans = min(ans, dp[i][0]);
    }
    cout << ans << endl;
}

Submission #1024931 - AtCoder Beginner Contest 004 | AtCoder