AtCoder Beginner Contest 267

OKU

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}$$を追加から来るからその最大値を入れる

なるほど

この記事が気に入ったらサポートをしてみませんか？