AtCoder Beginner Contest #37

問題A：饅頭

あなたはとにかく沢山の個数を食べたいので、種類は気にせず、なるべく多くの個数の饅頭を買おうと思っています。 2 種類で買う個数が違ったり、片方の種類しか買わなかったりしてもかまいません。

と書いてあるので、Cをmin(A,B)で割ることで求められる。

#include <iostream>
#include <algorithm>

using namespace std;

int main(){
  int a,b,c;
  cin >> a >> b >> c;
  cout << c/min(a,b) << endl;
}

問題B：編集

問題文通りに実装した。置換する範囲が、[l,r]であることに注意する。

#include <iostream>

using namespace std;

int d[101];

int main(){
  int n,q;

  cin >> n >> q;
  for(int i = 0 ; i < q ; i++){
    int l, r, t;
    cin >> l >> r >> t;
    for(int j = l-1; j < r ; j++) d[j] = t;
  }
  for(int i = 0 ; i < n ; i++){
    cout << d[i] << '\n';
  }
}

問題C：総和

問題文通りに実装すると、計算量が多くTLEする。今回はしゃくとり法を用いて実装した。

#include <iostream>
#include <cstdio>

using namespace std;


int main(){
  long long in[100001];

  int n, k;
  scanf("%d %d", &n, &k);
  
  for(int i = 0 ; i < n ; i++){
    scanf("%llu", &in[i]);
  }
  
  long long ans=0;
  for(int i = 0 ; i < k ; i++) ans += in[i];

  long long tmp=ans;
  for(int i = 0 ; i < n-k ; i++){
    tmp = (tmp + in[k+i] - in[i]);
    ans += tmp;
  }

  printf("%llu\n",ans);
}

問題D：経路

dfsした。

#include <iostream>
#include <cstring>

using namespace std;

int dh[]={-1, 1, 0, 0};
int dw[]={0, 0, 1, -1};
int h, w;

#define rep(i,n) for(int i = 0 ; i < n ; i++)
#define MOD 1000000007

int field[1001][1001];
int memo[1001][1001]; 

long long int solve(int _h, int _w){
  long long int res=1;
  
  if(memo[_h][_w]>0) return memo[_h][_w];

  rep(i,4){
    int nh = _h + dh[i]; int nw = _w + dw[i];
    if(0 <= nh && nh < h && 0 <= nw && nw < w && field[nh][nw]>field[_h][_w]){
      res += solve(nh, nw);
    }
  }
  
  return memo[_h][_w]=res%MOD;
}

int main(){
  cin >> h >> w;
  rep(i,h){
    rep(j, w){
      cin >> field[i][j];
    }
  }
  long long int sum=0;
  memset(memo, 0, sizeof(memo));
  rep(i,h){
    rep(j,w){
      sum += solve(i,j);
    }
    sum %= MOD;
  }
  cout << sum%MOD << endl;
}