週記(23/02/12週)：PC新調

今週のまとめ

• ABC289バチャ。出てたら冷えてた
• AHC018に向けてPCを新しくした
• 東京行った

です。

(本文中にABC046 D, 289 B, E, F, 060 Dの解法を含む話題が出てくるのでご注意ください。)

2/12(Sun)

水Diffの練習でABC046「D – AtCoDeer and Rock-Paper」を解きました。DPで考えたものの[math]O(N^2)[/math]から改善せず。サンプルで実験するとグー、パーを交互に出すのが最適そうで厳密な証明してないものの間違いなさそう…ということで実装して無事AC。

解説を見ると

• すべてグーを出した状態を考える
• グーをパーに変えると相手の手に関係なく得点が+1になる
• パーを貪欲に増やすのが最適

となってて確かに極端な状態を考えてそこから変えたときにどうなる？と考察して性質を導くのは考察の典型ともいえますね。

届いたPCをようやくセットアップ。ここにきて

• ディスプレイ出力: HDMI x 1, Display port x 1
• ディスプレイ: HDMI or DVI-D or D-sub

しかないことに気づきます。なんとシングルディスプレイしかできない…。変換ケーブルを注文しつつ1画面でセットアップ。

WSLを使おうとしたら「エラー：0x80370102」が出て進めず。CPUの仮想化機能がオフだと出るエラーらしくBIOSを確認するもすでに有効。結局、Windows側で「仮想マシンプラットフォーム」がオフになっていたのが原因でした。

VSCodeの設定やフォーマッタ、スニペット、ojツールを入れて移行作業はできたはず。ディスプレイケーブルが届いたらABCのバーチャル参加をして動作確認してみます。

2/13(Mon)

ABC289のバーチャル参加

5完3ペナでパフォーマンス1334相当。出てたら冷えてましたね…。

「B – レ」は「ん？」という問題。UnionFindで連結成分を作って降順にしましたが時間をつかっちゃいました。

「E – Swap Places」は高橋くん、青木くんが今いる位置さえ管理すればよいとわかっていながら「高橋くんの位置とその時、青木くんのありうる位置集合」という筋悪な状態を持ってしまってTLE。

Fに行ってちょっと考え、Eに戻ってちょっと修正してTLEを繰り返す…という良くない動きをしてしまいました。

50分位うだうだやってようやく「高橋くんの位置と青木くんの位置」を持てばOKと気づいて実装。Eまでの速解き勝負だったのでパフォーマンスは仕方ないです。

2/14(Tue)

ABC289「F – Teleporter Takahashi」は2時間くらいかかってようやく通りました。

まず1次元で考えます。

• 点[math]x[/math]を点[math]a[/math]に関して対称に移すと[math]2a-x[/math]になる
• 点[math]x[/math]を区間[math][a, b][/math]に関して対称に移すと[math][2a-x, 2b-x][/math]になる
• 区間[math][x, y][/math]を区間[math][a, b][/math]に関して対称に移すと[math][2a-y, 2b-x][/math]になる

が分かります。

次に操作を[math]2k[/math]回すると移せる区間が[math][-2k(b-a)+s_x, 2k(b-a)+s_x][/math]と線形に広がっていくので[math]t_x[/math]を含むまでシミュレートして、見つかったら逆順にシミュレートしていくと操作手順が求まります。

最初、幅が指数的に広がると勘違いしていたのと[math]a=b[/math]のケースで振動するのを見落としていて時間がかかってしまいました。

解説を見ると[math]x[/math]から[math]x\pm 2[/math]に移す手順を作れるのでそれを続けることで解が構成できたのですね。なるほどー。単位元を作る手順を見つけてそれを組み合わせて解を構成するのも典型発想な気がします。

2/15(Wed)

今日は会社の新卒学生向けイベントに登壇。データサイエンティストが働く環境として

• そもそもデータがとられている＆使いやすいように整備されている
• 反復性、再現性のあるビジネスをしていてビジネス規模が大きい
• ロールモデルがいる

が大切だと思ってて、今の会社はその条件が揃ってて良いよー的な話しました。

ABC060の「D – Simple Knapsack」を解きました。[math]w_1\leq w_i \leq w_1+3[/math]という制約を[math]w_{i-1}\leq w_i \leq w_{i-1}+3[/math]と読み違えてて変に難しくDPで解いてました。

解説見ると重さが4通りしかないので重さごとに何個使うかを決めると同じ重さのものからは価値が高い順に貪欲にとればOKで確かに…という感じ。

AHC018が土曜から始まるのでその環境構築。AHC017のソースを持ってきてmake / runはすんなり。シングルスレッド性能で以前使っていたマシン(Core i7 8700)と比べて1.6～1.7倍の性能がでてますね。素晴らしい。

並列実行用のdocker imageも持ってきて実行するとエラー。理由はOSが

• コンテナ側: Ubuntu 20.04
• ホスト側: Ubuntu 22.04 on WSL

になっているのが原因っぽい。コンテナ側を22.04に上げたら今度はコンテナ側のJupyter notebookに接続できない…。うーん。明日から東京に行くのでタイムアップでホスト側は20.04 on WSLを別途立てることにします。

2/16(Thr)

AHC017のプログラムで並列実行の性能テスト。

2000問を並列度4-32で実行したときの実行時間です。物理16コアなので並列度16まではリニアに伸びてそこから先はかなりサチる感じです。32並列で16並列の25%UPくらい。

2/17(Fri)

東京に行ってました。Thunderさん本の出版イベントがあって興味がありましたが時間的に都合がつかず。

ゲームで学ぶ探索アルゴリズム実践入門～木探索とメタヒューリスティクス

ヒューリスティックコン向けの書籍ってあまりなかった^[1]鉄則本で1章分割かれているくらい？と思いますがこれはバイブルになる気がしてます。

夜に大学時代の同期とちょっと遅めの新年会。日付変わるくらいまで話してました。大学時代はよく彼の家に入り浸って飲みながらゲームしたりプログラム書いたりしていたのが懐かしいです^[2]大学の授業が仕事に変わったくらいで飲むかプログラム書くかってのは変わっていない気もします。。

2/17(Sat)

東京から移動中にAHC018スタート。うん、今回も面白そう。AHC018は来週分にまとめて書きます。

関連記事

• 前週の週記: 「ヒューリスティック青コーダへ！」
• 翌週の週記: 「RECRUIT 日本橋ハーフマラソン 2023冬(AHC018)日記編」