はじめに
- AtCoder Beginner Contestの過去問の解法及び提出したソースコードをまとめています。
- 基本的に自分が振り返ることを目的としておりますが、誤りや気になった点、その他質問等もお待ちしておりますので遠慮なくお願いします。
コンテストページ
A問題
３つのうちの小さい方から２つを足し合わせた値が解です。
３つの合計から３つのうちもっとも大きいものを引いてあげると実装がスッキリします。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int p,q,r;
cin >> p >> q >> r;
cout << p + q + r - max({p,q,r}) << endl;
return 0;
}
B問題
区切り点を移動させて全探索します。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
vector<int> w(n);
for(int i = 0; i < n; i++) cin >> w[i];
int ans = INT32_MAX;
for(int i = 0; i < n; i++){
int s1 = accumulate(w.begin(), w.begin() + i, 0);
int s2 = accumulate(w.begin() + i, w.end(), 0);
ans = min(ans, abs(s1-s2));
}
cout << ans << endl;
return 0;
}
C問題
１つ前と２つ前の段への移動方法の合算がその段への移動方法パターン数です。
また0段目への行き方は1通り、壊れている段への移動方法は0通りと考えます。
段が壊れているかどうかの判定はunordered_setに予め壊れている段を入れておき確認できるようにしています。
#include <bits/stdc++.h>
using namespace std;
int main()
{
const int MOD = 1000000007;
int n,m;
cin >> n >> m;
unordered_set<int> a;
vector<int> dp(n+1, 0);
dp[0] = 1;
for(int i = 0; i < m; i++){
int tmp;
cin >> tmp;
a.insert(tmp);
}
int ans = 0;
for(int i = 1; i <= n; i++){
if(a.count(i)) continue;
if(a.count(i-1) == 0) dp[i] += dp[i-1];
if(a.count(i-2) == 0) dp[i] += dp[i-2];
dp[i] %= MOD;
}
cout << dp[n] << endl;
return 0;
}
D問題
全てのマスの上下左右方向への空きマス数(そのマスを含む)を別々に計算します。
求め方は愚直にやるとO(HW(H+W))となり間に合いませんが、以下のようにすることでそれぞれO(HW)で求まります。
- 上方向への空きマス数(u) = 上隣のマスの左方向への空きマス数 + 1
- 下方向への空きマス数(d) = 下隣のマスの左方向への空きマス数 + 1
- 左方向への空きマス数(l) = 左隣のマスの左方向への空きマス数 + 1
- 右方向への空きマス数(r) = 右隣のマスの左方向への空きマス数 + 1
最後に全てのマスの全方向への空きマス数を求めますが、別々に計算した上下左右方向の空きマス数は自マスを重複して数えているため(u+d+l+r)を-3する必要があります。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int h,w;
cin >> h >> w;
vector<string> s(h);
for(int i = 0; i < h; i++) cin >> s[i];
vector<vector<int>> l(h, vector<int>(w));
vector<vector<int>> r(h, vector<int>(w));
vector<vector<int>> u(h, vector<int>(w));
vector<vector<int>> d(h, vector<int>(w));
for(int i = 0; i < h; i++){
for(int j = 0; j < w; j++){
if(s[i][j] == '#') l[i][j] = 0;
else if(j==0) l[i][j] = 1;
else l[i][j] = l[i][j-1] + 1;
}
}
for(int i = 0; i < h; i++){
for(int j = w-1; j >= 0; j--){
if(s[i][j] == '#') r[i][j] = 0;
else if(j==w-1) r[i][j] = 1;
else r[i][j] = r[i][j+1] + 1;
}
}
for(int i = 0; i < h; i++){
for(int j = 0; j < w; j++){
if(s[i][j] == '#') u[i][j] = 0;
else if(i==0) u[i][j] = 1;
else u[i][j] = u[i-1][j] + 1;
}
}
for(int i = h-1; i >= 0; i--){
for(int j = 0; j < w; j++){
if(s[i][j] == '#') d[i][j] = 0;
else if(i==h-1) d[i][j] = 1;
else d[i][j] = d[i+1][j] + 1;
}
}
int ans = 0;
for(int i = 0; i < h; i++){
for(int j = 0; j < w; j++){
ans = max(ans, l[i][j] + r[i][j] + u[i][j] + d[i][j] - 3);
}
}
cout << ans << endl;
return 0;
}