ABC317_C "Remembering the Days"をrubyで通した方の解答について
ふざけたchrome拡張作って精進サボってたらレート冷えました。何やってんだ。
今回はこちらの記事へのエアリプです。
記事内にある問題とACコード
melo25さんは何をやっているのか
- 1から2行目で入力を受け取っています。
- 3から7行目で隣接行列を作成しています。
- 9行目の配列は0からn-1までの連番を作っています。これにpermutation(n)を当てることで、全ての並び順が一回ずつsに代入されます。これが「確認するルート」です。
- 10行目は早期リターン。半分見れば残り半分は逆順になるだけなので不要。
- 12行目でsを0からn-2まで順にiに代入します。
- 13行目は入れ子が深くてちょっと難しいです。まずs[i]が現在どの町にいるか、s[i+1]は次にどの町に行くかです。これを隣接行列で確認し、現在の町と次の町道が繋がっていないかどうかを確認します。
- 道が繋がっていない場合は14行目で計算打ち切り。小ループの計算結果と大ループの暫定最大値を比べ、小ループの値の方が大きい場合は暫定最大値を更新します。また15行目で小ループの値をリセットします。小ループを抜ける訳ではなくそのまま続ける事に注意してください。
- 道が繋がっている場合は17行目で小ループの数値に道の長さを追加します。最後の一回は20行目で大ループの暫定最大値を更新します。
- 最後に22行目で最大値を出力します。
以下はオマケです。
なぜ元記事のdfsコードはTLEしたのか
パッと見ではありますが、元記事の最後にあるコードは公式解説の方針とそう大きな違いはなさそうに見えます。
結論を言うとrubyが遅いからです。動的型付け言語はどうしても静的型付け言語に比べて実行が遅くなるため、c++では通るアルゴリズムでもrubyやpythonでは通らない問題が時々あります。pythonならpypyで提出すれば通ることもあるらしいですが、rubyとcrystalでは記法が違いすぎるため難しいでしょう。
ではrubyのdfsで通すにはどうすればいいのか
高速化を2.5重(?)に掛ける必要があります。
高速化その1;Array#maxをifに書き換え
rubyの配列は高機能である分重く、遅いです。2項目のうちどちらが大きいかに使うのはもったいないです。
こまめに answer = new_answer if answer < new_answerとif文を書きます
高速化その2;キャッシュする
「現在どの街にいるか」「どの街が既に通過不能になっているか」の2点が同じだった場合、「そこから最大でどれだけの距離を歩けるか」は常に同じになります。なので最初の一回だけ計算し、二回目以降はキャッシュを読むだけにすれば計算回数を減らせます。
高速化その2.5;visitedを配列ではなく整数(bit）に
rubyの配列は高機能である分重く、遅いです(二回目)。数値がtrueかfalseかの判定に用いるのはもったいないです。
visitedはintにしてしまいましょう。indexはbit桁数、boolean値は0か1かです。
visitedの整数化が0.5扱いである理由は、「そもそも配列のままだと(なぜか)WAするから」です。rubyのhashは配列をkeyにできるため、理論上はvisitedが配列か整数かは出力に影響しないはずです。しかし内部的にhashが衝突しているのか何なのか、配列のままではWAが出ています。何故でしょう？ 誰か教えてください。
dfsでのACコード
投稿者が疲労困憊したので記事上でコードの説明はしません。
コード内のコメントを読んでください。
最近自力で高diff問題が解けず、初心者へのマサカリ記事が増えてきてしまっている。
Discussion