public

# 公開の記録

{{toc}}

## ABC 274 E の TLE <2023-01-03 Tue 19:49>

独力で解けなかったので https://atcoder.jp/contests/abc274/submissions/35636696 の回答を参考に実装してみたら、TLE になってしまったので、原因を調べてみた。

ほぼ同じ実装である https://atcoder.jp/contests/abc274/submissions/35887265 が AC なのに、なぜ TLE したのかと思って細かく見ていったところ、DP の漸化式に相当する「訪問済みノードのビットセット」の更新処理に問題があることが分かった。

公式回答の Python では以下のように、ビットセット `s` に `(1<<j)` というビットを追加するために XOR を使用している。

```

     if dp[j][s^(1<<j)]>new_dist: dp[j][s^(1<<j)]=new_dist

```

Ruby に書き換える際に、この XOR を深く考えず安直にコピーしてしまったために、余計な遅延が乗って時間制限をオーバーしてしまったということだった。

実際簡単なベンチマークでビット XOR 演算子とビット OR 演算子の速度の違いを比較してみる。

```

$ cat xor_or.rb

S = (1<<17)*17*17

t1 = Time.now

S.times do |i|

  x = i | (S - 1)

end

t2 = Time.now

p t2 - t1

t1 = Time.now

S.times do |i|

  x = i ^ (S - 1)

end

t2 = Time.now

p t2 - t1

```

ABC274E の最大規模に相当するループ回数で実行してみると、以下のように 1 秒程度の差が生じた。

XOR は OR よりも遅いことを認識しておかないといけない。

```

$ ruby xor_or.rb

2.797993445

3.898028078

```

少し関係ないが、本問題を検証している上で、ビットカウントのルーチンの効率について調べてみたので、一応書いておく。

```

$ cat popcount_test.rb

# https://stackoverflow.com/questions/1639723/ruby-count-the-number-of-1s-in-a-binary-number に基づく最適なルーチン

def popcount(x)

  m1 = 0x55555555

  m2 = 0x33333333

  m4 = 0x0f0f0f0f

  x -= (x >> 1) & m1

  x = (x & m2) + ((x >> 2) & m2)

  x = (x + (x >> 4)) & m4

  x += x >> 8

  return (x + (x >> 16)) & 0x3f

end

M = 20

t1 = Time.now

(1 << M).times do |i|

  popcount i

end

t2 = Time.now

# 整数型に [] でアクセスすると bit がセットされているかどうかで 0, 1 を返す

t3 = Time.now

(1 << M).times do |i|

  M.times.count {|j| i[j] > 0}

end

t4 = Time.now

t5 = Time.now

(1 << M).times do |i|

  i.digits(2).size

end

t6 = Time.now

p t2 - t1

p t4 - t3

p t6 - t5

$ ruby popcount_test.rb

0.355551277

3.333421961

0.839962182

```

ということで、独自ルーチン `popcount` を用いるのが最速のようだ。

ライブラリに登録しておこう。

## AtCoder ABC 276 E について <2022-11-06 Sun 00:07>

https://atcoder.jp/contests/abc276/editorial/5162

公式解法のとおり、BFS や DSU を用いたにも関わらず TLE を解決できなかったので振り返る。

アルゴリズムの問題ではなく、Ruby の基本的なデータ構造の問題で遅くなっていた。

グリッド問題の入力は以下のような文字列で与えられるが、これをどういうデータ構造に落とすのがよいかという問題。

```

5 7

.#...#.

..#.#..

...S...

..#.#..

.#...#.

```

安直なものでは以下のような格納方式が考えられる。

1. 1 つの文字列として格納する方式

   ```

   ".#...#...#.#.....S.....#.#...#...#."

   ```

2. 1 次元の文字の配列として格納する方式

   ```

   [".", "#", ".", ".", ".", "#", ".", ".", ".", ...]

   ```

3. 各行ごとの文字列の配列として格納する方式

   ```

   [".#...#.",

    "..#.#..",

    "...S...",

    "..#.#..",

    ".#...#."]

   ```

4. 文字の 2 次元配列として格納する方式

   ```

   [[".", "#", ".", ".", ".", "#", "."],

    [".", ".", "#", ".", "#", ".", "."],

    [".", ".", ".", "S", ".", ".", "."],

    ...]

   ```

私はこれまで割と雰囲気で 1. や 2. を選んでしまっていた。

また、過去に別問題を変に学習してしまったようで 2D 配列は 1D 配列にした方が速い (添字を毎回変換していた) と思い込んでいたのもある。

一回自前で計測しておくと安心ということで測ってみた。

1000x1000 の適当なグリッドを作って各セルを走る処理を 5 回実行した時間を比較する (単位は秒)。

|   |                    | データロード | 全処理時間 |

|---|--------------------|--------------|------------|

| 1 | 文字列             | 0.22         | 4.35       |

| 2 | 一次元文字配列     | 4.96         | 6.49       |

| 3 | 行ごとの文字列配列 | 0.006        | 5.12       |

| 4 | 二次元文字配列     | 0.21         | 2.84       |

データロードにおいて一次元文字配列が遅いのは `array1 + array2` のような連結処理をしているからで、これは以前遅いことを学習済み。

文字列の添字でのアクセスよりも `string.chars` で文字れ配列に分割した方が、データロードには多少時間がかかるが、アクセスは高速になるようだ。

ということで、今後はグリッド問題が出た時は二次元文字配列で処理するようにしてみる。