ABCノート [ABC091~100]

はじめに

このあいだの土曜日にABC初参加しました。ので、今後リアルタイムで参加したABCのノートを随時こちらにまとめていきます。ある程度溜まったところで新しい記事に移ります。[リアルタイムか否かよりも普通にナンバリングに沿ってノート作った方がわかりやすそうなのでタイトル変更しました。]　別解は僕の解答ではなく、解説だったり他の方の解答だったりします。アドバイス等大歓迎です。

096

解説

B – Maximum Sum

別解

#include <iostream>  
#include <algorithm>  
int A, B, C, K;  
int main() {  
  std::cin >> A >> B >> C >> K; std::cout << A + B + C + std::max({ A, B, C }) * ((1 << K) - 1) << '\n';  
  return 0;  
} 

std::max({a, b, c})

こんなのあったのか…

左シフト演算子 <<

左シフト演算子では、shift-expression のビットを、additive-expression で指定されたビット数だけ左にシフトします。 シフト演算により空いたビット位置はゼロで埋められます。 左シフトは論理シフトです (符号ビットを含めてシフトし、溢れたビットは捨てます)。

https://msdn.microsoft.com/ja-jp/library/336xbhcz.aspx#Anchor_0

C – Grid Repainting 2

解答

#include <iostream>  
#include <string>  
using namespace std;  

int h,w;  

int main() {  

cin >> h >> w;  
string s[h];  
for (int i = 0; i < h; i++) cin >> s[i];  

bool ok = false;  
for (int i = 0; i < h; i++) {  
  for (int j = 0; j < w; j++){  
    ok = false;  
    if(s[i][j] == '#') {  
      if((i > 0 && s[i-1][j] == '#') or 
         (i < h-1 && s[i+1][j] == '#') or 
         (j > 0 && s[i][j-1] == '#') or 
         (j < w-1 && s[i][j+1] == '#')) 
           ok = true;  

      if (!ok) { 
        cout << "No"; exit(0); 
      }  
    }  
  } 
} 
  cout << "Yes"; 
} 

別解

#include <iostream>  
using namespace std;  

char c[55][55]; int H, W, cnt;  

int main() {  

  cin >> H >> W;  
  for (int i = 1; i <= H; i++) {         
    for (int j = 1; j <= W; j++)  
      cin >> c[i][j];  
  }  

  for (int i = 1; i <= H; i++) {         
    for (int j = 1; j <= W; j++) {  
      if (c[i][j] == '#' && c[i][j - 1] != '#' && c[i - 1][j] != '#' && c[i][j + 1] != '#' && c[i + 1][j] != '#')  
        cnt++;  
    } 
  }  

if (cnt == 0) cout << "Yes" << endl;  
else cout << "No" << endl;  

return 0;  
} 

最後にcntで判定する方法は覚えておきたい。

D – Five, Five Everywhere

解答

選んだ５個の和が合成数かどうかの確認で躓いた。

#include <iostream>

using namespace std;

bool isPrime(int n){
  for(i = 2; i <= n / 2; ++i){
      if(n % i == 0){
          return false;
      }
  }
  return true;
}

int N;
int main() {
  cin >> N;
  int a[N];
  for(int i = 0; i < N; i++) {
    for(int n = i > 0 ? 2 : a[i-1]; n <= 55555; n++){
      if(isPrime(n)) a[i] = n;
      if(i > 4){
        for(int j = 4; j <= i; j++)
      }
    }
  }
}

別解

割れる、割れないの話なんだからmod忘れないようにしないと。

#include <iostream>
using namespace std;

bool isprime(int p) {
    if (p == 1) return false;
    for (int i = 2; i < p; i++) {
        if (p%i == 0) return false;
    }
    return true;
}

int n;

int main() {
    cin >> n;
    for (int i = 31; i <= 55555; i += 30) {
        if (isprime(i) == true) {
            if (i != 31) cout << " ";
            cout << i; n--;
        }
        if (n == 0) break;
    }
    cout << endl;
    return 0;
}

試しに
for (int i = 11; i <= 55555; i += 5)
で提出したら通った。31スタートでも変わらないのは良いとして、なぜ　i+=30　だったんだろう。そっちの方が素数早く揃うのかな。

095

C - Half and Half

自分の解答

#include <iostream>
using namespace std;

int a, b , c , x ,y;

int main() {
  cin >> a >> b >> c >> x >> y;
  int total = 0;
  if (a + b > c * 2) {
    if (x > y) {
      if (a > c * 2) {
        total = c * x * 2;
      }
      else {
        total = c * y * 2+ a * (x - y);
      }
    } else {
      if ( b > c * 2) {
        total = c * y * 2;
      } else {
        total = c * x * 2+ b * (y - x);
      }
    }
  } else {
   total = a * x + b * y; 
  }
  cout << total;
}

別解

Taka0310さんより。上のifたちをまとめるとこうなるのか、、
A,B,Cの値段によって買い方のパターンが3つあってそれらのうち最も安くすむ値段を出力する。

(AとBをそれぞれx、y枚ずつ買った値段) v.s. (Cを2*max(x,y)枚買った値段)
v.s.
Cをmin(x,y)*2枚 + AあるいはBでより注文が多い方をCで足りない分買った値段

#include <iostream>
using namespace std;
int a, b, c, x, y, r;
int main() {
  cin >> a >> b >> c >> x >> y;
  cout << min(min(a*x+b*y, c*2*max(x,y)), min(x,y)*2*c+abs(x-y)*(x>y?a:b));
  return 0;
}

D - Static Sushi

自分の解答

初見でむりだったので解答のやり方で実装しようと３時間粘ってようやく解けたと思ったら公開テストケースの中で4つ目のみWAになって心が折れた。諦めて他の方の解答見て虚無感に包まれた。。つらい。。。

#include <iostream>
#include <vector>
#include <numeric>
using namespace std;
#define ll long long

ll N, C;
vector<ll> xs(1,0), vs(1,0); // reserve the first element for the start pos

int main() {
  cin >> N >> C;
  ll x, v;
  vector<ll> f(1,0) ,g(1,0);
  while (cin>>x){
    xs.push_back(x);
    cin >> v;
    vs.push_back(v);
    f.push_back(accumulate(vs.begin(), vs.end(),0) - x);
    if(g.size()>0) g.push_back(max(g.back(),f.back()));
    else g.push_back(f[0]);
  }
  ll ans = g.back(); // when B = O
  for(int b = N; b > 0; b--){
    ll sub = accumulate(vs.rbegin(), vs.rbegin()+N-b+1,0) - 2*(C-xs[b]); // -2OB
    ans = max(ans, g[b-1] + sub);
  } 

  g = f = vector<ll>(N+2,0);
  for(int b = 0; b < N; b++) {
    f[N-b] = accumulate(vs.rbegin(), vs.rbegin()+b+1,0);
    g[N-b] = max(g[N-b+1], f[N-b]-C+xs[N-b]);
  }
  ll anscw = g[1]; // when A = O
  for(int a = 1; a < N+1; a++){
    ll subcw = accumulate(vs.begin(), vs.begin()+a+1,0) - 2*xs[a]; // -2OA
    anscw = max(anscw, g[a+1] + subcw);
  } 

  cout << max(ans,anscw) << endl;
}

別解

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=100010;
int n;
long long c,mx,x[maxn],v[maxn],a[maxn],b[maxn];
int main()
{
    cin>>n>>c;
    for(int i=1;i<=n;i++)
    {
        cin>>x[i]>>v[i];
        a[i]=a[i-1]+x[i-1]-x[i]+v[i];
    }
    x[n+1]=c;
    for(ll i=n;i>=1;i--)b[i]=b[i+1]+x[i]-x[i+1]+v[i];
    for(int i=2;i<=n;i++)a[i]=max(a[i],a[i-1]);
    for(int i=n-1;i>=1;i--)b[i]=max(b[i],b[i+1]);
    for(int i=1;i<=n;i++)
    {
        mx=max(mx,a[i]),mx=max(mx,b[i]);
        mx=max(mx,a[i]-x[i]+b[i+1]);
        mx=max(mx,b[i]-(c-x[i])+a[i-1]);
    }
    printf("%lld\n",mx);
    return 0;
}