AtCoder Beginner Contest113

- [コンテスト](https://beta.atcoder.jp/contests/abc113)

## C問題「[ID](https://beta.atcoder.jp/contests/abc113/tasks/abc113_c)」

## 考察

### 本番での考察

- やるだけっぽい。けど実装がだるそう
- 最初は`set`を使った。そして、`set`が何番目かを高速に求める方法を探した。ググって`distance()`という関数が出てきた。なんか上手いこと高速に処理してくれそうだからこれを使った。が、TLE。やはり`set`の要素が何番目にあるかは$O(N)$になってしまうようだ。
- なので、`map`をつかった。`map`でデータをソートしつつ格納して、最後に番号を振れば良いという考えに至った。
- 考察終了



## 実装

### [コード](https://beta.atcoder.jp/contests/abc113/submissions/3547509)

```cpp
#include <bits/stdc++.h>
using namespace std;

#define int long long

int N, M;
int P[111111], Y[111111];
int cnt[111111];

// 1スタート
// G[県]<年, 番号>
map<int, int> G[111111];

signed main() {
   // 入力
   cin >> N >> M;
   for (int i= 0; i < M; i++) {
      cin >> P[i] >> Y[i];
      G[P[i]][Y[i]] = 0;
   }

   // mapによって年でソートされているため、それに従い番号を振る
   for (int i = 1; i <= N; i++) {
      int cnt = 1;
      for (auto x : G[i]) {
         G[i][x.first] = cnt;
         cnt++;
      }
   }

   for (int i= 0; i < M; i++) {
      int p = P[i], y = Y[i];
      int number = G[p][y]; // G[県][年] = 番号
      printf("%06lld%06lld\n", p, number);
   }

   return 0;
}

```

- もっと良い方法があるのかもしれない。けど、調べる気力が無い。それに、これでも十分綺麗



## 要点

- コードを書く前に計算量を確認する
  - 気が抜けてるとよく忘れる（よくない）
- `distance()`を`set`につかうと計算量は$O(N)$
  - `vector`だと$O(1)$らしい。結構柔軟に対応してくれるみたい
  - 使う機会はあんまりなさそう
- `map`の配列
  - 値を2つ指定すると1つの値が出てくるという実装に役立った。
  - 初めて書いた気がする。
  - こういう書き方もあるんだなー程度に思っておく



## 感想

- 数学を使わないC問題久しぶりな気がした。
- 正答率も高かったのでみんな数学苦手なのかなーとか思ってた。



## D問題「[Number of Amidakuji](https://beta.atcoder.jp/contests/abc113/tasks/abc113_d)」

## 考察

### 本番での考察

- パターンを列挙して、それを組み合わせるのかなーと思う
- なんか複雑だし、それじゃ無理そうだなーってなる。
- 経路を求めるDPと似た雰囲気を感じた。なのでDPで解けそうだなーって思う。
- どういう経路があるかを考えた。以下の2パターンだけで大丈夫かなーと思った（全然大丈夫じゃ無いけど）。

![a.jpg](https://qiita-image-store.s3.amazonaws.com/0/218584/c26f3f81-a8f3-9d10-8f19-7d8911920dbc.jpeg)



- とりあえず、画像のような経路をたどる方針でDPを書いた。
- 答えが合わない
- 終了

### 理想の考察

- 全探索は計算量的に無理そう
- 雰囲気が経路を数え上げるDPっぽい。なので、DPで解けそう
- 2次元グリッドの経路と違って今回はあみだくじなので、線があるところと無いところがある。なので、線がある部分だけ考えて遷移するというのが必要になる。
- ある高さをみたとき横の線は引くか、引かないかの2通りとなる。なので、bit全探索で列挙できる。それをそれぞれの高さについて列挙してやれば良い。それぞれの高さは独立している。なので、毎回普通にbit全探索で列挙すれば良さそう。ただ、隣り合う線が引かれていたらはじくという処理が必要。
- あとは、遷移を考える。bit全探索で求めたbitを元に遷移を書いていく。画像にすると、以下のように遷移したい。こんな感じの遷移を全ての高さについて行えば良さそう。

![b.jpg](https://qiita-image-store.s3.amazonaws.com/0/218584/b168c7d0-0d23-2659-0450-78b975b7f8ec.jpeg)


- 横線を全探索したときに、bitが立っているのを見つけたら右への遷移と左への遷移を一気に処理する（ホントは別々に処理しようとしたけどなんかバグったからやめた）。そのあと$i$を余分にインクリメントする。bitが立っていない場合、真っ直ぐに遷移する。
- 考察終了



## 解法

### 大体の方針

- ある高さについて、bit全探索で全ての組み合わせを列挙する
- 列挙した組み合わせをDPで数え上げる。

### 解法

1. DPテーブルを用意して`dp[0][0] = 1`で初期化する。
2. 高さについて、$1 \leq h \leq H$の範囲で全探索する。
   1. この高さについて、bit全探索でパターンを全列挙する
      1. このとき、隣り合っているビットがあるならこの先の処理を飛ばす
      2. 高さと横棒のパターンが決まったので、DPを遷移させる
         1. `mask`を見て、立ってるビットがあったら遷移する。立ってるビットからは右に遷移する。立ってるビットの一つ右から今見ている部分にも遷移する。ビットが立ってなかったら真っ直ぐ遷移する。

- 言葉で書いてみたけど、すごい分かりづらい。コードを見た方がよさそう。



## 実装

### [コード](https://beta.atcoder.jp/contests/abc113/submissions/3547229)

```C++
#include <iostream>
using namespace std;

using ll = long long;

const ll MOD = 1e9+7;

int main() {
   // 入力
   int H, W, K;
   cin >> H >> W >> K;

   // DPテーブルを初期化する
   ll dp[H+1][W];
   fill(dp[0], dp[H+1], 0);
   dp[0][0] = 1;

   for (int h = 0; h < H; h++) { // それぞれの高さについてループを回す
      for (int mask = 0; mask < (1<<(W-1)); ++mask) { // bit全探索のループ

         // 横線が隣り合っていないかチェック
         bool ok = true;
         for (int i = 0; i < W-2; ++i) {
            // これで末尾が11のときにはじくことが出来る
           if (((mask >> i) & 3) == 3) ok = false;
         }
         // 隣り合っていたらこの先の処理を飛ばす
         if (!ok) continue;

         for (int i = 0; i < W; i++) {
            // 横線を見つける
            if ((i < W) && ((mask >> (W - (i+2)))&1)) { // 右と左の遷移
               // 右への遷移と左への遷移を一気に処理する
               dp[h+1][i+1] += dp[h][i];
               dp[h+1][i+1] %= MOD;
               dp[h+1][i] += dp[h][i+1];
               dp[h+1][i] %= MOD;
               i++;
            } else { // まっすぐの遷移:
               dp[h+1][i] += dp[h][i];
               dp[h+1][i] %= MOD;
            }
         }
      }
   }

   cout << dp[H][K-1] << endl;

   return 0;
}

```

### 改善

- Misterさんのコードを参考にコードを書いた。[これ](https://beta.atcoder.jp/contests/abc113/submissions/3547296)
- 遷移の部分を以下のように書いている

```cpp
// 遷移先のインデックスを示す配列
int perm[W];
// 最初は真っ直ぐ遷移するインデックスで初期化する
for (int i = 0; i < W; i++) perm[i] = i;

// 横線を見つけたらswapして遷移先を入れ替える
for (int i = 0; i < W-1; i++) {
  if ((mask >> i) & 1) {
    swap(perm[i], perm[i+1]);
  }
}

// 配列permの通りに遷移させる
for (int i = 0; i < W; i++) {
  dp[h+1][perm[i]] += dp[h][i];
  dp[h+1][perm[i]] %= MOD;
}
```

- 頭良すぎて自分では思いつけないと思う。なので考察の部分にも書かなかった。でもこういうのを自然に思いつけるといいなー（願望）



## 要点

- **部分的に考える**

  - あみだくじは全体を見るとすごく複雑である。今回はパターンも膨大で、頭が爆発しそうになる
  - ただ、1マスだけ注目すると、「選ぶか、選ばないか」の2通りである事が分かる。
  - これがわかると、行は「101000」みたいに出来ることが分かる。これはbit全探索で列挙できる。
  - そして、それを全ての高さについて適応すれば全てのあみだくじを列挙することが出来る。
  - 画像にすると以下のような感じ。ある部分について考え、部分の範囲を広げていくと考察しやすいのかなーと思った。

![c.jpg](https://qiita-image-store.s3.amazonaws.com/0/218584/fe380d10-7813-9000-468c-8c80a7e02d87.jpeg)


- **選ぶか、選ばないかの2通りを列挙するにはbit全探索を使う**

  - 最初はとりあえず全探索を考えたけど、全探索する方法が思い浮かばなかった。
  - 組み合わせが無限通りあるように思えて、どう列挙すれば良いか分からなかった。
  - ある高さのみに注目すれば、「線を引くか引かないか」になる。

- **細かいことは後で考える**

  - 全探索が思いつかなかった原因のひとつに、条件が複雑だったことが挙げられる。
  - 隣り合う線があってはならないという条件に引っ張られて複雑に考えすぎた。
  - まずは列挙して、条件に合わないものは弾くという考えが必要だった。
  - とりあえず全探索の方法を考えて、細かいことは後で考える方針で行けばよかった。



## 感想

- これムズくないか？？？まあ理解はできたけど
- 横線をbit全探索して、それを元に数え上げDPをする。実装も少し複雑。これ本番解けねえぞ
- 参考にした記事は[これ](https://misteer.hatenablog.com/entry/ABC113)。めっちゃわかりやすい神のような記事。ありがたや～。
- あと、誤読してた。経路のDPに引っ張られて、経路数を求めるDPだと思ってた。けど、あみだくじのパターン数を求める問題だった(takeoさんありがとう！)
- あみだくじ　線があったら　曲がります
- DPで　数え上げると　フィボナッチ