ABC 004
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