AtCoder Beginner Contest #61

問題はこちらから abc061.contest.atcoder.jp

問題A : Between Two Integers

#include <iostream>
 
using namespace std;
 
int main(){
  int a, b, c;
 
  cin >> a >> b >> c;
 
  cout << ((a <= c && c <= b)?"Yes":"No") << endl;
}

問題B : Counting Roads

#include<bits/stdc++.h>
 
#define rep(i, n) REP(i, 0, n)
#define REP(i, a, n) for(int i = a ; i < (int)n ; i++)
#define m0(x) memset(x, 0, sizeof(x))
 
using namespace std;
 
signed main(){
  int n, m;
  int field[51][51];
  int a, b;
  m0(field);
  
  cin >> n >> m;
 
  rep(i, m){
    cin >> a >> b;
    field[a][b]++;
    field[b][a]++;
  }
 
  REP(i, 1, n+1){
    int sum = 0;
    rep(j, n+1) sum += field[i][j];
    cout << sum << endl;
  }
 
}

問題C : Big Array

#include<bits/stdc++.h>
 
#define rep(i, n) REP(i, 0, n)
#define REP(i, a, n) for(int i = a ; i < (int)n ; i++)
 
using namespace std;
 
typedef long long ll;
 
ll cnt[100001];
 
signed main(){
  int n;
  ll k;
  int a, b;
 
  cin >> n >> k;
  
  rep(i, n){
    cin >> a >> b;
    cnt[a] += b;
  }
 
  REP(i, 1, 100001){
    if(k <= cnt[i]){
      cout << i << endl;
      break;
    }
    k -= cnt[i];
  }
 
}

問題D : Score Attack

普通のベルマンフォード書いてたくさんWAした. つらい.（コーナーケース思いつけなかった）

#include <iostream>
#include <vector>
 
using namespace std;
 
#define rep(i, n) REP(i, 0, n)
#define REP(i, a, n) for(int i = a ; i < (int)n ; i++)
#define pb push_back
#define N_MAX 1000
#define INF (1LL << 51)
 
typedef long long ll;
 
struct Edge{
  int from, to;
  ll cost;
  Edge(int f, int t, ll c) : from(f), to(t), cost(c) {}
};
 
int n, m;
vector<Edge> edges;
ll d[N_MAX+1];
 
bool bellman_ford(){
  rep(i, N_MAX+1) d[i] =-INF;
  d[0] = 0;
  rep(i, 2*n){
    for(auto &edge:edges){
      if(d[edge.from] != INF && d[edge.to] < d[edge.from] + edge.cost){
        d[edge.to] = d[edge.from] + edge.cost;
        if(i > n && edge.to == n-1) return true;
      }
    }
  }
  return false;
}
 
signed main(){
  int f, t;
  ll c;
  cin >> n >> m;
 
  rep(i, m){
    cin >> f >> t >> c;
    f--; t--;
    edges.emplace_back(f, t, c);    
  }
 
  if(bellman_ford()){
    cout << "inf" << endl;
  }else{
    cout << d[n-1] << endl;
  }
}

参考

最短経路問題（ベルマンフォード法・ワーシャルフロイド法） - アルゴリズム講習会