週記(23/01/22週)：久しぶりに東京へ

今週のまとめ

• 半年ぶりに東京へ
• AHC017スタート

AHC頑張ります。

(本文中に286 E, Gの解法を含む話題が出てくるのでご注意ください。)

01/22(Sun)

昨日のABC286「G – Unique Walk」を寝る前に考えていたら方針が浮かんだので朝にupsolve。

連結なグラフと辺集合[math]S[/math]が与えられるので[math]S[/math]の辺をちょうど1度だけ通る歩道が作れるか？という問題。

「1度しか通らない」は「1度通ったら削除する」と思い典型発想の「グラフの辺削除は時間を逆順にする」で考えてみます。

[math]S[/math]の辺を削除した状態から始めて連結成分を頂点とみなすと頂点をつなぐ[math]S[/math]の辺を張った時に一筆書きができるか？という問題になります。これは有名問題で奇数次数の個数が0 or 2個という条件で判定できます。

01/23(Mon)～01/25(Wed)

会社が変わってから初の東京出張。

新橋のSL、お色直し中なんですね。

夜に前の職場の上司と飲んだのですが

「競プロめっちゃやってるけど、新しい会社でちゃんと仕事してるの！？」

と心配されました。大丈夫です、今の会社は残業がほぼないので両立できています。

あとこの本が話題に。

最適輸送の理論とアルゴリズム (機械学習プロフェッショナルシリーズ)

やはり最適化出身の人はみんな気になっているみたいですね。私も積読状態なのでAHCラッシュが終わったら読もうと思います。

01/26(Thr)

先週の週記でABC286「E – Souvenir」は価値最大の経路をdfsで求めたと書いたのですがTLEする解法でした。

[math]\sqrt{N}[/math]個のノードを[math]\sqrt{N}[/math]段並べたグラフを考えると1回のクエリで[math]O(N\sqrt{N})[/math]かかる可能性があり最大ケースだとTLEします^[1]ノード間の最大価値をメモ化しておけば大丈夫です。。

01/27(Fri)

ABC286「F – Guess The Number 2」の反省でインタラクティブ問題で

• ローカル実行時にはジャッジをシミュレート
• ジャッジ側での実行時は標準入出力でやりとり

のひな形を書いてスニペット化しました。

ジャッジ側の処理も書かないといけずちょっと面倒ですが転ばぬ先の杖として用意しておきます。

さて明日からAHC017ですね。なんとAHC018も生えてて

• AHC017: 1/28～2/5
• AHC018: 2/18～2/26

それぞれ土曜昼開始の日曜夜終わりなので2/11-12以外の土日は埋まった形ですね。うーん、これは思ってもいないスケジュール。

あと注文したPCはAHC017にはやはり間に合わないことが確定。もっと早く注文しておけば…ですが、AHC018用の秘密兵器にとっておきます。

01/28(Sat)

昼からAHC017スタート！頑張ります。

関連記事

• 前週の週記: 「PCを注文するも…」
• 翌週の週記: 「THIRDプログラミングコンテスト2022(AHC017)日記編」