ABC165自分なりのまとめ

A-We Love Golf

めんどくさいので、a~bの範囲で全探索

//競技プログラミング用のテンプレート
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <string>
#include <math.h>
#include <stack>

#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define repr(i, n) for(int i = n - 1; i >= 0; i--)

using namespace std;
using ll = long long int;
using p = pair<int, int>;
using pl = pair<ll, ll>;
using v = vector<int>;
using vd = vector<double>;
using vs = vector<string>;
using vl = vector<ll>;

int main()
{
  int a, b, k;
  cin >> k >> a >> b;
  for(int i = a; i <= b; i++)
  {
    if(i % k == 0) 
    {
      cout << "OK" << endl;
      return 0;
    }
  }
  cout << "NG" << endl;
}

B-1%

サンプルからシミュレーションできることが分かるので、やる

//競技プログラミング用のテンプレート
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <string>
#include <math.h>
#include <stack>

#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define repr(i, n) for(int i = n - 1; i >= 0; i--)

using namespace std;
using ll = long long int;
using p = pair<int, int>;
using pl = pair<ll, ll>;
using v = vector<int>;
using vd = vector<double>;
using vs = vector<string>;
using vl = vector<ll>;

int main()
{
  ll x;
  cin >> x;
  ll start = 100;
  int need = 0;
  while(start < x) {
    need++;
    start = start * 0.01 + start;
  }
  cout << need << endl;
}

C-Many Requirements

広義単純増加列はそんなに数がないので、愚直に全探索

//競技プログラミング用のテンプレート
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <string>
#include <math.h>
#include <stack>
#include "unistd.h"

#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define repr(i, n) for(int i = n - 1; i >= 0; i--)

using namespace std;
using ll = long long int;
using p = pair<int, int>;
using pl = pair<ll, ll>;
using v = vector<int>;
using vd = vector<double>;
using vs = vector<string>;
using vl = vector<ll>;


int n, m, q;
int a[50], b[50], c[50], d[50];
int result = 0;
map<v, int> memo;

bool isValid(v &target) {
  rep(i, n - 1) {
    if(target[i] > target[i + 1]) return false;
  }
  if(target[n- 1] > m) return false;
  return true;
}

void dfs(v &target) {
  if(isValid(target)) {
    if(memo.count(target)) return;
    memo[target] = 1;
    int point = 0;
    rep(i, q) {
      if(target[b[i] - 1] - target[a[i] - 1] == c[i]) point += d[i];
    }
    result = max(result, point);
    rep(i, n) {
      v temp = target;
      temp[i]++;
      dfs(temp);
    }
  }
}

int main()
{
  cin >> n >> m >> q;
  rep(i, q) {
    cin >> a[i] >> b[i] >> c[i] >> d[i];
  }
  v start(n, 1);
  dfs(start);
  cout << result << endl;
}

D-Floor Function

floor(Ax/B)の部分は、x/Bの商とあまりの部分にAを掛けたものの和以下の最小の整数
floor(x/B) * Aの部分は、x/Bの商にAを掛けたもの
x/Bの商の部分に関しては、floor(Ax/B), floor(x/B) * Aで共通であるため
floor(Ax/B) - floor(x/B) * Aで残るのは、あまりの部分にAを掛けたものだけです
あまりなので、取りうる範囲は0~B - 1です。
また、あまりが大きくなればなるほど掛けた結果も大きくなるので、
BがN以下の場合はB - 1を、BがNより大きい場合はNをそれぞれxとして計算し出力すれば良いです。

//競技プログラミング用のテンプレート
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <string>
#include <math.h>
#include <stack>

#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define repr(i, n) for(int i = n - 1; i >= 0; i--)

using namespace std;
using ll = long long int;
using p = pair<int, int>;
using pl = pair<ll, ll>;
using v = vector<int>;
using vd = vector<double>;
using vs = vector<string>;
using vl = vector<ll>;

int main()
{
  ll a, b, n;
  cin >> a >> b >> n;
  if(b <= n) {
    cout << (a * (b - 1)) / b << endl;
  } else {
    cout << (a * (n)) / b << endl;
  }
}

E-Rotation Matching

自分の中で考えをまとめ中

//競技プログラミング用のテンプレート
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <string>
#include <math.h>
#include <stack>

#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define repr(i, n) for(int i = n - 1; i >= 0; i--)

using namespace std;
using ll = long long int;
using p = pair<int, int>;
using pl = pair<ll, ll>;
using v = vector<int>;
using vd = vector<double>;
using vs = vector<string>;
using vl = vector<ll>;

int main()
{
  int n, m;
  cin >> n >> m;
  vector<pair<int, int>> t(m, {0, 0});
  if(n % 2 != 0) {
    int l = 1;
    int r = n - 1;
    for(int i = 0; i < m; i++)
    {
      t[i] = {l, r};
      l++;
      r--;
    }
  }else{
    bool flag = false;
    int l = 1;
    int r = n;
    for(int i = 0; i < m; i++)
    {
      if(!flag && r - l <= n / 2) {
        r--;
        flag = true;
      }
      t[i] = {l, r};
      l++;
      r--;
    }
  }
  for(auto e : t) {
    cout << e.first << " " << e.second << endl;
  }
}