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

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

ABC173自分なりのまとめ

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

A- Payment

N円を超えるまで1000円ずつ足していけば良いです。

//競技プログラミング用のテンプレート
#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;
  int pay = 1000;
  while(pay < n) {
    pay += 1000;
  }
  cout << pay - n << endl;
}

B- Judge Status Summary

mapにそれぞれの出現回数を記録しました。

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

string cand[] = {"AC", "WA", "TLE", "RE"};

int main()
{
  int n;
  cin >> n;
  map<string, int> memo;
  rep(i, n)
  {
    string s;
    cin >> s;
    memo[s]++;
  }
  rep(i, 4) {
    printf("%s x %d
", cand[i].c_str(), memo[cand[i]]);
  }
}

C- H and V

H + Wビットのbit全探索を行えばよいです。
H,Wともに6以下なので計算量的にも問題ありません。

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

string grid[6] = {""};

void choose(map<int, int> &memo, int bits, int &comp, int size) {
  for(int i = 0; i < size; i++) {
    if (bits & comp) {
      memo[i] = 1;
    }
    comp = comp << 1;
  }
}

int count(int h, int w, map<int, int> &row, map<int, int> &col) {
  int result = 0;
  for(int i = 0; i < h; i++)
  {
    for(int j = 0; j < w; j++)
    {
      if (row.count(i) == 0) continue;
      if (col.count(j) == 0) continue;
      if (grid[i][j] == '#') result++;
    }
  }
  return result;
}

int main()
{
  int h, w, k;
  cin >> h >> w >> k;
  rep(i, h)
  {
    cin >> grid[i];
  }
  int cand = 0;
  for(int i = 0; i < pow(2, h + w); i++) {
    int comp = 1;
    map<int, int> row;
    map<int, int> col;  
    choose(row, i, comp, h);
    choose(col, i, comp, w);
    int temp = count(h, w, row, col);
    if (temp == k) cand++;
  }
  cout << cand << endl;
}

D- Chat in a Circle

結構難しめかな？
最適性の証明が難しかったです。(今もできてるか怪しい)
直感的には思いつきやすいのではないでしょうか
最初にプレイヤーをフレンドリーさの降順にソートします。
その後、それぞれのフレンドリーさを何回心地よさに加えることができるかを考えます。
一番大きいフレンドリーさA{max}は1回しか加えることができません。
これは、心地よさに加えられるフレンドリーさは両脇のうち小さい方だからです。
では、その次に大きいフレンドリーさは何回加えられるでしょうか?
フレンドリーさの降順に到着していくと仮定すると、最大2回加えられることがわかります。
右隣にプレイヤーを到着させた場合と、左隣にプレイヤーを到着させた場合です。
フレンドリーさの降順に到着していくと仮定しているので、右隣と左隣、一回ずつしか加えられません。
この場合、最終的な心地よさの合計は、A{max} + 2 * A_i (i != max)となります。
次に、この到着の仕方が最適であることを証明します。
もしあるフレンドリーさA_iを2回よりも多く心地よさに加えようとすると、プレイヤーiよりもあとに到着するプレイヤーの フレンドリーさの方が大きい必要があります。
すると、A_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 n;
  cin >> n;
  vl a(n, 0);
  rep(i, n) cin >> a[i];
  sort(a.begin(), a.end());
  reverse(a.begin(), a.end());
  ll sum = a[0];
  int arrived = 2;
  for(int i = 1; i < n && arrived <= n; i++) {
    if (arrived + 1 <= n) {
      sum += a[i];
      arrived++;
    }
    if (arrived + 1 <= n) {
      sum += a[i];
      arrived++;
    }
  }
  cout << sum << endl;
}

E- Multiplication 4

コンテスト中には解けなかったけど、D問題よりも考察自体は簡単かも
基本的に、絶対値の降順にk個取ったとき、掛け算の結果がマイナスにならなければそれが解になります。
解がマイナスになった場合は

  • 負の数をK個の中から一つ取り除いて、正の数を追加する
  • 正の数をK個の中から一つ取り除いて、負の数を追加する

ことで、結果を正にすることができます。
どちらの方法をとったほうが解が大きくなるかは

  • R: 先頭からK個取ったときの解
  • P1: K個の中から最も小さい正の数
  • M1: K個の中から最も絶対値が小さい負の数
  • P2: 残った数の中から最も大きい正の数
  • M2: 残った数の中から最も絶対値が大きい負の数

とすると

  • P1 * P2 < M1 * M2

で比較することができます。
あとは細かい例外を適切に処理していけば解けるはずです。
コードが説明と若干離れているのは目をつぶってください。

//競技プログラミング用のテンプレート
#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 llmin = numeric_limits<ll>::min();
const ll mod = 1e9 + 7;
const double pi = M_PI;

ll calc_only(vl &src, int k) {
  ll ans = 1;
  for(int i = 0; i < k; i++) {
    ans *= src[i];
    ans %= mod;
  }
  return ans;
}

ll calc_mix_even(vector<pair<ll, int>> &mix,  int k) {
  ll ans = 1;
  for(int i = 0; i < k; i++) {
    ans *= mix[i].first;
    ans %= mod;
  }
  return ans;
}

ll calc_mix_odd_without(vector<pair<ll, int>> &mix, int k, int target) {
  ll ans = 1;
  for(int i = 0; i < k; i++) {
    if (i == target) continue;
    ans *= mix[i].first;
    ans %= mod;
  }
  return ans;
}

int get_last_index(vector<pair<ll, int>> &mix, int k, int target) {
  int last_index = -1;
  for(int i = 0; i < k; i++)
  {
    if(mix[i].second == target) last_index = i;
  }
  return last_index;
}

int get_first_index(vector<pair<ll, int>> &mix, int k, int target) {
  for(int i = k; i < mix.size(); i++)
  {
    if(mix[i].second == target) return i;
  }
  return -1;
}

ll adapt(vector<pair<ll, int>> &mix, int k, int without, int add) {
  ll ans = calc_mix_odd_without(mix, k, without);
  ans *= mix[add].first;
  ans %= mod;
  return ans;
}

ll calc_mix_odd(vector<pair<ll, int>> &mix, int k) {
  ll ans = llmin;
  int plus_last = get_last_index(mix, k, 1);
  int minus_last = get_last_index(mix, k, -1);
  int plus_first = get_first_index(mix, k, 1);
  int minus_first = get_first_index(mix, k , -1);
  if (plus_last == -1) {
    //プラスが<kにそもそも存在しない
    //マイナスを取り除いてプラスを入れる
    return adapt(mix, k, minus_last, plus_first);
  }
  if (plus_first == -1) {
    //プラスが>=kに存在しない
    //プラスを取り除いてマイナスを入れる
    return adapt(mix, k, plus_last, minus_first);
  }
  if (minus_first == -1) {
    //マイナスが>=kに存在しない
    //マイナスを取り除いてプラスを入れる
    return adapt(mix, k, minus_last, plus_first);
  }
  ll plus1 = mix[plus_last].first;
  ll minus1 = mix[minus_last].first;
  ll plus2 = mix[plus_first].first;
  ll minus2 = mix[minus_first].first;
  if (plus1 * plus2 < minus1 * minus2) {
    //プラスを取り除いてマイナスを入れる
    return adapt(mix, k, plus_last, minus_first);
  } else {
    //マイナスを取り除いてプラスを入れる
    return adapt(mix, k, minus_last, plus_first);
  }
}


ll calc_mix(vector<pair<ll, int>> &mix, int k) {
  int num_minus_in_k = 0;
  for(int i = 0; i < k; i++) {
    if (mix[i].second == -1) num_minus_in_k++;
  }
  if (num_minus_in_k % 2 == 0) {
    return calc_mix_even(mix, k);
  }
  if (num_minus_in_k % 2 != 0) {
    return calc_mix_odd(mix, k);
  }
}


int main()
{
  int n, k;
  cin >> n >> k;
  vl as(n, 0);
  vl plus, minus, minusr;
  vector<pair<ll, int>> abss(n);
  rep(i, n) {
    ll a; cin >> a;
    as[i] = a;
    if (a < 0) {
      minus.push_back(a);
      abss[i] = {abs(a), -1};
    }else{
      plus.push_back(a);
      abss[i] = {a, 1};
    }
  }
  sort(plus.begin(), plus.end());
  reverse(plus.begin(), plus.end());
  sort(minus.begin(), minus.end());
  minusr = minus;
  reverse(minusr.begin(), minusr.end());
  sort(abss.begin(), abss.end());
  reverse(abss.begin(), abss.end());
  //全部正
  if (plus.size() == n) {
    ll ans = calc_only(plus, k);
    cout << ans << endl;
    return 0;
  }
  //全部負
  if (minus.size() == n) {
    ll ans = llmin;
    if (k % 2 == 0) ans = calc_only(minus, k);
    if (k % 2 != 0) ans = calc_only(minusr, k);
    if (ans < 0) ans += mod;
    cout << ans << endl;
    return 0;
  }
  //n == k
  if (n == k) {
    ll ans = calc_only(as, k);
    if (ans < 0) ans += mod;
    cout << ans << endl;
    return 0;
  }
  //それ以外
  ll ans = calc_mix(abss, k);
  cout << ans << endl;
}