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]) / 10^r

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

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

ここで、合同式の公式より、10^rが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;
  }
}

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

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

ABC164自分なりのまとめ

ABC164自分なりのまとめ

A - Sheep and Wolves

B - Battle

C - gacha

D - Multiple of 2019

E - Two Currencies