Wiki » History » Revision 5
Revision 4 (hori, 04/24/2023 11:39 PM) → Revision 5/6 (hori, 04/25/2023 10:17 PM)
# 公開の記録
{{toc}}
## <2023-04-25 Tue 22:05> ABC297 E
https://atcoder.jp/contests/abc297/tasks/abc297_e
優先度付きキューを用いた解法は比較的容易に思いつくことはできた。
ただ、ちょっとした違いが微妙な速度の差につながり TLE するかどうかに効いてしまい、解決まで時間がかかってしまったので、メモしておく。
AC した解法は以下である。
```
N, K = gets.split.map(&:to_i)
A = gets.split.map {|i| i.to_i}.uniq
n = A.size
pq = PriorityQueue.new {|x, y| x < y}
pq.push(0)
tmp = {}
x = -1
while x < K
val = pq.pop
x += 1
n.times do |i|
if tmp[val + A[i]].nil?
pq.push(val + A[i])
tmp[val + A[i]] = true
end
end
end
puts val
```
これだとサンプルの 3 は 2.7 秒程度で通る。
一方、当初 while ループの中を以下のようにしてしまっていて、5.8 秒くらいかかり、TLE になっていた。
```
while x < K
val = pq.pop
next if tmp[val]
tmp[val] = true
x += 1
n.times do |i|
pq.push(val + A[i])
end
end
```
優先度付きキューにとりあえず入れて、出してから既に出現済みかどうかをチェックするよりも、優先度付きキューに入れる前に、出現済みかどうかをチェックして除外する方が、キューに入れるという重めの操作をを減らすことができて速い、ということのようだ。
ハッシュのチェックは、優先度付きキューの取り出し処理よりも速い、これはまあ実感として分かるが、そこが差になるということは知っておかねばなるまい。
## <2023-04-24 Mon 23:31> Anthy の日本語入力
手元の作業マシンは Ubuntu 20.04 のデスクトップ版を利用していて、日本語入力には Mozc を使っていた。
ところが、どうも誤変換が多くて使い物にならない [^1] ということで Mozc は諦め、Anthy に戻した。
いつ頃からそうなったのか不明だが、キーバインドを柔軟に割り当てられるようになったため、問題なく戻せた。
個人的に一番重要と思うのは IME のオン・オフ (日本語入力と直接入力) のために指を大きく移動させたくないというのと、オンとオフを異なるキーバインドにしたいという点だ。
いくつか試してみたが今一番上手く言っている気がするのは `Ctrl + j` でひらがなモード、`Ctrl + ;` で半角英数モード、とすることだ。
これが指の位置的には最小の動きで済むというのと、意外に他のキーバインドと干渉しない点が気に入っている。
[^1]: 変換の精度も問題だが、変換候補の文節の切り方が異常で、どう考えてそうは切らないだろうというところで切られた単位で変換候補が表示されるのが辛いところ。
## <2023-01-03 Tue 19:49> ABC 274 E の TLE
独力で解けなかったので 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` で文字れ配列に分割した方が、データロードには多少時間がかかるが、アクセスは高速になるようだ。
ということで、今後はグリッド問題が出た時は二次元文字配列で処理するようにしてみる。
Go to top