2020-01-31

ABC153

ABC 参戦記録

結果

問題	ACまでに要した時間	AC
A	02:21	1
B	06:31	1
C	11:26	1
D	21:10	1

Rating	順位
641 (+23)	2663

初4完答を達成したが，えらく簡単でD問題ですら正答率が 5145/5366 という具合でこれをカウントしていいのか．．という気持ちではある．

ratingは黒字になったのでまぁ良かった．できればE問題まで解きたかったがdpをどう適用するか悩んだ挙げ句わからずに終了．当たり前だが貪欲法では解けない．

解答

C

強いやつに優先して必殺技を使えばよいので，昇順sortして戦闘からN-K番目まで通常攻撃で殴ってその回数をカウントすればおｋ．

#include <bits/stdc++.h>

#define REP(i, x) REPI(i, 0, x)
#define REPI(i, a, b) for (int i = int(a); i < int(b); ++i)
#define ALL(x) (x).begin(), (x).end()

typedef long long ll;
using namespace std;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  int N, K;
  cin >> N >> K;
  vector<ll> H(N);
  REP(i, N) { cin >> H[i]; }
  sort(H.begin(), H.end());
  ll ans = 0;
  REP(i, N - K) { ans += H[i]; }
  cout << ans << endl;

  return 0;
}

D

一度の攻撃の後に残るモンスターのHPを並べていくと完全二分木を作っていく作業であることが分かる．あとはそのとおりに実装すればいい．

#include <bits/stdc++.h>

#define REP(i, x) REPI(i, 0, x)
#define REPI(i, a, b) for (int i = int(a); i < int(b); ++i)
#define ALL(x) (x).begin(), (x).end()

typedef long long ll;
using namespace std;

ll f(ll h) {
  if (h == 1) {
    return 1;
  }
  return 1 + f(h / 2);
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  ll H;
  cin >> H;
  if (H == 1) {
    cout << 1 << endl;
    return 0;
  }

  ll depth = f(H);
  ll ans = 0;
  REPI(i, 1, depth + 1) { ans += pow(2, i - 1); }
  cout << ans << endl;

  return 0;
}

ダメだった点

E問題は 制限なしナップザック問題 という典型問題だったようだが，知らなかったので解けなかった．まだまだ知識不足．

トキ「E問題は私よ。
DP[i]=(ダメージをi与えるまでに消耗する魔力)
としてDPで解けるわ。EDPC Eみたいなイメージね。DPの基礎だからちゃんと復習してね。ところで、問題の設定はサーバルに決めてもらったんだけど、私には魔法なんか使えないわよ？」
サーバル（歌のことだなんて言えない……）
— 競技プログラミングをするフレンズ (@kyopro_friends) 2020年1月26日

drken1215.hatenablog.com

良かった点

早解きがキマってratingが黒字

おわりに

合同式の逆元は極めた（ような気がする）ので次はdpや．

DP まとめコンテストというDPだけを集めたコンテストがあるのでこれを全問解くで．

2020-01-14

ABC151

参戦記録 ABC TODO

atcoder.jp

結果

問題	ACまでに要した時間	AC	WA
A	01:17	1	0
B	06:56	1
C	40:19	1	1
D	:	0	0

Rating	順位
618 (+7)	3027

久々にWAをやらかしてしまった．最初の提出でAC取れれば2300位ぐらいには入れたので大変もったいないことをした．国語力の問題でコーナーケース踏み抜くとか大変情けないので今後は気をつけたいものである．

解答

A

#include <bits/stdc++.h>

#define REP(i, x) REPI(i, 0, x)
#define REPI(i, a, b) for (int i = int(a); i < int(b); ++i)
#define ALL(x) (x).begin(), (x).end()

typedef long long ll;
using namespace std;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  char C;
  cin >> C;
  cout << char(C + 1) << endl;

  return 0;
}

B

途中で平均を取ると小数点を扱わなくてはならない．しかし点数の総和だけで考えれば整数の範疇で解ける．

#include <bits/stdc++.h>

#define REP(i, x) REPI(i, 0, x)
#define REPI(i, a, b) for (int i = int(a); i < int(b); ++i)
#define ALL(x) (x).begin(), (x).end()

typedef long long ll;
using namespace std;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  int N, K, M;
  int sum = 0;
  int a;
  cin >> N >> K >> M;
  REP(i, N - 1) {
    cin >> a;
    sum += a;
  }
  int target = M * N;
  if (target - sum <= K) {
    cout << max(target - sum, 0) << endl;
  } else {
    cout << -1 << endl;
  }

  return 0;
}

C

今回最大のやらかし．

高橋君のペナルティ数は、高橋君が AC を 1回以上出した各問題において、初めて AC を出すまでに出した WA の数の総和です。

この一文から 一度もACしていない問題をWAしてもペナルティに含まれないというルールを導出しなければならないのだが，これができずに一度WA踏んでから20分以上悩んでいたらしい．

#include <bits/stdc++.h>

#define REP(i, x) REPI(i, 0, x)
#define REPI(i, a, b) for (int i = int(a); i < int(b); ++i)
#define ALL(x) (x).begin(), (x).end()

typedef long long ll;
using namespace std;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  int N, M;
  int wa = 0;
  int ac = 0;
  map<int, bool> aced;

  cin >> N >> M;
  vector<int> waed(N + 1, 0);
  REPI(i, 1, N + 1) { aced.insert(make_pair(i, false)); }

  int p;
  string s;
  REP(i, M) {
    cin >> p >> s;
    if (!aced.at(p)) {
      if (s == "WA") {
        ++waed.at(p);
      }

      if (s == "AC") {
        ++ac;
        wa += waed.at(p);
        aced.at(p) = true;
      }
    }
  }

  cout << ac << " " << wa << endl;

  return 0;
}

D

TODO

ダメだった点

問題文の読み違いによる大幅順位下落

良かった点

直近のABCではABC3完がキープできている

おわりに

ﾆﾎﾝｺﾞﾑｽﾞｶｼｲﾈ

2020-01-12

第6回ドワンゴからの挑戦状予選

参戦記録

結果

問題	ACまでに要した時間	AC
A	05:30	1
B	:	0
C	:	0
D	:	0

Rating	順位
611 (+44)	1464

解答

A

問題文を理解するのに少し時間がかかって提出が遅くなった印象．

#include <bits/stdc++.h>

#define REP(i, x) REPI(i, 0, x)
#define REPI(i, a, b) for (int i = int(a); i < int(b); ++i)
#define ALL(x) (x).begin(), (x).end()

typedef long long ll;
using namespace std;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  int N;
  cin >> N;
  string s[50];
  string x;
  int sum_t = 0;
  int t[50];
  REP(i, N) {
    cin >> s[i];
    cin >> t[i];
    sum_t += t[i];
  }
  cin >> x;
  int current_sum = 0;
  int ans = 0;
  REP(i, N) {
    if (s[i] == x) {
      ans = sum_t - current_sum - t[i];
      break;
    }
    current_sum += t[i];
  }

  cout << ans << endl;

  return 0;
}

B

アプローチが全く分からなかった．手も足も出なかった．

TODO

C

D

ダメだった点

良かった点

おわりに

2020-01-11

ABC150

TODO 参戦記録 ABC

atcoder.jp

結果

問題	ACまでに要した時間	AC
A	04:57	1
B	07:15	1
C	32:49	1
D	:	0

Rating	順位
unrated	1917

解答

A

そのまんま

#include <bits/stdc++.h>

#define REP(i, x) REPI(i, 0, x)
#define REPI(i, a, b) for (int i = int(a); i < int(b); ++i)
#define ALL(x) (x).begin(), (x).end()

typedef long long ll;
using namespace std;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  int K, X;
  cin >> K >> X;
  if (K * 500 >= X) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }

  return 0;
}

B

そのまんま．substr使うのとどっちが速度的に速いのかは検証してないけど，決め打ちで条件並べた方が間違いが少なくていいかなと思っている．

#include <bits/stdc++.h>

#define REP(i, x) REPI(i, 0, x)
#define REPI(i, a, b) for (int i = int(a); i < int(b); ++i)
#define ALL(x) (x).begin(), (x).end()

typedef long long ll;
using namespace std;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  int N;
  string S;

  cin >> N >> S;

  int ans = 0;
  REP(i, N - 2) {
    if (S[i] == 'A' && S[i + 1] == 'B' && S[i + 2] == 'C') {
      ++ans;
    }
  }

  cout << ans << endl;

  return 0;
}

C

next_permutationの使い方を調べていて時間がかかってしまった．N=8程度ならN!をそのまま計算しても間に合うが，これがN=50とかだともっと効率よく辞書順を求める方法を考える必要がある．

#include <bits/stdc++.h>

#define REP(i, x) REPI(i, 0, x)
#define REPI(i, a, b) for (int i = int(a); i < int(b); ++i)
#define ALL(x) (x).begin(), (x).end()

typedef long long ll;
using namespace std;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  int N;
  cin >> N;

  vector<int> order(N, 0);
  REPI(i, 0, N) { order[i] = i + 1; }
  int seq = 1;
  string key = "";
  map<string, int> perm;
  do {
    key = "";
    REP(i, N) { key += to_string(order[i]); }
    perm.insert(make_pair(key, seq));
    ++seq;
  } while (next_permutation(order.begin(), order.end()));

  // for (auto e : perm) {
  //   cout << e.first << ":" << e.second << endl;
  // }

  int a, b;
  char tmp_c;
  string tmp_s = "";

  REP(i, N) {
    cin >> tmp_c;
    tmp_s += tmp_c;
  }
  a = perm.at(tmp_s);

  tmp_s = "";
  REP(i, N) {
    cin >> tmp_c;
    tmp_s += tmp_c;
  }
  b = perm.at(tmp_s);

  cout << abs(a - b) << endl;

  return 0;
}

D

全然わからなくて死亡．あとで検討．

ダメだった点

D問題が全く手が出なかった．年末年始に勉強した合同式もそうだが，競プロでは（整）数論に強くないと解けない問題が結構あるようだ．

良かった点

ABCまでは割とスムーズに解けるようになったという感覚が得られた．しかしD問題までコンテスト中にACできなければ緑にはいけないであろう．まだまだ力不足．

おわりに

2020-01-09

モジュロ演算しながら四則演算する

競プロtips 数学

これは何か
先に結論
資料

これは何か

計算結果を $10^{9}+7$ で割った値を回答とする問題が頻出する．ARC058B，CODE FESTIVAL 2017 Final (Parallel) G，ABC145Dなどが該当する．AtCoderだけ見ても他にもたくさんあると思われるのだが，いかんせん問題文をすべて全文検索する方法がないので完璧にリストアップできないのが残念だ．

それはともかく，このような問題を解く場合はモジュロ演算の定石を知らないと即「詰み」になる演算があるため，事前に勉強しておく必要がある．本稿では対処法をまとめておく．

先に結論

証明で頻繁に必要になるので覚えておくべき合同式の性質

$(a,~b,~c,~k,~m,~x,~y\in\mathbb{Z})$

$a \equiv b \pmod{m} \Leftrightarrow a - b \equiv 0 \pmod{m}$
$a \equiv b \pmod{m} \Leftrightarrow a \times c \equiv a \times c \pmod{m}$
$a \pmod{m} = 0 \Leftrightarrow a = km$
$\gcd(a, m) = 1 \Leftrightarrow ax + my = 1 \Leftrightarrow ax \equiv 1 \pmod{m}$ （aとmが互いに素である場合，aは法mにおいて可逆）

四則演算の計算方法

演算	計算方法
加算	一度演算を行うごとにMODを取る
減算	一度演算を行うごとにMODを取る．最終結果が負の数の場合は法を足す．
乗算	一度演算を行うごとにMODを取る．
除算	割る数と法が互いに素である場合，割る数の逆元をかけていく．

注意事項

代入演算子を使うとMODが先に評価されてしまい，意図した通りの結果にならないため使わない

BAD a += b % MOD
GOOD a = a + b % MOD

逆元の求め方

$a~\div~b~\pmod{m}~(a,b,m \in \mathbb{Z})$ を求める場合， $\gcd(b, m) = 1$ であれば $bx+my=1~(x,y \in \mathbb{Z})$ が成立するため，この不定方程式を解いて，特殊解 $(x, y)$ のペアのうち１つの $x$ が逆元となる．
- 逆元はユークリッドの互除法でも解けるが，計算量を削減するために拡張ユークリッド互除法が一般に使用されるらしい．
- 参考
  - mathtrain.jp
  - noshi91.hatenablog.com
実装例（上述のQiita記事より）

#include <iostream>
using namespace std;

typedef long long ll;
int const MOD = 1000000007;

ll modinv(ll a, ll m) {
  ll b = m;
  ll u = 1;
  ll v = 0;
  ll t = a / b;

  while (b) {
    t = a / b;
    a -= t * b;
    swap(a, b);
    u -= t * v;
    swap(u, v);
  }
  u %= m;
  if (u < 0)
    u += m;

  return u;
}

int main() {

  ll a = 12345678900000;
  ll b = 100000;
  a %= MOD;
  cout << a * modinv(b, MOD) % MOD << endl;

  return 0;
}

二項係数

$_nC_k = \frac{n!}{(n-k)!k!} \pmod{m}$ の計算をする場合はメモ化により階乗の計算量を削減できる．

実装例（上述のQiita記事より）

#include <iostream>
#include <vector>
using namespace std;

const int MAX = 510000;
const int MOD = 1000000007;

typedef long long ll;
vector<ll> fac(MAX, 0ll);
vector<ll> finv(MAX, 0ll);
vector<ll> inv(MAX, 0ll);

void COMinit() {
  fac[0] = fac[1] = 1;
  finv[0] = finv[1] = 1;
  inv[1] = 1;
  for (int i = 2; i <= MAX; i++) {
    fac[i] = fac[i - 1] * i % MOD;
    inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
    finv[i] = finv[i - 1] * inv[i] % MOD;
  }
}

long long COM(int n, int k) {
  if (n < k)
    return 0;
  if (n < 0 || k < 0)
    return 0;
  // n! / (r!(n-r)!)
  return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

int main() {
  COMinit();
  cout << COM(510000, 123123) << endl;
}

資料

これにすべて書いてあるため，この内容を頭に叩き込んでおけば良さそう． qiita.com

2020-01-02

ABC149

参戦記録 TODO ABC

atcoder.jp

結果

開始時刻を間違えて20時40分ぐらいから慌てて解きはじめたのだが，後述するPCトラブルも相まって状況は最悪だった．

問題	ACまでに要した時間	AC	WA
A	46:21	1	1
B	71:41	1	3
C	81:23	1	0
D	:	0	0

Rating	順位
unrated	3118

解答

A

まさかのWAを決めてしまった．こんなもん何を間違える要素があるんじゃいと思うが問題文を焦って読んで出力する文字列の順序を間違えた．笑えない．

#include <bits/stdc++.h>

#define REP(i, x) REPI(i, 0, x)
#define REPI(i, a, b) for (int i = int(a); i < int(b); ++i)
#define ALL(x) (x).begin(), (x).end()

    typedef long long ll;
using namespace std;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  string S, T;
  cin >> S >> T;

  cout << T << S << endl;

  return 0;
}

B

単純に考えれば以下のステップで解けるクッソ簡単なシミュレーションである．

A = max(A-K, 0)
A > K ? K = 0 : K = A - K
B = max(B-K, 0)

しかし後述するように予期せぬ自体に焦っていたせいかWAを3回も出してしまった．A > KのケースでBが操作されないパターンを想定し忘れるとか，普段なら絶対やらないようなミスをしていた．これがratedなコンテストならこの時点でrating減少は避けられなかった．猛反省すべき結果である．．

#include <bits/stdc++.h>

#define REP(i, x) REPI(i, 0, x)
#define REPI(i, a, b) for (int i = int(a); i < int(b); ++i)
#define ALL(x) (x).begin(), (x).end()

typedef long long ll;
using namespace std;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  ll ans_0, ans_1, A, B, K;
  cin >> A >> B >> K;
  ans_0 = A;
  ans_1 = B;

  ans_0 = max(A - K, 0ll);
  if(A < K){
    K -= A;
    ans_1 = max(B - K, 0ll);
  }

  cout << ans_0 << " " << ans_1 << endl;

  return 0;
}

C

C問題まで来てようやく落ち着きを取り戻したのかこれはすんなり解けた．素数判定をする処理は $\mathcal{O} (\sqrt{N})$ であり，2から10,000の範囲であれば次の素数に遭遇するまでインクリメンタルに素数を求めていっても大した計算量にはならないと判断してnaiveに実装すれば解ける問題．

#include <bits/stdc++.h>

#define REP(i, x) REPI(i, 0, x)
#define REPI(i, a, b) for (int i = int(a); i < int(b); ++i)
#define ALL(x) (x).begin(), (x).end()

typedef long long ll;
using namespace std;

bool is_prime(int x) {
  for (int i = 2; i * i <= x; ++i) {
    if (x % i == 0) {
      return false;
    }
  }

  return true;
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  int X;
  cin >> X;

  int ans;
  while (true) {
    if(is_prime(X)){
      ans = X;
      break;
    }else{
      ++X;
    }
  }

  cout << ans << endl;

  return 0;
}

ところで，{ $x \in \mathbb{R} \mid 2 \leqq x \leqq 1000000$ } な整数集合において，素数がどの程度の間隔で含まれる気になったので調べてみた．最小1，最大114，平均値12.74，中央値10，標準偏差10.28という結果となった．そのため，最悪ケースでも113回素数判定をすれば良く，計算量が113 * $\sqrt{1000000}$ となったとして10⁵なので十分間に合うことが確認できた．

f:id:serihiro:20200102120050p:plain — 1から10⁶の範囲における素数を昇順で並べた時の前の素数との差分をplotした図．予行軸は素数の出現順を示し，縦軸は1個前の素数との差分を示す．最大で114であった．

雑な検証用コード．10⁶まで求めても手元のmacbook proで1秒未満で完了した．

#include <bits/stdc++.h>

using namespace std;

bool is_prime(int n) {
  if (n < 4) {
    return true;
  }

  for (int i = 2; i * i <= n; ++i) {
    if (n % i == 0) {
      return false;
    }
  }

  return true;
}

int main() {
  int seq = 1;
  int last_prime_number = -1;
  for (int i = 2; i <= 1000000; ++i) {
    if (is_prime(i)) {
      if (last_prime_number != -1) {
        cout << seq << ',' << i - last_prime_number << endl;
      } else {
        cout << seq << ',' << i << endl;
      }
      ++seq;
      last_prime_number = i;
    }
  }

  return 0;
}

D

ダメだった点

良かった点

おわりに

20時開始だったのを21時開始と間違えて盛大にやらかした．また，OSをCatalinaにアップデートした後にXCodeのアップデートを忘れていた為にローカルでC++のコードをコンパイルできないトラブルも発生した．その結果，散々な結果となった．システムトラブルでunratedになったのは不幸中の幸いであった．

2019-12-31

2019年総括

マイルストーン

これは何か
今年の状況
当初設定していた目標
- どれかのコンペで時間内に4完を達成する
- 緑コーダーになる
  - 結果
  - 対策
改善すべき点
新しい目標設定
総括

これは何か

2019年の競プロ活動の振り返り

f:id:serihiro:20191231193130p:plain — 現在のAtCoderレーティング推移．やっていなかった時期が長いせいでかなり損をしていることがよく分かる．

今年の状況

Rating: 567
色: 茶色
コンテスト参加回数: 9回

当初設定していた目標

どれかのコンペで時間内に4完を達成する

結果

未達成
3完が限界
未だにABCはD問題が大体解けない

対策

ABCのD問題を埋めまくる

現在のABC回答埋め率

f:id:serihiro:20191231193610p:plain — ABC埋め率．D問題になると急に下るのが笑える（笑えない）．

緑コーダーになる

結果

未達成
レーティングは右上がりなので目標に近づいてはいるが，ABCだけで緑コーダーになるにはD問題をコンスタントに解けないと難しいと思われるため，このままだとレーティングは上がらなくなると思われる

対策

ABCはD問題を解けるようになって今よりも高い順位を狙えるようになる

改善すべき点

bit全探索，最長増加部分列などの，競プロなら当然のように知ってなければいけない基本的なアルゴリズムが実装できない理由で詰むコンテストが多い．
- つまり基礎力が圧倒的に足りていない．
- dpだけはできないと話にならないので何も見なくても実装できるまで「もらうdp」の代表であるナップザック問題を繰り返し解いて覚えたが，dpだけ知っていてもほとんど意味がない．
すぐに諦めてしまう．
- 諦めない．
- 「WA踏んで順位落とすぐらいなら回答しない方がいいか」と諦めてしまうことが多いが，考えなければ力がつかない．
- とはいえレーティング下がるのはいやなので，過去問を大量に解いてトレーニングするしかない．

新しい目標設定

ABCでABCD4完および緑コーダー達成の期限を3月末に伸ばしてみる
- 緑コーダー達成には3ヶ月間でレーティングを 233 上げる必要があるが，ABCが5回あるとしたら毎回平均で47以上上げないと達成できない計算である
- これは毎回ABCD 4完を達成しないと厳しいのではないかと思われるが，それぐらいの目標の方が良さそうなので頑張ることにする．

総括

ABCの3完率は徐々に上がってきている．
- しかし，本腰入れてやり始める前に出たABCはすべてAB2完で終わっており（ABC125，ABC139，ABC144），直近だとABC147もbit全探索が実装できなくて2完で終わっている．C問題対策も引き続き続けないとまた変なところで2完で終わる可能性がある．
競プロの練習が継続的にできていない．やったりやらなかったりというのが続いている．そのせいで実力が伸びていない
- 11月に入ってから突然Over Watchでマスターを目指したいと思ってしまったのでそのせいで何というか何というかである．
- 来年は就職するということもあり，今以上に時間と体力が持っていかれることが予想される．そのため，１日１問でもいいから続けることをまず目標としたい．