盆栽エンジニアリング日記

勉強したことをまとめるブログ

ABC170自分なりのまとめ

AtCoder C++ 競技プログラミング

A- Five Variables

順番に変数を読み込んでいって0で会った場所を出力すればよいです。

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

#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>;

//定数
const int intmax = numeric_limits<int>::max();
const ll llmax = numeric_limits<ll>::max();
const ll mod = 1e9 + 7;
const double pi = M_PI;

int main()
{
  rep(i, 5) {
    int x;
    cin >> x;
    if (x == 0) {
      cout << i + 1 << endl;
      return 0;
    }
  }
}

B- Crane and Turtle

鶴の数を固定してfor文を回せば良いです。

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

#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>;

//定数
const int intmax = numeric_limits<int>::max();
const ll llmax = numeric_limits<ll>::max();
const ll mod = 1e9 + 7;
const double pi = M_PI;

int main()
{
  int x, y;
  cin >> x >> y;
  for(int i = 0; i <= x; i++)
  {
    int reg = 2 * i + 4 * (x - i);
    if (reg == y) {
      cout << "Yes" << endl;
      return 0;
    }
  }
  cout << "No" << endl;
}

C- Forbidden List

p_iの範囲が1~100と狭いため、候補を全探索することを考えます。
問題文では負の整数についての言及がありますが、p_iの範囲から必ず0~101に解があることがわかります。
あとは、0~101の範囲の整数について、p_iに存在しないかを確かめながら絶対値が最小のものを探せばよいです。

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

#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>;

//定数
const int intmax = numeric_limits<int>::max();
const ll llmax = numeric_limits<ll>::max();
const ll mod = 1e9 + 7;
const double pi = M_PI;

int main()
{
  int x, n;
  cin >> x >> n;
  v p(n, 0);
  rep(i, n) {
    cin >> p[i];
  }
  int result = x;
  int num = 0;
  rep(i, 102) {
    bool exit = false;
    rep(j, n) {
      if (p[j] == i)  exit = true;
    }
    if (!exit) {
      if (result > abs(x - i)) {
        result = abs(x - i);
        num = i;
      }
    }
  }
  cout << num << endl;
}

D- Not Divisible

強引な解法で通してしまいました。
具体的には、A_iをmapで保存しておき、各A_iについて約数列挙を行い、その約数がA_iに存在しないかを判定しました。
計算量的には、O(N * sqrt(A_{max}))となり2 * 108なのでテストケースによっては間に合わない気がします。
運が良かったです。
想定解法はdpを使うようです。
公式のPDFがわかりやすいのでそちらを参照してください。
僕の解法のように、すべての約数を列挙する必要はないということですね。

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

#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>;

//定数
const int intmax = numeric_limits<int>::max();
const ll llmax = numeric_limits<ll>::max();
const ll mod = 1e9 + 7;
const double pi = M_PI;

map<int, int> memo;

bool check(int a) {
  for(int i = 2; i * i <= a; i++) {
    if (a % i == 0) {
      if (memo.count(i)) {
        return false;
      }
      if (memo.count(a / i)) {
        return false;
      }
    }
  }
  if (memo[a] != 1) return false;
  if (a != 1 && memo.count(1)) return false;
  return true;
}

int main()
{
  int n;
  cin >> n;
  v a(n, 0);
  rep(i, n) {
    cin >> a[i];
    memo[a[i]]++;
  }
  int count = 0;
  rep(i, n) {
    bool result = check(a[i]);
    if(result) count++;
  }
  cout << count << endl;
}

E- Smart Infants

コンテスト後にAC
基本的な方針としては、各幼稚園における最大値を保持しておき、転園時に転園元と転園先の最大値を更新し、最大値の最小値を取得することを考えます。
このときに必要になるのが、

  • 各幼稚園に所属している園児の降順リスト(レートについて)
  • 各幼稚園の最大値の最小値を取得する方法

です。
最初の要件についてはプライオリティキューを用いることで解決することができます。
プライオリティキューには、レートと園児の番号をペアにして入れておき、転園元の最大値の更新の際には、所属が変わっていない園児が手に入るまでキューをpopするような処理を行えば良いです。
転園先の最大値の更新は単純にプライオリティキューにpushするだけで良いです。
この操作はO(Q)回しか行われません。
2つめの要件については、各幼稚園の最大値を管理するセグメントツリーを用いることで解決できます。
以上を組み合わせることで解を高速に求めることができます。
コードが汚くてすみません。

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

#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>;

//定数
const int intmax = numeric_limits<int>::max();
const ll llmax = numeric_limits<ll>::max();
const ll mod = 1e9 + 7;
const double pi = M_PI;

int n;
int m;
int q;
int t = 2 * 100000;

//セグ木

const ll MAX_N = 1 << 20;

//セグメント木を持つグローバル配列
ll dat[2 * MAX_N - 1];

//初期化
void init_seg(int n_)
{
    //簡単のため、要素数を2のべき乗に
  m = 1;
    while(m < n_)
    {
        m *= 2;
    }
    //全ての値をINT_MAXに
    for (int i = 0; i < 2 * m -1; i++)
    {
        dat[i] = llmax;
    }
}

//k番目の値(0-indexed)をaに変更
void update(int k, ll a)
{
    //葉の節点
    k += m - 1;
    dat[k] = a;
    //登りながら更新
    while(k > 0)
    {
        k = (k - 1) / 2;
        dat[k] = min(dat[k * 2 + 1], dat[k * 2 + 2]);
    }
}

//[a, b)の最小値を求める
//後ろの方の引数は、計算の簡単のための引数
//kは節点の番号,l,rはその節点が[l, r)に対応づいていることを表す
//したがって外からはquery(a, b, 0, 0, n)として呼ぶ
ll query_(int a, int b, int k, int l, int r){
    //[a, b)と[l, r)が交差しなければ、INT_MAX
    if(r <= a || b <= l){ 
        return llmax;
    }

    //[a, b)が[l, r)を完全に含んでいれば、この節点の値
    if(a <= l && r <= b)
    {
        return dat[k];
    }else{
        //そうでなければ,2つの子の最小値
        ll vl = query_(a, b, k * 2 + 1, l, (l + r) / 2);
        ll vr = query_(a, b, k * 2 + 2, (l + r) / 2, r);
        return min(vl, vr);
    }
}

vl rates, belongs, emax;
vector<priority_queue<pl>> eq;

//初期化処理
void init() {
  cin >> n >> q;
  m = t;
  rates.resize(n, 0);
  belongs.resize(n, 0);
  emax.resize(t, -1);
  eq.resize(t);
}

//有効な園児が得られるまでキューから取り出す
void qpop(int school_num) {
  int next = eq[school_num].top().second;
  while(belongs[next] != school_num) {
    eq[school_num].pop();
    if (eq[school_num].empty()) break;
    next = eq[school_num].top().second;
  }
}

int main()
{
  //データの読み込み
  init();
  //セグ木の初期化
  init_seg(t);
  rep(i, n) {
    ll a;
    int b;
    cin >> a >> b; b--;
    rates[i] = a;
    belongs[i] = b;
    eq[b].push({a, i});
    emax[b] = max(emax[b], a);
    update(b, emax[b]);
  }
  vl result;
  //初期解の生成
  ll maxmin = query_(0, t, 0, 0, t);
  //転校処理
  rep(i, q) {
    int c, d;
    cin >> c >> d; c--; d--;
    //転校前の幼稚園
    int ex = belongs[c];
    //転校先の最大値の更新と解の更新
    belongs[c] = d;
    eq[d].push({rates[c], c});
    emax[d] = max(emax[d], rates[c]);
    update(d, emax[d]);
    maxmin = query_(0, t, 0, 0, t);
    //転校元の最大値の更新と解の更新
    if (eq[ex].top().second == c) {
      qpop(ex);
      if ( !eq[ex].empty() ) {
        emax[ex] = eq[ex].top().first;
        update(ex, emax[ex]);
      } else{
        emax[ex] = -1;
        update(ex, llmax);
      }
      maxmin = query_(0, t, 0, 0, t);
    }
    result.push_back(maxmin);
  }
  for (auto e : result) cout << e << endl;
}

ABC169自分なりのまとめ

AtCoder C++ 競技プログラミング

A- Multiplication 1

入力を受け取ってかけるだけです。

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

#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>;

//定数
const int intmax = numeric_limits<int>::max();
const ll llmax = numeric_limits<ll>::max();
const ll mod = 1e9 + 7;
const double pi = M_PI;

int main()
{
  int a, b;
  cin >> a >> b;
  cout << a * b << endl;
}

B- Multiplication 2

コンテスト中に解けず。。。
簡単な問題でWA出すとパニックになってしまうのなんとかしたいです
解法としては、Aiの中に0が1つでもあったら0を出力
ない場合には、オーバーフローに注意しながら計算して答えを出力するだけです。
オーバーフローの検知はresultを解を格納する変数、limitを解の上限とすると

  • result <= limit / Ai

でできます。(これが思いつかなかった。。。)

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

#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>;

//定数
const int intmax = numeric_limits<int>::max();
const ll llmax = numeric_limits<ll>::max();
const ll mod = 1e9 + 7;
const double pi = M_PI;
const ll limit = 1e18;

int main()
{
  int n;
  cin >> n;
  vl a(n, 0);
  rep(i, n) {
    cin >> a[i];
    if (a[i] == 0) {
      cout << 0 <<endl;
      return 0;
    }
  }
  ll result = 1;
  rep(i, n) {
    if (result <= limit / a[i]) {
      result *= a[i];
    } else {
      cout << -1 << endl;
      return 0;
    }
  }
  cout << result << endl;
}

C- Multiplication 3

これも解けなかった。。
今回のコンテストはひどかったです。
浮動小数点の誤差がテーマの問題です。
知識としては知っていても、コンテスト中に活用するのはできませんでした。
この記事で詳しく解説されています。
誤差を回避する方法としては、文字列で受け取って小数点の前と後で分割するのが無難らしいです。

//競技プログラミング用のテンプレート
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <string>
#include <math.h>
#include <stack>
#include <limits>
#include <stdlib.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>;

//定数
const int intmax = numeric_limits<int>::max();
const ll llmax = numeric_limits<ll>::max();
const ll mod = 1e9 + 7;
const double pi = M_PI;

int main()
{
  ll a;
  string b;
  cin >> a >> b;
  int temp = b[0] - '0';
  int temp2 = stoi(b.substr(2, 2));
  cout << a * temp + (a * temp2) / 100 << endl;
}

D- Div Game

解けた。
体感、B,Cよりも簡単です。
任意の数は素数の積で表せます。
よって、素因数分解をして各素因数に対して同じ冪の肩を選ばないように何回操作を行えるかを数えていけば良いです。

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

#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>;

//定数
const int intmax = numeric_limits<int>::max();
const ll llmax = numeric_limits<ll>::max();
const ll mod = 1e9 + 7;
const double pi = M_PI;

vl dc(ll n) {
  vl result;
  for(ll i = 2; i * i <= n; i++) {
    while( n % i == 0 ) {
      result.push_back(i);
      n = n / i;
    }
  }
  if(n > 1) {
    result.push_back(n);
  }
  return result;
}

ll calc(ll n) {
  ll start = 1;
  ll sum = 0;
  int count = 0;
  while(sum < n) {
    sum += start;
    if(sum > n) break;
    start++;
    count++;
  }
  return count;
}

int main()
{
  ll n;
  cin >> n;
  vl cand = dc(n);
  cand.push_back(0);
  int count = 1;
  int total = 0;
  for(int i = 0; i < cand.size() - 1; i++) {
    if(cand[i] == cand[i + 1]) {
      count++;
    }else{
      total += calc(count);
      count = 1;
    }
  }
  cout << total << endl;
}

E- Count Median

コンテスト後に考えてたけど解けませんでした。
解説呼んだ後のなるほど感がすごい。
最初にNが奇数の場合を考えます。 まず、各Xiで取りうる一番小さい数(Ai)を選んだとします。
この時の中央値をAmとします。 次に、反対にXiで取り得る一番大きい数(Bi)を選んだとします。 この時の中央値をBmとします。 実は、Am~Bmの範囲すべてを中央値とすることができます。 証明は以下のような感じでできるはずです。

  • ベースケース
  • Amが中央値となるようなケースで、Amを取る項に1加算できるならAm + 1が中央値となるようなケースを作ることができる
  • もしAm + 1 > Bならば、Am + 1を取ることができる任意の項をAm + 1とすることでAm + 1を中央値とすることができる
  • 数学的帰納法の仮定
  • Am + 1 < x < Bmが中央値となるようなケースを作ることができる
  • 帰納ステップ
  • xが中央値ならばベースケースと同様にx + 1を中央値とするようなケースを作ることができる。

偶数の場合は、中央値をx(N / 2) + x((N / 2) + 1)とすると奇数の場合と同様に求めることができます。

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

#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>;

//定数
const int intmax = numeric_limits<int>::max();
const ll llmax = numeric_limits<ll>::max();
const ll mod = 1e9 + 7;
const double pi = M_PI;

ll median(vl &target) {
  int size = target.size();
  if (size % 2 == 0) {
    size--;
    return target[size / 2] + target[(size / 2) + 1];
  } else {
    return target[size / 2];
  }
}

int main()
{
  int n;
  cin >> n;
  vl as(n, 0);
  vl bs(n, 0);
  rep(i, n) {
    ll a, b;
    cin >> a >> b;
    as[i] = a;
    bs[i] = b;
  }
  sort(as.begin(), as.end());
  sort(bs.begin(), bs.end());
  ll amedian = median(as);
  ll bmedian = median(bs) + 1;
  cout << bmedian - amedian << endl;
}

ABC168自分なりのまとめ

AtCoder C++ 競技プログラミング

A- ∴ (Therefore)

下一桁で条件分岐
もっと賢いやり方がありそうだけど、、、

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

#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>;

//定数
const int intmax = numeric_limits<int>::max();
const ll llmax = numeric_limits<ll>::max();
const ll mod = 1e9 + 7;
const double pi = M_PI;

int main()
{
  int n;
  cin >> n;
  string s = to_string(n);
  if(s[s.size() - 1] == '3') {
    cout << "bon" << endl;
  }else if(s[s.size() - 1] == '0') {
    cout << "pon" << endl;
  }else if(s[s.size() - 1] == '1') {
    cout << "pon" << endl;
  }else if(s[s.size() - 1] == '6') {
    cout << "pon" << endl;
  }else if(s[s.size() - 1] == '8') {
    cout << "pon" << endl;
  }else if(s[s.size() - 1] == '2') {
    cout << "hon" << endl;
  }else if(s[s.size() - 1] == '4') {
    cout << "hon" << endl;
  }else if(s[s.size() - 1] == '5') {
    cout << "hon" << endl;
  }else if(s[s.size() - 1] == '7') {
    cout << "hon" << endl;
  }else if(s[s.size() - 1] == '9') {
    cout << "hon" << endl;
  }
}

B-... (Triple Dots)

長さ判定して、あとは適当に

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

#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>;

//定数
const int intmax = numeric_limits<int>::max();
const ll llmax = numeric_limits<ll>::max();
const ll mod = 1e9 + 7;
const double pi = M_PI;

int main()
{
  int k;
  cin >> k;
  string s;
  cin >> s;
  if (s.size() <= k) {
    cout << s << endl;
  }else{
    cout << s.substr(0, k) << "..." << endl;
  }
}

C- : (Colon)

悪夢のようなC問題
デジタル時計になれすぎたせいで、分針が動くと時針が動くことに気づけなくて解けなかった
それ以外は適当に三角関数を使って解けばいいです
余弦定理を知っていたらそれが一番楽

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

#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>;

//定数
const int intmax = numeric_limits<int>::max();
const ll llmax = numeric_limits<ll>::max();
const ll mod = 1e9 + 7;
const double pi = M_PI;

int main()
{
  int a, b, h, m;
  cin >> a >> b >> h >> m;
  double aarg = 30 * h + 0.5 * m;
  double barg = 6 * m;
  double x = aarg - barg;
  double arg = (double)  (x) * pi / 180.0;
  double result = sqrt(a * a + b * b - 2 * a * b * cos(arg));
  cout << fixed;
  cout << setprecision(9) << result << endl;
}

D- .. (Double Dots)

これが本当に400点問題なのかと思うくらい簡単だった。
辺に重みが無いため幅優先探索で始点からの最短経路は全ノードについて求まります。
あとは、幅優先木の親に当たるノードの番号を各ノードについて覚えていけば良いです。
引っ掛けとして、できない場合は-1を出力するように言われていますが、非連結な要素がないため
上の解放で構成できない場合はありません。

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

#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>;

//定数
const int intmax = numeric_limits<int>::max();
const ll llmax = numeric_limits<ll>::max();
const ll mod = 1e9 + 7;
const double pi = M_PI;

int main()
{
  int n, m;
  cin >> n >> m;
  vector<vector<int>> graph(n, vector<int>());
  rep(i, m) {
    int a, b; 
    cin >> a >> b;
    graph[a - 1].push_back(b - 1);
    graph[b - 1].push_back(a - 1);
  }

  v parents(n, -1);

  auto bfs = [&](){
    queue<int> q;
    vector<bool> flag(n, false);
    q.push(0);
    flag[0] = true;
    while(!q.empty()) {
      int cur = q.front();
      q.pop();
      for(int i = 0; i < graph[cur].size(); i++) {
        int next = graph[cur][i];
        if(flag[next]) continue;
        q.push(next);
        flag[next] = true;
        parents[next] = cur;
      }
    }
  };
  bfs();
  cout << "Yes" << endl;
  rep(i, n - 1) cout << parents[i + 1] + 1 << endl;
}

E-

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

#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>;

//定数
const int intmax = numeric_limits<int>::max();
const ll llmax = numeric_limits<ll>::max();
const ll mod = 1e9 + 7;
const double pi = M_PI;

int main()
{
}

ABC167自分なりのまとめ

AtCoder C++ 競技プログラミング

A- Registration

SとTの末尾以外を比較して一致していればOK

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

#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>;

//定数
const int intmax = numeric_limits<int>::max();
const ll llmax = numeric_limits<ll>::max();
const ll mod = 1e9 + 7;
const double pi = M_PI;

int main()
{
  string s, t;
  cin >> s >> t;
  rep(i, s.size()) {
    if(s[i] != t[i]) {
      cout << "No" << endl;
      return 0;
    }
  }
  cout << "Yes" << endl;
}

B-Easy Linear Programming

A+BがKよりも大きいならばKが答え
A+BがK以下ならばA+BからK - (A + B)を引いたものが答え

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

#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>;

//定数
const int intmax = numeric_limits<int>::max();
const ll llmax = numeric_limits<ll>::max();
const ll mod = 1e9 + 7;
const double pi = M_PI;

int main()
{
  ll a, b, c, k;
  cin >> a >> b >> c >> k;
  ll result = 0;
  if( a + b <= k ) {
    result += a;
    k -= a + b;
  }else{
    result += k;
    cout << result << endl;
    return 0;
  }
  result -= k;
  cout << result << endl;
}

C-Skill Up

久しぶりのBit全探索
ある参考書を購入する場合は1,購入しない場合を0とすると、参考書の購入パターンは12桁の2進数で表すことができる。
212 = 4096であるため、全パターンを探索することが可能。
コードが少し汚いけど許してください。

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

#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>;

//定数
const int intmax = numeric_limits<int>::max();
const ll llmax = numeric_limits<ll>::max();
const ll mod = 1e9 + 7;
const double pi = M_PI;

int main()
{
  int n, m, x;
  cin >> n >> m >> x;
  v c(n, 0);
  vector<vector<int>> a(n, vector<int>(m, 0));
  rep(i, n) {
    cin >> c[i];
    rep(j, m) {
      cin >> a[i][j];
    }
  }
  int result = intmax;
  for(int i = 1; i <= 4096; i++) {
    v alg(m, 0);
    int cost = 0;
    for(int j = 0; j < n; j++) {
      if(i & (1 << j)) {
        rep(k, m) {
          alg[k] += a[j][k];
        }
        cost += c[j];
      }
    }
    bool ok = true;
    rep(k, m) {
      if(alg[k] < x) {
        ok = false;
      }
    }
    if(ok) {
      result = min(result, cost);
    }
  }
  if (result == intmax) {
    cout << -1 << endl;
  }else{
    cout << result << endl;
  }
}

D-Teleporter

与えられた問題をグラフで考えてみると、全てのノードの出次数が1となっているグラフであることがわかる。
出次数とは、自分から出ていく辺の数です。
全ノードの出次数が1であるため、たかだかN回移動を繰り返すと、必ず訪問済みのノードに到達することがわかります。
一度訪問済みのノードに到達すると、あとはそのループを繰り返すだけになります。
最初のサンプルを例に取ると、

  • 1 -> 3 -> 4 -> 1

というルートで訪問済みの1に戻ることになります。
そして、以降はどれだけ移動を重ねても、その経路はこのループ上をぐるぐる回るだけになります。
この性質を用いると、K回の移動をシミュレーションする必要がなくなります。
具体的には、ループに入るまでに必要な移動数をK'、ループの長さをLとすると
(K - K') % L回、ループの先頭から移動するだけでよくなります。
これは、(K - K') / L回のループ回数は省略することができるためです。
Lは必ずN以下であるため、計算量も十分高速です。

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

#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>;

//定数
const int intmax = numeric_limits<int>::max();
const ll llmax = numeric_limits<ll>::max();
const ll mod = 1e9 + 7;
const double pi = M_PI;

int n;
ll k;
int a[2 * 100000];

pair<int, ll> calc(int start) {
  if(k == 0) return {start, 1};
  vector<bool> flag(n, false);
  flag[start] = true;
  int cnt = 0;
  while(1) {
    start = a[start] - 1;
    cnt++;
    if(k == cnt){
      k -= cnt;
      return {start, cnt};
    };
    if(flag[start]){
      k -= cnt;
      return {start, cnt};
    }else{
      flag[start] =true;
    }
  }
}

int main()
{
  cin >> n >> k;
  rep(i, n) cin >> a[i];
  auto stop = calc(0);
  if(stop.first != 0) {
    stop = calc(stop.first);
  }
  ll rest = k % stop.second;
  int result = stop.first;
  rep(i, rest) {
    result = a[result] - 1;
  }
  cout << result + 1 << endl;
}

E-Colorful Blocks

先週に続いて、今週も自力で解くことができました！
まず最初に、素朴なケースであるK=0の場合を考えてみます。
この場合、最初のブロックにはM色を選ぶことができ、あとのブロックにはそれぞれM-1色を選ぶことができます。
これは、1つ前のブロックと同じ色は選ぶ事ができないためです。
よって、ありえるパターン数はM * (M - 1)N - 1個となります。
次に、このケースを利用してK=1の場合を考えてみましょう。
K=1の場合、すべての組の中で1つだけ色が同じになる組を許します。
今、組はN-1個あり、この中から1つを選ぶ組み合わせの数はN-1 C 1個あります。
そして、そのような組を1つ選ぶとありえるパターン数はM * (M - 1)N - 1 / (M - 1)となります。
これは、1つのブロックの色の選択肢がなくなるためです。
よって、K=1の場合、(M * (M - 1)N - 1 / (M - 1)) * (N - 1 C 1)となります。
K=2以降の場合についても、同様の考え方で求めていく事ができます。
注意点としてはM = 2の場合にはK = N - 1以外は可能な塗り方が存在しないことと、
modの世界で計算をしていくので逆元を求める必要があることです。

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

#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>;

//定数
const int intmax = numeric_limits<int>::max();
const ll llmax = numeric_limits<ll>::max();
const ll mod = 998244353;
const double pi = M_PI;


template <typename number>
pair<number, number> extended_euclid(number a, number b)
{
  number r0, r1, a0, a1, b0, b1;
  r0 = a; r1 = b;
  a0 = 1; a1 = 0;
  b0 = 0; b1 = 1;
  while (r1>0) {
    number q1 = r0 / r1;
    number r2 = r0 % r1;
    number a2 = a0 - q1 * a1;
    number b2 = b0 - q1 * b1;
    r0 = r1 ; r1 = r2;
    a0 = a1 ; a1 = a2;
    b0 = b1 ; b1 = b2;
  }
  number c = r0;
  a = a0; //x
  b = b0; //y
  return  {a, c};
}

template  <typename number>
number inverse_N(number a, number N)
{
  pair<number, number> result = extended_euclid(a, N);
  if(result.first < 0)
  {
    result.first = result.first + N;
  }
  return result.first;
}

ll n, m, k;

ll calc() {
  ll result = m;
  rep(i, n - 1) {
    result = (result * (m - 1)) % mod;
  }
  return result;
}

int main()
{
  cin >> n >> m >> k;
  if(m == 1) {
    if(k == n - 1){
      cout << 1 << endl;
    }else{
      cout << 0 << endl;
    }
    return 0;
  }
  ll base = calc();
  ll minv = inverse_N(m - 1, mod);
  ll numerator = n - 1;
  ll denominator = 1;
  ll cand = numerator;
  ll result = base;
  for(int i = 1; i <= k; i++) {
    ll temp = base * minv;
    temp %= mod;
    temp *= cand;
    temp %= mod;
    result += temp;
    result %= mod;
    //分母の更新
    numerator = (numerator * (n - 1 - i)) % mod;
    //分子の更新
    denominator = (denominator * (i + 1)) % mod;
    //組み合わせの更新
    cand = numerator * inverse_N(denominator, mod);
    cand %= mod;
    //減る候補を更新
    minv = minv * inverse_N(m - 1, mod);
    minv %= mod;
  }
  cout << result << endl;
}

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;
  }
}

ABC166自分なりのまとめ

A-A?C

ABCならARC、ARCならABCと出力すれば良いです。

//競技プログラミング用のテンプレート
#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()
{
  string s;
  cin >> s;
  if(s == "ABC") {
    cout << "ARC" << endl;
  }else{
    cout << "ABC" << endl;
  }
}

B-Trick or Treat

mapで受け取ったお菓子の枚数を記録して、0の人数を出力すれば良いです。

//競技プログラミング用のテンプレート
#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, k;
  cin >> n >> k;
  v memo(n, 0);
  rep(i, k) {
    int d;
    cin >> d;
    rep(j, d) {
      int a;
      cin >> a;
      memo[a - 1] = 1;
    }
  }
  int cnt = 0;
  rep(i, n) {
    if(memo[i] == 0) {
      cnt++;
    }
  }
  cout << cnt << endl;
}

C-Peaks

最初は連結している展望台の中で一番高いやつかと思いました。。。
距離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()
{
  int n, m;
  cin >> n >> m;
  vl h(n, 0);
  rep(i, n) {
    cin >> h[i];
  }
  vector<vector<int>> graph(n, vector<int>());
  rep(i, m) {
    int a, b;
    cin >> a >> b;
    graph[a - 1].push_back(b - 1);
    graph[b - 1].push_back(a - 1);
  }
  int result = 0;
  auto calc = [&](int start) {
    ll ma = h[start];
    map<int, int> memo;
    memo[ma]++;
    for(int i = 0; i < graph[start].size(); i++)
    {
      int ne = graph[start][i];
      if(ma <= h[ne]) {
        ma = h[ne];
        memo[ma]++;
      }
    }
    if(ma == h[start] && memo[ma] == 1) result++;
  };
  rep(i, n) {
    calc(i);
  }
  cout << result << endl;
}

D-I hate Factorization

そんなに広い範囲を調べなくても、解が見つかるだろうとエスパーしました。
A5 - B5をxを引数に取る関数f(x) = x5 - (x - 1)5と考えます。
この関数は明らかにx=0.5が最小値となる凹関数です。
f(x)はx=120, -119で109を超えます。
よってA,Bともにこの範囲で全探索をすれば良いです。
コードはエスパーの結果なので、1000になっています。

//競技プログラミング用のテンプレート
#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>;

ll calc(ll x) {
  return x * x * x * x * x;
}

int main()
{
  ll x;
  cin >> x;
  for(ll i = 0; i <= 1000; i++) {
    ll a5 = calc(i);
    ll b5 = a5 - x;
    if(b5 < 0) {
      for(ll j = 0; j <= 1000; j++){
        if(b5 == calc(-j)) {
          cout << i << " " << -j << endl;
          return 0;
        }
      }
    }else{
      for(ll j = 0; j <= 1000; j++){
        if(b5 == calc(j)) {
          cout << i << " " << j << endl;
          return 0;
        }
      }
    }
  }
}

E-This Message Will Self-Destruct in 5s

久しぶりにE問題が自力で解けました。
参加者が1~Nの順番で並んでいるとします。
このとき、順番iまでの参加者で条件を満たしている組み合わせ数がx個あるとします。
そうすると、順番i + iの参加者を新たに加えるとi + 1番目までの参加者で条件を満たしている組み合わせ数は
x + (i + 1番目を加えて時に新たに発生する組み合わせ数)となります。
よって、もしこの新たに発生する組み合わせ数を簡単に求めることができるならば、簡単な動的計画法を用いて
解を計算することが出来ます。
ここからは、新たに参加者を加えたときに条件を満たす組み合わせ数を計算する方法について考えます。
条件は、参加者i,jの場合、Ai + Aj = |i - j|でした。
今、1から順番に参加者を追加していっているため、上の式は以下のように変形できます。

  • Ai + Aj = j - i (j > i)

これを更に変形すると

  • Ai + i = j - Aj

となります。
よって、各i(i < j)について、自身の番号と身長の和をmapに保存していくことで
簡単に新たに発生する組み合わせ数を計算することができます。

//競技プログラミング用のテンプレート
#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 n;
ll a[2 * 100000];
ll dp[2 * 100000 + 1];

int main()
{
  cin >> n;
  rep(i, n) {
    cin >> a[i];
  }
  map<ll, ll> m;
  for(ll i = 1; i <= n; i++) {
    ll want = i - a[i - 1];
    m[i + a[i - 1]]++;
    dp[i] = m.count(want) == 0 ? dp[i - 1] : dp[i - 1] + m[want];
  }
  cout << dp[n] << endl;
}

ABC164自分なりのまとめ

AtCoder C++ 競技プログラミング

ABC164自分なりのまとめ

A - Sheep and Wolves

狼と羊の数が与えられるので、大小比較をすれば良いです。

#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 s, w;
  cin >> s >> w;
  if(s > w) {
    cout << "safe" << endl;
  }else{
    cout << "unsafe" << endl;
  }
}

B - Battle

高橋君と青木君について、相手の体力を0以下にするために必要な攻撃回数を計算して、比較すれば良いです。

#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, c, d;
  cin >> a >> b >> c >> d;
  int tc = ( c + (b - 1) ) / b;
  int ac = ( a + (d - 1) ) / d;
  if(tc <= ac) {
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
}

C - gacha

mapに要素を入れながら、もし一度も格納されたことがなかったらカウントしていけば良いです。

#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;
  cin >> n;
  vs s(n);
  map<string, int> memo;
  int c = 0;
  rep(i, n) {
    cin >> s[i];
    if(memo.count(s[i]) == 0){
      memo[s[i]] = 1;
      c++;
    }
  }
  cout << c << endl;
}

D - Multiple of 2019

解けませんでした。
最近D問題も解けないことが多くて辛いです。
こういう部分列を考える問題には累積和的なアプローチが有効らしいです。
一番簡単な例だと、区間がクエリとして与えられてその区間の和を求める問題でしょうか。
今回の場合も、最初にSの1の桁から順番にi桁目までの部分列と見たときの10進数としての値を配列に記録しておきます。
例えば、12345という値が与えられた時の配列memoの要素は以下のようになります。

  • memo[1] = 5
  • memo[2] = 45
  • memo[3] = 345
  • ・・・
  • memo[5] = 12345

この様な配列を持つと、区間[l, r)を10進数は以下のような式で計算することが出来ます

  • 区間[l, r) = (memo[l] - memo[r]) / 10r

例えば、[3, 1)の場合は(memo[3] - memo[1]) / 101 = 34
この値が2019で割り切れるということは、以下の式が成り立つことと同値です。

  • (memo[l] - memo[r]) / 10r = 0 mod 2019 (=は合同に読み替えてください)

ここで、合同式の公式より、10rが2019と互いにその場合、上の式は以下の式と同値になります。

  • (memo[l] - memo[r]) = 0 mod 2019

今回10と2019が互いに素であるため、問題なく上の式が成り立ちます。
よって、memo[l]とmemo[r]が等しい場合にのみ区間が2019で割り切れるため、今回の問題は各iにたいして、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()
{
  string s;
  cin >> s;
  int base = 2019;
  int result = 0;
  reverse(s.begin(), s.end());
  v memo(base, 0);
  int d = 1;
  int num = 0;
  memo[0] = 1;
  for(int i = 0; i < s.size(); i++) {
    num = num + d * (s[i] - '0');
    num %= base;
    memo[num]++;
    d = (d * 10) % base;
  }
  for(int i = 0; i < base; i++)
  {
    if(memo[i] > 0) {
      result += (memo[i] * (memo[i] - 1)) / 2;
    }
  }
  cout << result << endl;
}

E - Two Currencies

これも難しかったです。
両替する場所を固定できれば、ダイクストラで求まるなあなどと考えていましたが、 明らかに複数回両替する場合も考えられるため詰まっていました。
この問題のポイントは以下の2点です。

  • 持っている金貨の枚数が十分に多いので金貨は無限にあると考えて良い
  • 制約より、2500枚の銀貨があれば十分に目的の都市にたどり着ける

以上より、各都市に対して、その都市にいるときに銀貨をx枚持っているという状態を含めて1つのグラフ上のノードとして 考えることで、ダイクストラ法を用いて最短経路を求めることが出来ます。
今回は都市の数がたかだか50であり、1都市の状態は2500個しかないので、問題なく扱うことが出来ます
ダイクストラ法を実装する上で気をつけることは、各ステップで隣接ノードには移らず、その場で両替を行うというパターンを追加することです。

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <string>
#include <math.h>
#include <stack>
#include <limits>

#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>;

const int imax = numeric_limits<int>::max();
const ll llmax = numeric_limits<ll>::max();

using pp = pair<ll, pair<int, int>>; //cost, node_num, have_money;

struct Edge {
  int u;
  int v;
  int a;
  ll b;
};

struct City {
  ll c;
  ll d;
};

p graph[50][50]; //cost, need_money
Edge edges[100];
City cities[50];
ll dp[50][2501];

int n;
int m;
ll s;

void djk(int start, int have) {
  rep(i, n) {
    rep(j, 2501) {
      dp[i][j] = llmax;
    }
  }
  priority_queue<pp, vector<pp>, greater<pp>> pq; //cost, node_num, have_money;
  pq.push({0, {start, have}});
  dp[start][have] = 0;
  
  while(!pq.empty()) {
    pp cur = pq.top();
    pq.pop();
 
    ll curcost = cur.first;
    int curcity = cur.second.first;
    int nowhave = cur.second.second;

    //両替しない
    for(int i = 0; i < n; i++) {
      if(graph[curcity][i].first == 0) continue;

      ll newcost = curcost + graph[curcity][i].first;
      int newmoney = nowhave - graph[curcity][i].second;

      if(newmoney < 0) continue;

      if(newcost >= dp[i][newmoney]) continue;

      dp[i][newmoney] = newcost;
      pq.push({newcost, {i, newmoney}});
    }

    //両替する
    ll newcost = curcost + cities[curcity].d;
    int newmoney = nowhave + cities[curcity].c;
    newmoney = newmoney >= 2500 ? 2500 : newmoney;
    if(newcost < dp[curcity][newmoney]) {
      dp[curcity][newmoney] = newcost;
      pq.push({newcost, {curcity, newmoney}});
    }
  }
}

int main(){
  cin >> n >> m >> s;
  s = min(s, (ll)(2500));
  rep(i, m) {
    cin >> edges[i].u >> edges[i].v >> edges[i].a >> edges[i].b;
  }
  rep(i, n) {
    cin >> cities[i].c >> cities[i].d;
    cities[i].c = min(cities[i].c, (ll)2500);
  }

  //グラフの初期化
  rep(i, 50) rep(j, 50) graph[i][j] = {0, 0};

  //グラフの構成
  rep(i, m) {
    auto e = edges[i];
    graph[e.u - 1][e.v - 1] = {e.b, e.a};
    graph[e.v - 1][e.u - 1] = {e.b, e.a};
  } 
  djk(0, s);
  for(int i = 1; i < n; i++) {
    ll result = llmax;
    for(int j = 0; j <= 2500; j++)
    {
      result = min(result, dp[i][j]);
    }
    cout << result << endl;
  }
}