2021-01-05

AtCoder Beginner Contest 187 D - Choose Me

AtCoder ABC-D

問題

問題文へ

N個の町があり、i番目の町には青木派の有権者が $A_i$ 人、高橋派の有権者が $B_i$ 人います。他に有権者はいません。

高橋氏は、それぞれの町で演説を行うことができます。

高橋氏がある町で演説を行った場合、その町の高橋派も青木派も全員高橋氏に投票します。

一方、高橋氏がある町で演説を行わなかった場合、その町の青木派は全員青木氏に投票し、高橋派は投票に行きません。

高橋氏が青木氏より多く票を獲得するためには、最小でいくつの町で演説をする必要があるでしょうか？

制約

入力はすべて整数
${1 \leqq N \leqq 2 \times 10^5}$
${1 \leqq A_i,B_i \leqq 10^9}$

考えたこと

高橋氏が演説をすれば、 $A_i,B_i$ を手にします。演説をしないならば、青木氏が $A_i$ を手にします。

まったく演説をしないと、高橋氏0票対青木氏は $A_i$ の合計です。逆にすべての町で演説をすると、高橋氏は ${A_i,B_i}$ の合計に対して青木氏は0票です。

求められているのは、最小でいくつの町で演説をするかです。スタートは演説をしない状態で、そこから一番多く票をもらえる町から演説していくことにします。

ある町で演説すると、高橋氏は ${A_i,B_i}$ 票を得ます。同時に青木氏は $A_i$ 票を失います。高橋氏は1つの町で ${2A_i + B_i}$ 票を得ます。

これをあらかじめ計算し、降順にソートしておきます。

得票数の多い順に、青木氏の最大得票数から引いていき、0を下回れば勝つことができます。

コード

#define _GIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define all(v) v.begin(), v.end()
using namespace std;
using ll = long long;


int main(void) {
    ll N;
    cin >> N;

    vector<ll> v(N);
    ll A_sum = 0;
    rep(i, N) {
        ll a, b;
        cin >> a >> b;
        A_sum += a;
        v[i] = a * 2 + b;
    }

    sort(v.rbegin(), v.rend());
    ll ans = 0;
    while (A_sum >= 0) {
        A_sum -= v[ans];
        ++ans;
    }

    cout << ans << endl;
    
    return 0;
}

解説を読んで

X=（高橋氏の得る票数）-（青木氏の得る票数）と定義する。これができてなかったです。式をたてることが大事なのではないかと思います。

2021-01-05

AtCoder Beginner Contest 187 C - 1-SAT

AtCoder ABC-C

問題

問題文へ

N個の文字列 ${S_1~S_N}$ が与えられます。各文字列は、英小文字からなる空でない文字列の先頭に!を0文字か1文字付加したものです。

文字列Tは先頭に!を0文字付加しても1文字付加しても ${S_1~S_N}$ のいずれかに一致するとき、不満な文字列といいます。

不満な文字列があるかどうか判定し、あれば1つ示してください。

制約

1 $\leqq$ N $\leqq$ 2 $\times$ 10⁵
1 $\leqq$ $|S_i|$ $\leqq$ 10
$S_i$ は英小文字からなる空でない文字列の先頭に!を0文字か1文字を付加したものである。

考えたこと

!の付加されていない文字列の集まりを考えます。!の付加された文字列から!を取り除いたものが、その集まりに含まれればそれが不満な文字列でしょう。

文字列を探す処理はstd:mapに任せれば、時間は間に合うと考えました。

コード

#define _GIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define all(v) v.begin(), v.end()
using namespace std;
using ll = long long;


int main(void) {
    int N;
    cin >> N;
    vector<string> v(N);
    rep(i, N) cin >> v[i];

    map<string, int> mp;
    rep(i, N) {
        if (v[i][0] != '!') {
            mp[v[i]]++;
        }
    }

    rep(i, N) {
        if (v[i][0] == '!') {
            string t = v[i].substr(1);
            if (mp[t] != 0) {
                cout << t << endl;
                return 0;
            }
        }
    }

    cout << "satisfiable" << endl;

    return 0;
}

解説を読んで

なぜ、私は!付きの文字列をもとに調べたのだろう？

2020-12-22

AtCoder Beginner Contest 186 C - Unlucky 7

AtCoder ABC-C

問題

問題文へ

1以上N以下の整数のうち、10進法で表しても8進法で表しても7を含まないような数はいくつありますか？

制約

${1 \leqq N \leqq 10^5}$
Nは整数である。

考えたこと

制約より、 $10^5$ までならばすべてを確認しても間に合うと判断しました。8進法への変換方法は検索しました。

コード

#define _GIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define all(v) v.begin(), v.end()
using namespace std;
using ll = long long;


int main(void) {
  int N;
  cin >> N;

  int ans = 0;
  char s[100];
  for (int i = 1; i <= N; ++i) {
    sprintf(s, "%u%o", i, i);
    if (strchr(s, '7') == NULL) ++ans;
  }

  cout << ans << endl;
  
  return 0;
}

解説動画を見て

10で割った余りから10進法の一桁ずつ取得できます。8で割ればすむようです。基数を変えて応用ですね。

関数にせず、for(int base : (8, 10))で処理を分けるのはかっこいいです。

2020-12-01

AtCoder Regular Contest 109 B - log

AtCoder ARC-B

問題

問題文へ

長さ1からnまでのn種類の丸太が1本ずつほしいです。長さ1からn+1までn+1種類の丸太が1本ずつ販売されています。

買った丸太を切断することにコストはかかりません。丸太の値段は1本1円です。必要な最小の金額を求めてください。

制約

${1 \leqq n \leqq 10^18}$

考えたこと

切断にコストがかからないので長さn+1を買い、たくさんの丸太にします。長さ1から作れば最適です。

n+1が2なら1本、3なら2本…10なら4本と書いて考えました。作れる最大の本数をxとして、x*(x+1)/2=n+1としてみました。n+1は与えられるので二次方程式でしょうか。それを解いて正しい答えか判定するプログラムを考える事は私には時間がかかりそうです。xに1から当てはめて試してみるプログラムならば、すぐに書けそうです。制約は大きいですが、試す回数は少なくともnの半分より小さくなるでしょうから間に合うと考えました。変数名がcountなのはカウントアップするイメージからです。

コード

#define _GIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define all(v) v.begin(), v.end()
using namespace std;
using ll = long long;


int main(void) {
  ll n;
  cin >> n;

  ll target = n + 1;
  ll num = 1;
  ll count = 1;
  while (count * (count + 1) / 2 <= target) {
    count++;
  }
  --count;

  ll ans = n + 1 - count;

  cout << ans << endl;
  
  return 0;
}

解説を読んで

二分探索は思い浮かんでいませんでした。制限時間に間に合うか考えただけで、アルゴリズムを適用する思考が足りないようです。

1+...+k=k(1+k)/2も、プログラマの数学で読んでいたのに思い至らなかったのが悔やまれます。x*(x+1)/2はどんな式なら良いだろうと試行錯誤しました。

2020-11-30

AtCoder Regular Contest 109 A - Hands

AtCoder ARC-A

問題

問題文へ

100階建ての建物A,Bがあります。i=1,...,100について、建物Aのi階とBのi階は廊下で繋がれています。また、i=1,...,90について、建物Aのi+1階とBのi階は廊下で繋がれています。どの廊下も双方向に通行可能で、移動にはx分かかります。また、A,Bどちらの建物にも階段があり、i=1,...99について、同じ建物のi階とi+1階は階段で繋がれています。どの階段も双方向に通行可能で、移動にはy分かかります。

建物Aのa階から建物Bのb階に移動するのにかかる最短時間を求めてください。

制約

${1 \leqq a,b,x,y \leqq 100}$
入力はすべて整数

考えたこと

移動時間はAとBをつなぐ廊下と同一建物の階段の2種類と少ないため、思いつく移動パターンをすべて計算して最短距離を求めることを考えました。

コード

#define _GIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define all(v) v.begin(), v.end()
using namespace std;
using ll = long long;


int main(void) {
  int a, b, x, y;
  cin >> a >> b >> x >> y;

  int ans = 1000000;
  if (a == b) {
    ans = min(ans, x);
  } else if (a < b) {
    ans = min(ans, (b - a) * y + x);
    ans = min(ans, (b - a + 1 + b - a) * x);
  } else {
    ans = min(ans, x + (a - 1 - b) * y);
    ans = min(ans, (a - b + a - b - 1) * x);
  }

  cout << ans << endl;
  
  return 0;
}

解説を読んで

全然違ってショックです。

2020-11-24

AtCoder Regular Contest 108 B - Abbreviate Fox

AtCoder ARC-B

問題

問題文へ長さNの英小文字のみからなる文字列sが与えられます。

sからfoxを1つ選んで除いて間を詰める操作を、可能な限り続けます。

操作ができなくなった時点のsの長さを出力してください。

制約

${1 \leqq N \leqq 2 \times 10^5}$
sは英小文字のみからなる長さNの文字列

考えたこと

fofoxxなど取り除いた後にまた取り除く必要があります。foxを取り除く処理はstringの連結を使うと時間がかかりそうです。

文字列を先頭から順にstackに入れて、xの場合は取り出してofならば取り除いたとして数え上げ、違った場合はstackに戻すこととしました。

コード

#define _GIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define all(v) v.begin(), v.end()
using namespace std;
using ll = long long;


int main(void) {
  int N;
  cin >> N;
  string s;
  cin >> s;

  stack<char> st;
  int count = 0;
  rep(i, s.length()) {
    if (s[i] == 'x' && i >= 2) {
      char temp = st.top();
      st.pop();
      if (temp == 'o' && st.top() == 'f') {
        st.pop();
        ++count;
      } else {
        st.push(temp);
        st.push(s[i]);
      }
    } else {
      st.push(s[i]);
    }
  }

  cout << N - count * 3 << endl;
  
  return 0;
}

解説を読んで

stackなどを使わなくてもできたようです。stringについて学ぶことがまだまだあります。

2020-11-20

AtCoder Regular Contest 057 A - 2兆円

AtCoder ARC-A

問題

問題文へ

2兆円を目指します。初日はA円です。翌日は当日から1+K*当日の所持金分増えます。

何日かかりますか？

制約

${0 \leqq A < 2 \times 10^12}$
${0 \leqq K \leqq 10^6}$
入力はすべて整数である

考えたこと

指数関数的に増えていくので操作をシミュレートしても間に合うと思います。指数関数的の使い方が正しいか自信はありません。

ただし、Kが0の時は1ずつしか増えないので場合分けする必要がありそうです。

コード

#define _GIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define all(v) v.begin(), v.end()
using namespace std;
using ll = long long;


int main(void) {
  ll A, K;
  cin >> A >> K;

  ll target = 2 * 1e12;

  if (K == 0) {
    cout << target - A << endl;
    return 0;
  }

  ll ans = 0;
  while (A < target) {
    A = A + 1 + A * K;
    ++ans;
  }

  cout << ans << endl;
  
  return 0;
}

解説を読んで

とくにありません。