AtCoder Beginner Contest 267
https://atcoder.jp/contests/abc267
結果
A - Saturday:AC(3:09)
B - Split?:AC(84:33)
C - Index × A(Continuous ver.):WA,TLE
D - Index × A(Not Continuous ver.):提出無し
A - Saturday
月~金の曜日が与えられ、それが土曜日まであと何日かを求める問題
自分の回答
int main() {
string S;
cin >> S;
if(S == "Monday"){
printf("5\n");
}
else if(S == "Tuesday"){
printf("4\n");
}
else if(S == "Wednesday"){
printf("3\n");
}
else if(S == "Thursday"){
printf("2\n");
}
else {
printf("1\n");
}
}
入力が5種類のみで答えと一対一対応してるため全パターン書いて終わり
公式解説
同じため省略
B - Split?
$${i}$$番目のボウリングのピンが倒れているとき$${i}$$桁目が0、立っているとき1として表わされる10ビットのビット列が与えられ、それがスプリットかを判別する問題
自分の回答
int main() {
string S;
cin >> S;
if(S[0] == '1'){
printf("No\n");
}
else{
bool retu[7];
S[6] == '0' ? retu[0] = 0 : retu[0] = 1;
S[3] == '0' ? retu[1] = 0 : retu[1] = 1;
S[1] == '0' && S[7] == '0' ? retu[2] = 0 : retu[2] = 1;
S[4] == '0' ? retu[3] = 0 : retu[3] = 1;
S[2] == '0' && S[8] == '0' ? retu[4] = 0 : retu[4] = 1;
S[5] == '0' ? retu[5] = 0 : retu[5] = 1;
S[9] == '0' ? retu[6] = 0 : retu[6] = 1;
for(int i = 0; i < 5; i++){
if(retu[i] == 1){
for(int j = i + 1; j < 6; j++)
if(retu[j] == 0){
for(int k = j + 1; k < 7; k++){
if(retu[k] == 1){
printf("Yes\n");
goto OUT;
}
}
}
}
}
printf("No\n");
}
OUT:;
}
まず前提として1番が倒れているかを判定
その後各列ごとに立っているピンがあるなら1、無いなら0となる配列を作成
そしてその配列を1番目から順番に見て行って101の並び(0は間にいくつあってもいい)が存在するかを判定
最後の判定の部分もっときれいにできた気はするんだけど
あと書いててなんかおかしいなと思ったら2回目のforの{}忘れてるやん
公式解説
int main(){
string s;
cin >> s;
if(s[0]=='1'){cout << "No\n";return 0;}
vector<int> line={4,3,5,2,4,6,1,3,5,7};
set<int> pln;
for(int i=0;i<10;i++){
if(s[i]=='1'){pln.insert(line[i]);}
}
if(pln.empty()){cout << "No\n";return 0;}
int mn=(*pln.begin()), mx=(*pln.rbegin());
if(mx-mn+1 != pln.size()){cout << "Yes\n";}
else{cout << "No\n";}
return 0;
}
https://atcoder.jp/contests/abc267/editorial/4740より
何番目の列にピンが立っているかをsetに入れ、setは自動で昇順になるためmnに最小値、mxに最大値が入り、mx-mn+1がmn番目からmx番目までのすべての列にピンが立っているときのplnの要素数になる
そしてplnの要素数とmx-mn+1が異なるならば間にピンが立っていない列が存在する
なるほど
C - Index × A(Continuous ver.)
長さ$${N}$$の整数列$${A=(A_{1},A_{2},…,A_{N})}$$が与えられ、そこから連続する$${M}$$個を取り出した数列$${B=(B_{1},B_{2},…,B_{M})}$$に対する$${\displaystyle\sum_{i=1}^{M}i×B_{i}}$$の最大値を求める問題
自分の回答
良い方法が思いつかなかったため愚直に全パターン調べる方法で書いたが、まあTLEした
あと答えが負となる場合を見逃したのと、オーバーフローの仕様をしっかり理解していなかったのでWAも出た
公式解説
int main(){
int n,m;
cin>>n>>m;
vector<long long> a(n);
for(int i=0;i<n;i++) cin>>a[i];
vector<long long> sum(n+1);//sum[i] = a_1 + a_2 + ... + a_{i-1}
for(int i=1;i<=n;i++) sum[i]=sum[i-1]+a[i-1];
vector<long long> sumi(n-m+1);
long long now=0;
for(int i=0;i<m;i++) now+=a[i]*(i+1);
sumi[0]=now;
for(int i=1;i<n-m+1;i++) sumi[i]=sumi[i-1]+m*a[m+i-1]-(sum[m+i-1]-sum[i-1]);
long long ans = -1000000000000000000ll;
for(int i=0;i<n-m+1;i++) ans=max(ans,sumi[i]);
cout<<ans<<endl;
}
https://atcoder.jp/contests/abc267/editorial/4727より
総当たりは必須だが、計算回数を減らしたいから最初の$${M}$$個での値を求めてその値を利用できないか、
つまり
$${\displaystyle\sum_{i=1}^{M}i×A_{i+1}=\displaystyle\sum_{i=1}^{M}i×A_{i}+X}$$
のような形で求められないかを考える
$${\displaystyle\sum_{i=1}^{M}i×A_{i+1}-\displaystyle\sum_{i=1}^{M}i×A_{i}}$$
は開くと
$${(1×A_{2}-1×A_{1})+\\(2×A_{3}-2×A_{2})+\\(3×A_{4}-3×A_{3})+\\…\\(M×A_{M+1}-M×A_{M})}$$
なため
$${A_{1}(-1)+A_{2}(1-2)+A_{3}(2-3)+…+A_{M}((M-1)-M)+M×A_{M+1}}$$
となり
$${-\displaystyle\sum_{i=1}^{M}A_{i}+M×A_{M+1}}$$
になる、これが最初に挙げた式のXにあたるため
$${\displaystyle\sum_{i=1}^{M}i×A_{i+1}=\displaystyle\sum_{i=1}^{M}i×A_{i}-\displaystyle\sum_{i=1}^{M}A_{i}+M×A_{M+1}}$$
で動的計画法の要領で全て求められる
計算量は$${\displaystyle\sum_{i=1}^{M}A_{i}}$$を前もって計算して記録しておけば上の式自体は$${Ο(1)}$$なため全て求めるのに$${Ο(N)}$$で終わる
なるほど、これは思いつかんわ
D - Index × A(Not Continuous ver.)
長さ$${N}$$の整数列$${A=(A_{1},A_{2},…,A_{N})}$$が与えられ、そこから順番通りに$${M}$$個取り出した数列(連続でなくてよい)$${B=(B_{1},B_{2},…,B_{M})}$$に対する$${\displaystyle\sum_{i=1}^{M}i×B_{i}}$$の最大値を求める問題
自分の回答
ちょっと覗いた程度だけど手がかりすら掴めなかった
公式解説
long long dp[2001][2001];
int main(){
int n,m;
cin>>n>>m;
vector<long long> a(n);
for(int i=0;i<n;i++) cin>>a[i];
dp[0][0]=0;
dp[0][1]=-1000000000000000000ll;
for(int i=1;i<=n;i++){
for(int j=0;j<=n;j++){
if(j==0) dp[i][0]=0;
else if(j>i) dp[i][j]=-1000000000000000000ll;
else dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]+a[i-1]*j);
}
}
cout<<dp[n][m]<<endl;
}
https://atcoder.jp/contests/abc267/editorial/4728より
$${A_{i}}$$までで$${j}$$個選んだ時の最大値で動的計画法か
dp[i][j]にはdp[i-1][j]から追加無しとdp[i-1][j-1]に$${A_{i}×j}$$を追加から来るからその最大値を入れる
なるほど
この記事が気に入ったらサポートをしてみませんか?