AtCoder Beginner Contest 159に参加した話。

結果から。

f:id:horoyoisawa:20200322225546p:plain

Ranking: 2290th / 8352
Performance: 1068
Rating: 780 → 815

緑になった。５問目が解けなかった。

順に見ていく。

A - The Number of Even Pairs

ペアの和が偶数になる様にペアを選ぶ方法が何通りあるか。奇数をa個、偶数をb個として求めるのはa * (a - 1) / 2 + (b * (b - 1)) / 2。

B - String Plindrome

「強い回文」の条件が与えられて、その条件を満たしているかを判定する問題。条件をしっかり読んで実装すればおけ。（回文の判定はreverseして一致するかでできる）

C - Maximum Volume

縦、横、高さの長さの合計がLである直方体の体積で考えられる最も大きい値はいくらか。相加相乗平均の不等式を使えばすぐにわかる。これがわからずアホほど時間を使ってしまった。結局解けたが。

D - Banned K

前計算をしておいて、あとはkの値に応じて加減をすれば答えが出る。

E - Dividing Chocolate

解けなくて絶望した問題。厳密には違くて解けることはわかっていたが、実装できず一番辛かった。解く方法は簡単で、Hが大きくても10なので全探索をすることができる。あとは縦にどうやって割れ目を入れるかを貪欲でやっていくだけ。言葉で説明するのは簡単なのだが、実装力がなさすぎて解けなかった。コンテストが終わったあと、まじで首吊ろうかなと思ったくらい解けなかったのが辛すぎた。自分の実力のなさ、そして実装力のなさを呪う。

(翌日追記）

計算量恐れずに実装したらできた。計算量を恐れて手が震える現象本当にどうにかして欲しい（自分の解法に自信がもてず、やたらと手を動かすのが躊躇われる現象）。ゆっくり考えて解けてもコンテスト中に同じことができるかって言われると。。わからんとしてか言いようがない。

提出したコードはこちらから。

atcoder.jp

他の人のコードを見てみる。ABC大抵1位のhitonanodeさんのコードを参照。リンクは以下から。

atcoder.jp

#include <bits/stdc++.h>
using namespace std;
int main() {
  int H, W, K;
  cin >> H >> W >> K;
  vector<string> S(H);
  // これいいな
  cin >> S:
  int ret = 1e9;
  REP(bs, 1 << (H - 1)) {
    int nb = 1 + __builtin_popcount(bs);
　　 // __builtin_popcountってなんやねん
    vector<int> cnt(nb);
    int tmp = __builtin_popcount(bs);
    // sucは隣に仕切りがあるかないかを表すものだけど、最初なんでfalse？
    // なるほどね。あとでsuc=trueにして計算し直すからどっちにしろ引っかかるのか。
    bool suc = false;
    REP(j, W) {
      int now = 0;
      REP(i, H) {
        if(S[i][j] == '1') cnt[now]+++;
        // これ今度から使える
        if((bs >> i) & 1) now++;
      }
      if( *max_element(ALL(cnt)) > K) {
        if(suc) {
          tmp = 1e9;
          break;
        }
        tmp++;
        for(auto & x : cnt) x = 0;
　　　　　// 一つ手前に戻ってもう一回計算し直す。
        j--;
        suc = true;
        continue;
      }
      suc = false;
    }
    chmin(ret, tmp);
  }
  cout << ret << endl;
}

__builtin_popcountって何？？？？？

gccのビルドイン関数らしい。整数を引数として渡すと、セットされているビットの数を返してくれる関数。

他にもgccにはBuild-in funcitonがいくつかある。以下の記事を参照。

www.geeksforgeeks.org

上位陣のコードは見ていて気分がいいなぁ。

F - Knapshot for All Segments

問題を見ていない。あとで考察したら解説と共に追記しておく。

感想と反省

さて恒例の自分が解けた問題までで最速の人のパフォーマンスを見てみよう。

今回はこの方。

f:id:horoyoisawa:20200322231530p:plain — D問題まで解けている人で最も順位が高い人

Ranking: 1231st / 8352
Performance: 1396

水色パフォ欲しかった。。

反省について

スピードはいつも言っている通り練習して。
今回のコンテストでわかったのは、解放がわかっても実装できなければ意味ないよねということ（今回のE問題なんで実装力とかそんな問題じゃないぞ！客観的に。。）細かいインデックスの調整が本当にわからなかった。ここからここまでのホワイトチョコレートはどうなるんだろう。。なんてことを考えていたらコンテストが終わっていた。大まかな方針としてはあっていたが細かい部分で考えきれていなかった。ちゃんと自分で実装したら実力がつくかも。
あとはF問題を無視しないで考えよ。
早くコードを書いている人がどんなコードを書いているのか観察する。なんか発見が会ったら追記しとく。

ああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああ

寝よ。

horoyoisawaのゴミ箱

いろいろ書きます