ABC002 + ARC073

ABC002 C問題


C: 直訴 - AtCoder Beginner Contest 002 | AtCoder

これは解き方を知らなければ、四角で三角を囲って周りにできた4つの三角の面積を四角から引くという面倒くさい事をしなければならない問題だがググればすぐにでてくる
解いてる途中は気づかなかったがご丁寧にヒントまで書いてあった

ヒント
3 点 (0,0), (a,b), (c,d) で構成される三角形の面積は、|ad−bc|⁄2 となります。

つまり一つの頂点を (0, 0) までもってきてその差分を他の点からも引けば良い
しかし問題はそこではなくデフォルトの出力フォーマットでは求める出力ができない点にある

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
 
#define pb push_back
#define rep(i, a, n) for(int i = (a); i < (n); i++)
#define dep(i, a, n) for(int i = (a); i >= (n); i--)
 
__attribute__((constructor))
void initial() {
  cin.tie(0);
  ios::sync_with_stdio(false);
}
 
int main() {
  double x, y, x2, y2, x3, y3;
  cin >> x >> y >> x2 >> y2 >> x3 >> y3;
 
  cout << fixed << fabs(((x2 - x) * (y3 - y)) - ((x3 - x) * (y2 - y))) / 2 << endl;
}

ABC002 D問題


D: Widespread - AtCoder Regular Contest 075 | AtCoderD: 派閥 - AtCoder Beginner Contest 002 | AtCoder


一見難しそうな問題文ではあるが入力がすごく小さいので全探索でどうにかなる
一人目から順番に派閥に入れるか入れないかの分岐を行い、入れる場合はすでに派閥に入っている人間と知り合いであるかを探索する

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
 
#define pb push_back
#define rep(i, a, n) for(int i = (a); i < (n); i++)
#define dep(i, a, n) for(int i = (a); i >= (n); i--)
 
__attribute__((constructor))
void initial() {
  cin.tie(0);
  ios::sync_with_stdio(false);
}
 
int n, m, max_s = 0;
vector<vector<int> > kan(13, vector<int>(13));
 
int saiki(int i, vector<int> hi) {
  if(i == n) {
    max_s = max(max_s, (int)hi.size());
    return 0;
  }
  saiki(i + 1, hi);
  rep(j, 0, hi.size()) if(!kan[i][hi[j]]) return 0;
  hi.pb(i);
  saiki(i + 1, hi);
}
 
int main() {
  cin >> n >> m;
  int a, b;
 
  if(m == 0) {
    cout << 1 << endl;
    return 0;
  }
 
  rep(i, 0, m) {
    cin >> a >> b;
    kan[a - 1][b - 1] = 1;
    kan[b - 1][a - 1] = 1;
  }
 
  vector<int> hi;
  saiki(0, hi);
  cout << max_s << endl;
}

ARC075 C問題

C: Sentou - AtCoder Regular Contest 073 | AtCoder

前回スイッチを押した時間(x)とお湯が出た時間(y)を覚えておいて、x + お湯が出続ける時間(t) を次のスイッチを押した時間と比較し、小さければその差が得られる予定だったお湯の量なのでその値を y から引く
その後 y に t をプラスする

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
 
#define pb push_back
#define rep(i, a, n) for(int i = (a); i < (n); i++)
#define dep(i, a, n) for(int i = (a); i >= (n); i--)
 
__attribute__((constructor))
void initial() {
  cin.tie(0);
  ios::sync_with_stdio(false);
}
 
int main() {
  ll n, t, a, z = 0, ans;
  cin >> n >> t >> a;
  ans = t;
  rep(i, 1, n) {
    cin >> a;
    if(z + t > a) ans -= z + t - a;
    ans += t;
    z = a;
  }
  cout << ans << endl;
}

ARC075 D問題

D: Simple Knapsack - AtCoder Regular Contest 073 | AtCoder

超有名問題なので説明は省略
しかしネット情報を鵜呑みにすると w の上限が10 ^ 9 なので二次元配列が確保できないところにひっかかる
今回の場合は連想配列を用いる事でこの問題を回避できる

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

#define pb push_back
#define rep(i, a, n) for(int i = (a); i < (n); i++)
#define dep(i, a, n) for(int i = (a); i >= (n); i--)

__attribute__((constructor))
void initial() {
  cin.tie(0);
  ios::sync_with_stdio(false);
}

int n, w, mono[100][2];
map<int, int> memo[100];

int saiki(int i, int cost) {
  if(cost > w) return -10000000;
  if(i == n) return 0;
  if(memo[i].count(cost)) return memo[i][cost];
  return memo[i][cost] = max(saiki(i + 1, cost + mono[i][0]) + mono[i][1], saiki(i + 1, cost));
}

int main() {
  cin >> n >> w;
  rep(i, 0, n) {
    cin >> mono[i][0] >> mono[i][1];
  }

  cout << saiki(0, 0) << endl;
}