2019-12-08

ABC147

ABC 参戦記録

結果

問題	ACまでに要した時間	AC	WA	TLE
A	01:51	0	0	0
B	07:05	0	0	0
C	:	0	0	0
D	:	0	0	0

Rating	順位
567 (+17)	2736

ABは7分ちょいでACできたがC,Dが全く手が出なかった．

解答

A

そのまま

#include <bits/stdc++.h>

#define REP(i, x) for (int i = 0; i < (int)(x); 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 a_1, a_2, a_3;
  cin >> a_1 >> a_2 >> a_3;

  if (a_1 + a_2 + a_3 >= 22) {
    cout << "bust" << endl;
  } else {
    cout << "win" << endl;
  }

  return 0;
}

B

そのまま

#include <bits/stdc++.h>

#define REP(i, x) for (int i = 0; i < (int)(x); 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;
  cin >> S;

  int ans = 0;
  int l = S.length();
  REP(i, l / 2) {
    if (S[i] != S[l - 1 - i]) {
      ++ans;
    }
  }

  cout << ans << endl;

  return 0;
}

C

総当りで全ての 人 について列挙する方法が分からなかった．この場合はbit全探索という手法を使うらしい．

qiita.com

とある整数 bit を0からN-1までループを回して，bitを2進数として見たときに REP(i, N) bit & (1<<i)で各フラグの状態をチェックしながら処理を行うと，N bitのフラグについて全パターンを網羅した処理が実行できるというもの．

この問題ではこれを使ってすべての 人 に対して正直者か不親切者かを全列挙して，各bitパターンで親切な人の証言をすべて検証して矛盾がないかどうかを調べる．計算量は $\mathcal{O} \left(2^{N}\right)$ だが，Nは最大で15なので十分間に合う．

#include <bits/stdc++.h>

#define REP(i, x) for (int i = 0; i < (int)(x); i++)
using namespace std;

void solve() {
  int n;
  cin >> n;
  vector<int> A(n);
  vector<vector<int>> X(n, vector<int>(n));
  vector<vector<int>> Y(n, vector<int>(n));

  REP(i, n) {
    cin >> A[i];
    REP(j, A[i]) {
      cin >> X[i][j] >> Y[i][j];
      X[i][j]--;
    }
  }

  int ans = 0;
  bool ok = true;
  REP(bits, (1 << n)) {
    ok = true;
    REP(i, n) {
      if (!(bits & (1 << i)))
        continue;
      REP(j, A[i]) {
        if (bits & (1 << X[i][j]))
          ok &= Y[i][j];
        else
          ok &= !Y[i][j];
      }
    }
    if (ok)
      ans = max(ans, (int)__builtin_popcount(bits));
  }
  cout << ans << endl;
}

signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);

  solve();
  return 0;
}

D

解説pdf読んだが分からんので解説放送を２，３回繰り返し観てようやく理解した．

結論としてはbitごとにxor取った和を計算して最後に10進数に戻せばよかった．このbitごとにxor取った和は，各 $A_i$ のk桁目における1と0の全組み合わせのみがxorの結果が1となるため， $2^{k} \times (0の個数) \times (1の個数)$ をk桁目ごとに計算して総和を取れば10進数に復元することができる．なるほどな〜〜〜

アライグマ「ABC147のA,D,E問題を作ったのだ！　C問題は、誰が正直者か2^N通りを全探索するのだ！　D問題は、bit毎に別々に考えればいいのだ！」
フェネック「検索サイトで"sum of xor"まで入れると"sum of xor of all pairs"がサジェストされてほとんど答えに近いコードが出てくるねー」
— 競技プログラミングをするフレンズ (@kyopro_friends) 2019年12月8日

#include <bits/stdc++.h>

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

typedef long long ll;
using namespace std;

const ll MOD = 1e9 + 7;

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

  int N;
  cin >> N;
  vector<ll> A(N);
  REP(i, N) { cin >> A[i]; }

  ll ans = 0, now = 0;
  ll x = 0;

  REP(i, 60) {
    x = 0;
    REP(j, N) {
      if (A[j] >> i & 1) {
        ++x;
      }
    }
    now = x * (N - x) % MOD;
    REP(j, i) { now = now * 2 % MOD; }
    ans = ans + now;
    ans = ans % MOD;
  }

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

ダメだった点

bit全探索ができなくても再起で深さ優先探索を実装すれば解けないこともなかった．アプローチは分かっていたので，早々にあきらめてしまったのはダメだったと思う．

良かった点

特になし

おわりに

bit全探索を使う問題は初めて解いたが，頻出パターンなので覚えておきたい．

2019-11-25

GigaCode 2019

参戦記録

atcoder.jp

今回はオンラインではなく，Yahoo! JapanのLODGEで開催されたオフサイトイベントでの参加．こういうイベントに参加するのが久々過ぎて，初対面の人とどう会話するか本気で困ってしまうというコミュ障っぷりを発揮した．それでも同じテーブルにいたメンバーのうち二人は社会人で，まだ話しやすかったのが救いではあった．

今回のイベントの参加者は高校生・高専生・大学生がボリュームゾーンで，最年少は中学２年生という感じで平均年齢はかなり低めだった．一方で，４０代で青コーダーという方も参加されており，自分もまだまだ頑張らねばならぬと思った．

コンテストでは青，橙，黄のガチ勢がものすごいスピードでACしまくってて，「あ、アイツら・・・一体どんな動きをしてやがるんだ・・・？！」みたいな感じになった．そういうのを間近で見るだけでもいい勉強になったし，LTはどれも面白かった．一人OpenMPの話してる人がいたので，もし次回があったらMPIかGEMMの話でもしようかなと思った．

今回のコンテストは出題が８問，制限時間が３時間で，集中力を維持するのが大変だった．開始から２時間ぐらいで一度完全に集中が途絶えてしまい「もうダメかな」と思ったが，最後の10分ぐらいで通せなかったサンプルを通して部分点を追加したりできて，「一見お手上げでも最後まで諦めなければスコアを伸ばせることもある」ということを体験できたという点は良かった．

結果

ペナルティなし，部分点ありなので遠慮せずに出しまくるという頭の悪い戦法をとって部分点を稼いだ

問題	ACまでに要した時間	AC	WA
A	15:42	1	1
B	4:37	1	0
C	17:02	1	1
D	-（部分点28点）	0	5
E	-（部分点15点）	0	7
F	-（部分点13点）	0	3

スコア	全体順位	オフサイト順位
356	259	確か31ぐらいで，これは経験者枠の中だとケツから２番目か３番目．．まだまだ未熟である．

f:id:serihiro:20191127161537p:plain — 当日の順位表

A

瞬殺かと思ったら問題読み違えて一手WAした．．
A問題でも最低サンプルは通さないといけないと深く反省した．これがABCなら詰んでた．

B

簡単なシミュレーションなのでそのまま解けば良い．ぐるぐる $\mathcal{O} \left(N\right)$ で解ける．

C

longで定義するべき変数をintで定義して1サンプル落として一回WA食らった
計算途中に一個でもintでは足りない変数がでてきたら整数は全部long longで定義するぐらいの安全策を取ったほうが無難かもしれない．この辺の定石がまだ分からない．

D

ACは無理なので，H=1の場合に限定して部分点を取りに行った．
個人的にはかなりムズいと思った．
完全回答としては二次元累積和を使って事前に計算したあとに条件に合うかどうかをチェックすれば良かったらしいが，まだ完全には理解してないので後で考える

参考回答

atcoder.jp

E

ACは無理なのでH=1の場合に限定して部分点を取りに行った
H=1の場合は「乗り換えが必須かどうか」「乗り換えが必須でなく，乗り換えが可能かどうか」という２つの分岐で解くことができる
H>1の場合は特定のポイントまでの時間を最小化する（もしくはスピードの合計値を最大化する）DPを行う必要があるが，相変わらずDPが苦手なので実装できそうにないと判断した

参考回答

atcoder.jp

F

感覚的には分かるが定式化できそうにないなと思ったので大人しくH=1の場合に（ｒｙ
H=1の場合は「連続した何もおいてない床」の個数を数えるでFAであるが，二次元になるとどう解くのが良かったのか．．正直今でもよくわかってないのでゆっくり考える

参考回答

atcoder.jp

2019-11-17

ABC145

ABC 参戦記録

atcoder.jp

結果

問題	ACまでに要した時間	AC
A	1:09	1
B	5:18	1
C	16:55	1
D	-	0

Rating	順位
550 (+64)	1850

A, B, Cはたまたま簡単だったので速く解けただけのような気もするが，久々にレーティングをプラス更新することができた
Dは解答の方針は分かったが，{}_{m+n} C _n の計算とmod 10000007の計算の実装がうまくできずに終了した
- この手の「大きい整数で割って回答する」パターンは結構出るので解けるようになっておかないといけない．そのため完全な準備不足
あとE問題はDPで解けそうだったけど前処理をどのようにするか分からなくて手が出なかった
今回のレーティングの上がり幅からして，次はABC超速解きに加えてDかEもACしないとレーティングがほとんど上がらないような状態に見える．．厳しくなってきた．

解答

D

合同式における加減乗除演算の計算方法と逆元の求め方は調べた上で以下に別途まとめた．

serihiro-competitive-programming.hatenablog.jp

コンテスト時は以下の式変形をするところまではできたが肝心の除算しながらCombinationを計算する方法が分からずに断念した．

$2n + m = X$
$n + 2m = Y$
$\Leftrightarrow m = (2Y-3)/3, n = Y - 2m$

#include <bits/stdc++.h>

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

typedef unsigned long long ll;
using namespace std;

const ll MOD = 1000000007;
const ll MAX = 1000000;
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 (ll 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() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  ll X, Y, n, m;
  cin >> X >> Y;

  COMinit();

  // 2n + m = X
  // n + 2m = Y
  // <=> m = (2Y - X)/3, n = Y - 2m;
  if ((X + Y) % 3 == 0) {
    m = ((2 * Y - X) / 3);
    n = (Y - 2 * m);
    cout << COM(n + m, m) << endl;
  } else {
    cout << 0 << endl;
    return 0;
  }

  return 0;
}

解説放送出てきた t.co
Writerのコメント

フェネック「C問題は、制約が小さいから全ての順列を全探索すれば解けるけど、O(N^2)で解けるから考えてみてねー。D問題は、(+1,+2),(+2,+1)のどっちを何回したかはすぐ分かるから、あとは二項係数を求めるだけだよ。組み合わせ問題の入門、mod逆元の入門のつもりで作ってみたけどどうだったかなー？」
— 競技プログラミングをするフレンズ (@kyopro_friends) 2019年11月16日

茶色雑魚勢には難しかったのだフェネック…

2019年に出たABCで唯一4完チャンスがあったABC145だが，逆元使って剰余取りながら除算する方法知らないとD問題だけはどうしようもなかった．

2019-11-10

第二回全国統一プログラミング王決定戦予選

参戦記録

atcoder.jp

結果

問題	ACまでに要した時間	AC
A	12:23	1
B	-	0
C	-	0
D	-	0

Rating	順位
486 (-30)	2961

一問目もっと早く出すだけでもっと順位上げられたんじゃなかろうか．．
最初naiveに二重ループで解こうとしたが，ワークロード見たら明らかにTLEするのでメモ化に変更した．そこに時間を取られた感．．かなり無駄なことをした
解説PDF見るとループすら使わずに厳密解を求めているが，重複を許すのであればn-1パターンの式が考えられるのだから，重複を排除するために2で割るというのは至極当然である（なぜこういう簡単なことに気づかないのか．．）
レートが順調に下がっているのだが，今の環境だともしかして茶色ですらなく灰色適正である可能性すらある．スプラトゥーン2のようにレートが下がっていくのは中々に辛いが，自分の努力だけで上げられる点ではかなり楽っちゃ楽である

以下，後日解き直したレポート（A，Bのみ）

A

コンテスト参加時はかなり頭の悪い $\mathcal{O}{(N)}$ で解いているが，偶数と奇数に場合分けして解けば $\mathcal{O}{(1)}$ で解ける．

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

  if (N % 2 == 0) {
    cout << (N - 1) / 2 << endl;
  } else {
    cout << N / 2 << endl;
  }

  return 0;
}

B

「無向グラフが構成できる」条件は以下の通りである

グラフの頂点が唯一一個存在する
各距離 $D_i$ に対して $D_i - 1$ となる別の $D_j$ がどの $D_i$ に対しても存在する

あとはこの条件を満たす $D_i$ かどうかをチェックしながら存在しえるパターンのグラフを数え上げればよい．なんどかWA踏んだが，「頂点は1個だけ」という条件を忘れていたのと，オーバーフロー防止の除算の仕方を間違ってオーバーフローして0になっていたという間抜けなミスであった．

#include <iostream>

int main() {
  int MOD = 1000000007;
  int a = 11111;
  int b = 123456;
  long long c = 987654;
  long long d = c;

  c *= a * b % MOD;
  d = d * a * b % MOD;
  std::cout << c << std::endl;
  std::cout << d << std::endl;

  return 0;
}

上記のコードを実行すると以下のように結果が異なる．

367130358707286
356137376

一度代入演算子を使って実装してしまい，% MODされていない結果が累積されてオーバーフローが発生した．今後気をつけたい．

#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 const BASE = 998244353;

ll f(int n, int m) {
  ll ans = 1;
  REP(i, m) { ans = ans * n % BASE; }
  return ans;
}

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

  cin >> N;
  vector<int> D(N);
  REP(i, N) { cin >> D[i]; }

  if (D[0] != 0) {
    cout << 0 << endl;
    return 0;
  }

  sort(D.begin(), D.end());
  ll ans = 1;
  int parent_count = 1;
  int children_count = 1;

  REPI(i, 0, N - 1) {
    if (D[i] == 0 && i > 0) {
      cout << 0 << endl;
      return 0;
    }

    if (D[i] != D[i + 1]) {
      if (D[i + 1] != D[i] + 1) {
        cout << 0 << endl;
        return 0;
      } else {
        ans = ans * f(parent_count, children_count) % BASE;
        parent_count = children_count;
      }
      children_count = 1;
    } else {
      ++children_count;
    }
  }

  ans = ans * f(parent_count, children_count) % BASE;

  cout << ans % BASE << endl;

  return 0;
}

2019-11-06

ABC140

ABC 過去問練習参戦記録

atcoder.jp

所要時間
解答メモ
- A
- B
- C
- D
  - 考え方
  - 感想

所要時間

10分AB2完，CD分からず．．．これは情けない

解答メモ

A

そのまま

#include <bits/stdc++.h>

#define REP(i, x) for (int i = 0; i < (int)(x); 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;

  cout << N * N * N << endl;
  
  return 0;
}

B

そのままsimulation
ほぼ解説pdfと同じでワラタ

#include <bits/stdc++.h>

#define REP(i, x) for (int i = 1; i <= (int)(x); 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;
  int A[20];
  int B[20];
  int C[20];

  long result = 0;
  
  cin >> N;
  REP(i, N) {cin >> A[i];}
  REP(i, N) {cin >> B[i];}
  REP(i, N-1) {cin >> C[i];}

  int last_a = -100;
  REP(i, N){
    result += B[A[i]];
    if(A[i] - last_a == 1){
      result += C[last_a];
    }
    last_a = A[i];
  }

  cout << result << endl;

  return 0;
}

C

以下が分からなかった
- sample1, 2が通るB_iが昇順のケースは書けたが，それ以外のケースを通す方法が分からなかった
- つまり嘘解放しか書けていない．条件を充足する汎用的なソリューションが分からないマン． youtu.be
解説放送を見て考える
- 条件の読み替えをすると以下のようになる
  - $A_1$ と $A_N$ : $B_1$ と $B_{N-1}$ からのみ成約を受ける
  - それ以外: $B_i$ と $B_{i-1}$ の成約を受けるため，結果的にどちらか小さい方が $A_i$

この問題のキモはおそらく

$B_k \geqq max(A_k, A_{k+1})$

という条件を

$B_k \geqq A_k \land B_k \geqq A_{k+1} \Leftrightarrow$

$A_k \leqq B_{k-1} \land A_k \leqq B_k$

と読み替えられるかどうかにかかっていると思われる．

このように読み替え，A_iに注目すると

$\displaystyle A_0 \leqq B_0$

$\displaystyle A_1 \leqq B_0 \land A_1 \leqq B_1$

$\displaystyle A_2 \leqq B_1 \land A_1 \leqq B_2$

$\displaystyle A_N \leqq B_{N-1}$

という条件が成り立つので，このまま実装すればよい．式の読み替えさえできてしまえば実装はめちゃくちゃ簡単なのだが，ここまで自力でたどり着くのが難しい気がする．

min, maxについては普段から使っている関数だが，他の当たり前につかっている定義についても前提を正確に意識しておかねばなるまい．例えば単純にドモルガンの法則で論理式を置き換えて解くような問題も競プロの世界ではあるのではないだろうか．

#include <bits/stdc++.h>

#define REP(i, x) for (int i = 0; i < (int)(x); 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;
  int B[100];
  cin >> N;
  REP(i, N - 1) { cin >> B[i]; }

  int ans = B[0];
  for (int i = 1; i < N - 1; ++i) {
    ans += min(B[i], B[i - 1]);
  }
  ans += B[N - 2];

  cout << ans << endl;

  return 0;
}

D

割とマジで全く手が出なかったので解説を読んで考える
以下が参考になった qiita.com

考え方

不幸な人が幸福に変化する条件は「目の前にいるやつが自分と同じ向きになる」のみ
操作は指定範囲を「全部反転する」のみ
- 例えば LLRRLL のようなケースでは，不幸な人はS[0]，S[3]，S[4]の3人で，幸運な人は3人である
  - 真ん中のRRを反転させると不幸な人はS[0]のみとなり，幸運な人が二人増える
  - 左端のLLを反転させると不幸な人はS[3]，S[4]の2人で，幸運な人は一人増える
  - 右端のLLを反転させると不幸な人はS[0]，R[5]の二人で，幸運な人は一人増える
- 不幸な人が減るケースはこの「両端を含まない範囲を反転させて二人増やす」か「両端を含む範囲を判定させて一人増やす」の2パターンしか存在しない
- また，反転を繰り返してLLLLL や RRRRR のように反転できたとしても，端の一人は必ず不幸になるため，幸福な人の最大人数はN-1
- 一方で，端を反転させる動作は端を含まない範囲の反転をやり尽くした後の1回だけしか行わないように操作できる
  - よって最後に1回だけ幸福な人を一人増やす操作を行うことができるので，基本的に二人増やす操作を貪欲的に行えば幸福な人を最大化できることが分かる
以上の条件を踏まえると，解法としては
- 「K回全部を使って反転させて二人ずつ幸福な人を増やした場合の幸福な人数とN-1のどちらかの最小値を求める」ということになる

#include <bits/stdc++.h>

#define REP(i, x) REPI(i, 0, n)
#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;
  string S;

  cin >> N >> K >> S;

  int ans = 0;
  REPI(i, 1, N){
    if(S[i-1] == S[i]){
      ++ans;
    }
  }

  cout << min(ans + 2 * K, N-1) << endl;

  return 0;
}

感想

twitterでエゴサしたら結構色んな解き方があるようだったが，個人的には↑野参考リンクの説明が一番しっくり来た
問題文だけを読むと決められた反転方法でしか最適解が得られないようにも読めるが，よく読めばそんなことは書いてなく，手元でいくつかのパターンを想定して試してみれば幸福な人がどのように増えるか検証できた．
サンプルも実はワナで，これにこだわると「LとRの並びが衝突するタイミングに注目すればいい」ということに気づきにくくなる．そのため，単純に最適化すべき指標を最適化することだけを考えてシミュレートすることが重要だと思った．

アライグマ「ABC140を解いて78分5完で261位相当だったのだ……。C問題は、a[i]≦min(b[i-1],b[i])になるのがわかるからこれを足すのだ。D問題は、R*L*の列に分割して、この区間全体を反転するようにすればいいのだ。端の処理がよくわからなくて1時間近く悩んだのだ……」
— 競技プログラミングをするフレンズ (@kyopro_friends) 2019年9月8日

ABC140おつかれさまでした。
Fが通って5完!!!!!!!!!
Eを解けないと判断してFにいったのが正解でした
リンクはFのコードhttps://t.co/UbEgyRgToS pic.twitter.com/9Tba48QPoR
— しんちゃん (@Sophia_maki) 2019年9月7日

ABC140お疲れ様でした！
A n**3
B bは普通にsumでよくて、cだけ丁寧に調べればOK
C Σmin(b[i], b[i+1]) +b[1]+b[n-1]
D 同じところは圧縮してRLRL……としてよい。成分の個数が3以上の間は1回の操作で2個増やせる。成分が2個なら1個増やせる。
— てんぷら (@tempura_cpp) 2019年9月7日

2019-11-05

ABC141

ABC 過去問練習

atcoder.jp

所要時間
解答メモ
- A
- B
- C
- D

所要時間

30分ABC3完答，Cで一回WA，D問お手上げ

解答メモ

A

Weathering with you.

#include <bits/stdc++.h>

#define REP(i, x) for (int i = 0; i < (int)(x); 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;
  cin >> S;

  if(S == "Sunny"){
    cout << "Cloudy" << endl;
  }else if(S == "Cloudy") {
    cout << "Rainy" << endl;
  }else{
    cout << "Sunny" << endl;
  }
  
  return 0;
}

B

そのまま解く

#include <bits/stdc++.h>

#define REP(i, x) for (int i = 0; i < (int)(x); 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;
  cin >> S;

  bool result = true;
  // odd
  for(int i=0; i < S.length(); i+=2){
    if(!(S[i] == 'R' || S[i] == 'U' || S[i] == 'D')){
      result = false;
    }
  }

  if(!result){
    cout << "No" << endl;
    return 0;
  }

  if(S.length() == 1){
    cout << "Yes" << endl;
    return 0;
  }

  // even
  for(int i=1; i < S.length(); i+=2){
    if(!(S[i] == 'L' || S[i] == 'U' || S[i] == 'D')){
      result = false;
    }
  }

  if(result){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }

  return 0;
}

C

問題をもし1問も解答できなかった場合の最終スコアはK-Q と考えると，K-Qに正答できた問題数を足して1以上ならOKと読み替えられるので $\mathcal{O} \left(Q+N\right)$ で解ける
一回なぜかWA食らったが，if(score[i] + K - Q > 0) でオーバーフローしたためと考えられる（全部 long longで宣言するように修正しただけでACになった）

#include <bits/stdc++.h>

#define REP(i, x) for (int i = 0; i < (int)(x); 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 N, Q, K;

  cin >> N >> K >> Q;

  ll score[100001];
  REP(i, N+1) {score[i] = 0;}

  int tmp_a;
  REP(i, Q) {
    cin >> tmp_a;
    ++score[tmp_a];
  }

  for(long i=1; i<=N; ++i){
    if(score[i] + K - Q > 0){
      cout << "Yes" << endl;
    }else{
      cout << "No" << endl;
    }
  }

  return 0;
}

D

以下が分からなかった
- どういう戦略で割引券を使うのが最適か
  - 値段でソートして一番高いやつから多く使って行けばいいんじゃね？と思って実装してみたが違った
解説PDF
- 以下が分からなかった
  - 最初の定理については何となく分かる
  - $\lfloor \frac {X} {2^{Y}} \rfloor = \lfloor \lfloor X / 2 \rfloor / 2 \rfloor \dots$ は毎回の除算で小数点以下を切り捨てているので雰囲気は分かる
  - しかしこの定理に基づいてどう実装するか？priority_queueの使い方知らないマン
解説動画 youtu.be
- めちゃくちゃわかりやすくて感動した．↑の定理はたしかに2進数で考えると「そりゃそうやな」と腑に落ちる（けど数学的に証明できないと使うのは怖い）．
- 普通に考えれば「その時点で一番高いものを半額にしていけばよい」というのは確かにそうなのでそう解けば良かったが，↑の定理が思いつかないと厳しいか，あるいは「このような定理が成り立つ．知らんけど．」で，一か八かでこの方針で解くことになりそうではある．D問題解けた人はどうやって導いたんだこれ？

アライグマ「ABC141を解いて90分全完+4WAで80位相当だったのだ。C問題は、毎回ポイントの変化を計算しなくても、ラウンドが終わったときのポイントは「K-Q+正解数」になるからすぐ計算できるのだ。D問題は、金額が高い方から貪欲に券を1枚ずつ使うのだ」
— 競技プログラミングをするフレンズ (@kyopro_friends) September 16, 2019

santa98.hatenablog.com

bondo.hateblo.jp

みんな大して苦労せずに解いてるところを見るに，競プロ勢にとってはこの程度の問題は普通なのかもしれない．．．
ともかくpriority_queue使えないと同様の問題で詰むのがよくわかったので，使い方と時間計算量をちゃんと調べておく必要がある
解説見て書いた解答
- priority_queueの時間計算量は，push と pop は $\mathcal{O} (\log N)$ , top は $\mathcal{O}(1)$ らしい
- よって時間計算量は $\mathcal{O} (M \times 2 \times \log N)$

#include <bits/stdc++.h>

#define REP(i, x) for (int i = 0; i < (int)(x); 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;
  priority_queue<ll> A;
  ll tmp_a;

  cin >> N >> M;
  REP(i, N) {
    cin >> tmp_a;
    A.push(tmp_a);
  }

  REP(i, M) {
    tmp_a = A.top();
    A.pop();
    A.push(floor(tmp_a / 2));
  }

  ll result = 0;
  REP(i, N){
    result += A.top();
    A.pop();
  }

  cout << result << endl;

  return 0;
}

2019-11-04

ABC142

ABC 過去問練習

atcoder.jp

所要時間
解答メモ
- A
- B
- C
- D

所要時間

25分ABC3完答，D問途中で分からず

解答メモ

A

そのまま解けばいいのだが， $\frac {(N-N/2)} {N}$ で求まるのでわざわざ場合分けする必要はなかった．
あとstd::setprecisionを初めて使ったが，今回の問題は誤差が10^-6という指定だったので解説のようにsetprecision(10) と精度を高めにしておいた方が境界値で変なバグは出さなくて良いかもしれない．

#include <bits/stdc++.h>

#define REP(i, x) for (int i = 0; i < (int)(x); 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;

  if(N == 1){
    cout <<setprecision(6) <<  1.0 << endl;
    return 0;
  }

  if(N%2 == 0){
    cout << setprecision(6) << 0.500000 << endl;
  }else{
    cout << setprecision(6) << (((N-1) / 2.0) + 1.0) / N << endl;
  }
  
  return 0;
}

B

そのまま解けば良い

#include <bits/stdc++.h>

#define REP(i, x) for (int i = 0; i < (int)(x); 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, tmp_h;

  int result = 0;

  cin >> N >> K;
  REP(i, N) {
    cin >> tmp_h;
    if(tmp_h >= K){
      ++result;
    }
  }

  cout << result << endl;
  
  return 0;
}

C

順番を求めよとあるのでsortを疑うが，どの生徒が何番目なのかは決定論的に決まるのでsortする必要はなく，ループを回しながら順序のindexに生徒の番号を格納していけば解ける

#include <bits/stdc++.h>

#define REP(i, x) for (int i = 0; i < (int)(x); 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, tmp_a;
  int A[1000001];

  cin >> N;
  REP(i,N){
    cin >> tmp_a;
    A[tmp_a - 1] = i;
  }

  bool first = true;
  REP(i, N){
    if(first){
      cout << A[i] + 1;
      first = false;
    }else{
      cout << " " << A[i] + 1;
    }
  }
  cout << endl;

  return 0;
}

D

自力で解けなかったやつ
互いに素 と出てきた時点で解答は素数だろうという目星がつけられなかった
自力で考えた12 18だけ通るウソ解答

#include <bits/stdc++.h>
#include <numeric>


#define REP(i, x) for (int i = 0; i < (int)(x); 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 A, B;
  cin >> A >> B;

  vector<int> candidates;

  for(int i=1; i < max(sqrt(A), sqrt(B)); ++i){
    if((A % i == 0) && (B % i == 0)){
      candidates.push_back(i);
    }
  }

  ll result = 0;
  for(int i=0; i < candidates.size(); ++i){
    for(int j = i+1; j<candidates.size(); ++j){
      cout << candidates[i] << ":" << candidates[j] << ":" << __gcd(candidates[i], candidates[j])  << endl;

      if(__gcd(candidates[i], candidates[j]) == 1){
        ++result;
      }
    }
  }

  cout << result << endl;

  return 0;
}

結果

解答

A

B

C

D

ダメだった点

良かった点

おわりに

結果

A

B

C

D

参考回答

E

参考回答

F

参考回答

結果

コメント

解答

D

結果

コメント

以下，後日解き直したレポート（A，Bのみ）

A

B

所要時間

解答メモ

A

B

C

D

考え方

感想

所要時間

解答メモ

A

B

C

D

所要時間

解答メモ

A

B

C

D