AtCoder Heuristic Contest 005 参加記

AtCoder Heuristic Contest 005に参加し、16.3Mで143位でした。

atcoder.jp

解法

本番では一番近くのまだ到達していない「通り」に進むだけの貪欲しかできなかったため上記の点数でした。
やりたかった解法は以下のとおり。

問題の解釈

問題を良く読むと、縦か横のひと繋がりの道を「通り」としたとき、
「全ての道路を見渡す」は「全ての通りに最低1回は到達する」と同値であることがわかる。
また、それぞれの通りには必ず交差点で到達するので、経路を考えるときには交差点のみを考えれば良い。

つまり、「どの順番で通りを巡回するか、それぞれの通りにおいてどの交差点を経由するか」を定める問題と解釈しなおすことができる。

解法

前者の「どの順番で通りを巡回するか」は巡回セールスマン問題の2-optのような解法で焼きなましていけば良さそう。
後者の「それぞれの通りにおいてどの交差点を経由するか」は真面目にはさまざまな解法がありそうだが、シンプルにはスタートから 順に交差点を定めていき、前の交差点から最も近い交差点を選んでいけば良い。

交差点間の距離

上記の解法で経路の長さを求めるには各交差点間の距離が必要になる。
テストデータの交差点数は最大で1000個くらいあるように思えた(もうちょっと少ないかもしれない)
ここで、ワーシャルフロイド法を使うとO(交差点数の3乗)のため交差点数=1000だと間に合わない。
しかし、各点を始点とするダイクストラ法を行えば良い。ダイクストラ1回の計算量は O((辺の数+交差点数) log 交差点数)であり、辺の数<交差点数 x 4 なので十分間に合う。
本番ではここが思いつかず、どうにもそこから先に進めなかった。

スコア

前処理で交差点間の距離の計算を行っておけば、2-optで差分計算をせずに素朴に計算しても3秒で150万回くらいは試行できた。温度を適当に調整すると20.8M, optunaでもうちょっと調整すると21.5Mで、15-20位前後のスコアになった。 https://atcoder.jp/contests/ahc005/submissions/24899313

Togetterをスクレイピングしてヒューリスティックコン解法を集める

agwさんがヒューリスティックコンがあるときにだいたいTogetterまとめを作って下さっていて、それが情報収集にとても有り難いです。 自分の気になったツイートだけ抽出したくなったのでツールを作ってみました。

スクレイピング

github.com

  • 「残りを読む」ボタンを押す必要があるのがなかなか難しい。seleniumを使うことで対処。

できあがり

取得したhtmlをタブ区切りテキストに変換し、google spreadsheetに貼り付けたあと、目視で気になるツイートのみ抽出。 Togetterの機能でURLのリストからまとめを作成。

togetter.com

togetter.com

AtCoder Heuristic Contest 003 参加記

AtCoder Heuristic Contest 003に結構時間を溶かして参加し、96.7Bで暫定29位でした。
https://atcoder.jp/contests/ahc003

解法

  • ベースはRidge回帰+ダイクストラで最短路を選択
    • M=2を意識して行/列ごとに2個パラメータを持たせるようにした
  • 最初の90ターンは探索、「いい感じ」に未探索のパスを選択
    • 「いい感じ」のパスが見つからない場合は最短路を選択
  • その後は最短路を選択しつづける
    • あまり探索していない行/列は長さがちょっと短いように補正する

感想

早めに回帰の解法を思いつけて、土日に94Bまでには比較的良いペースで辿りつけた。 いろいろ分析を重ねたものの、上位との3Bの差を埋められるような大きさの知見が得られずにずっと苦しんでいた。 回帰に正則化を入れて更新頻度も多くしたところ96Bまで一気に上がり、そこから細かい工夫とパラメータチューニングで96.7B。

GCPのCloud RunでOptunaで自動パラメータチューニングする仕組みを立てていて、これはかなり便利。 20ケース x 100試行が1-2分で帰ってくるので、ちょっと迷ったときにパラメータ化して良さげなところに設定することができる。

プログラムはC#だけど、分析には結構Pythonを使っていて、地味にPythonのタスクランナーであるpython-invokeも便利でした。設定次第でカレントディレクトリに依存せずにいろんな処理をできるので、ターミナルがぐちゃぐちゃにならずにすむ。

フロントエンド何もわからない(その6)〜 Introduction To Heuristic Contestのビジュアライザを作った

threecourse.hatenablog.com のつづきです。

今回の成果物はAtCoderIntroduction to Heuristics Contest のビジュアライズで、人間では到底良さげな解に到達できないところ、最適化だと1秒程度で綺麗な解を出してくれるのが見てて面白い。

visualizer.threecourse.net

f:id:threecourse:20210511005851p:plain

Reactによるフロントエンドの構築

  • React + Reduxによる構成
  • ReduxのStateの中に情報を全部詰め込むようにするのが一番分かりやすかった。useDispatchを使うとどこからでも処理を走らせられ、useSelectorを使うとどこからでも情報を取得できる
  • 今回は26x365で10000個近い要素を扱うので、何も考えなしに扱うと再レンダリングが走って更新がかなり遅くなってしまうという難しさがあった
  • 10000個の配列を毎回生成する程度のコストは問題ではなく、それらのコンポーネントを再レンダリングしようとするのが速度低下の原因
  • react.Memo/useMemoを使うことで不要なコンポーネントの再レンダリングを抑えるとともに、各セルのコンポーネントからuseSelectorで値を取得させるようにした。useSelectorで取得した値が変わらない場合には再レンダリングが走らないため、十分な速度で動く

.NET Core(C#)によるバックエンドの構築

  • 最適化プログラムはC#で記述する(.NET Coreを利用)
  • PythonのflaskからC#のプログラムを呼び出すようにして、REST API サーバ化しておく

ローカルでのフロントエンド・バックエンド環境の構築

  • フロントエンドからバックエンドのAPIを叩くことで計算結果を取得して表示する
  • フロントエンドとバックエンドを分けると、バックエンドをC#などの好きな言語で書ける
  • Docker化して、docker-composeで立ち上げるようにすればわりと楽にサーバを同時に立てられる

GCPのCloud Runでのフロントエンド・バックエンド環境の構築

  • Cloud Runは、サーバとしてDockerイメージをデプロイすると、自動的によしなにしてくれるサービス。
  • フロントエンド、バックエンドをそれぞれCloud Runのサービスとして公開
    • フロントエンドはReactをビルドすると静的ファイルになるので、http-serverで起動させた
    • バックエンドは非公開としてフロントエンドからのみ呼び出せるようにしたかったが、Reactから呼び出すことが上手く行かなかったので公開するようにした。
    • この辺はもっとうまいやり方がありそう
  • Cloud Runは、CPU/メモリは格安なのだが、以前ログ課金で死にかけたことがあるので恐る恐るやっている
  • 良い機会なのでドメイン取ってみた
  • .Net CoreはReadyToRun コンパイルをすることで起動が高速になった。そうしないと、Cloud Run環境では遅いかもしれない https://docs.microsoft.com/ja-jp/dotnet/core/deploying/ready-to-run

マラソンマッチのビジュアライザいろいろ

ラソンマッチのビジュアライザについて、各者/各社さまざまな作り方をしているので、まとめてみました。

longcontest-visualizer-framework

kimiyukiさんのlongcontest-visualizer-frameworkおよびRCO/リクルート日本橋ハーフマラソンで使われている方法
(お互いに参考にしながら開発している?)

github.com

github.com

  • 時系列ごとに行動を出力する形式の問題では、時系列に沿った状況の推移が見たい。そのため、UIで時系列に沿って再生・巻戻し・早送りする機能がある
  • 入力・出力から毎フレームの情報を計算したのち、各フレームの情報をhtmlのCanvas 2Dに描画する
  • Canvasを画像に変換したり、動画に変換する機能もある(https://github.com/jnordberg/gif.js を使っている)

画像出力からの動画変換

https://github.com/kmyk/atcoder-heuristic-contest-002/blob/master/scripts/visualize.py

以下のようにして、AtCoder Heuristic Contest002の焼きなましの解の改善の様子を動画で出力している

  • ----BEGIN----と----END----と囲まれた範囲はビジュアライザ用出力とする。解法プログラム内で一定間隔ごとにビジュアライザ用出力を行うようにしておく。
  • 各ビジュアライザ用出力ごとに公式ビジュアライザを呼び出して画像を出力する
  • 出力された画像をffmpegで動画に変換する

画像を出すだけなら、いろんなアプローチがある(Pythonのmatplotlib, RustのSVGクレートなど)。とりあえず画像を出力してffmpegで動画変換というのは汎用的なアプローチかもしれない。

gvc/General Visualizer Client

colunさんのマラソンマッチ用ビジュアライザのプロトコル/ライブラリ

https://github.com/colun/gvc

www.youtube.com

解法プログラム内でプロトコルに沿った形式で命令を出力し、それを読み込んでJavaプログラムで表示する

siv3d

「ゲームとメディアアートのための C++ ライブラリ」であるsiv3dを用いて表示する

siv3d.github.io

Unity

天下一 Game Battle Contest 2021 Spring で使われた方法

tenka1.klab.jp

https://github.com/KLab/tenka1-2021-spring

UnityのWebGLビルドを使っている。魅せる目的では有効そう。ビジュアライザで求められる要件とゲームエンジンの相性は良いように思えるが、さすがにヘビーな気はする

React

最近私が研究しているアプローチ

ナーススケジューリング問題を焼きなまし法により解く
https://threecourse.github.io/nurse-scheduling-simulated-annealing/

  • Reactは開発が積極的に進められているGUIであり、情報が手に入りやすい
  • 問題の入力の作成もGUIでやって、それをバックエンドの解法プログラムに投げたり、作り込めばかなり柔軟性が高い
  • 1万個以上の要素を表示しなくてはいけないことがある。このとき、何も考えないとそれらのレンダー処理で表示のパフォーマンスが悲惨なことになる。ReduxやuseSelectorフックを上手く使い変化する要素のみ再レンダーするようにすると、問題なく表示できる。

ソフトウェアのアーキテクチャについて(その3)~ 良書とクリーンアーキテクチャ

以下の記事の続きです。 threecourse.hatenablog.com

ドメイン駆動設計についての書籍

ドメイン駆動設計周りを学ぶには、以下の2冊が良さそう。

有名な実践ドメイン駆動設計(www.amazon.co.jp/dp/B00UX9VJGW)を最初に読むと、主張が分かりづらかったり、概念の定義がはっきりとなされていないように思います。上記の書籍は、定義をできる限り明確に説明していたり、具体例で表現しているため比較的分かりやすいです。

クリーンアーキテクチャ

f:id:threecourse:20210501210013p:plain

クリーンアーキテクチャという良さげな設計があるらしく、上の図で表されます。
こちらもClean Architecture 達人に学ぶソフトウェアの構造と設計(www.amazon.co.jp/dp/B07FSBHS2V) を読んでも良くわからない部分があり、「ドメイン駆動設計入門」の著者のQiitaおよびGithubが参考になりました。

以下は私の理解です:

  • 具体的なクラスでなく、インターフェイスに依存することによって、柔軟性やテスト容易性を増す
  • 双方向に具体的なクラスに依存させると密結合になってしまう。だからといって双方向で抽象に依存させられるかというとそうではない。例えば、ユーザー作成処理をユーザーという具体的な概念なしに定義するのはむしろ不自然。
  • よって、具体的なクラスへの依存は片方向とし、逆はインターフェースへの依存としたい。Entities ← UseCases ← Controllers/Gateways/Presenters という方向への具体的なクラスへの依存は許容するが、逆方向は許容しない。
    つまり、UseCasesはEntitiesを利用できるし、ControllersはUseCasesを利用できるが、EntitiesはUseCasesをインターフェースを通してのみ参照でき、UseCasesはControllersをインターフェースを通してのみ参照できる

  • 処理は、インターフェイスで定義されるUseCaseとその実装であるInteractorで定義される

    • UseCaseのインターフェイスは、void Handle(UserCreateInputData inputData)のように入力を処理するだけである 
    • Interactorの実装は、IUserRepository, IUserCreatePresenterといったフィールドを持ち、入力を処理するときにレポジトリと連携してユーザ作成処理を行い、その結果を適切に表示させる、ということができる
    • UseCase/Interactorの入力、出力にはDTO (Data Transfer Object) として必要な値をまとめたオブジェクトを定義する
  • インターフェイスには、最終的に具体的なクラスを設定する必要がある(=依存オブジェクトを注入する必要がある)。各クラスのコンストラクタでいちいちセットする方法もあるが、この処理を行うためのDIコンテナと言われるライブラリがある。

ADOP

クリーンアーキテクチャを読んでいて、Entities, UseCasesとそれ以外を明確に分離することは有益であるが、小さなプロジェクトの初期段階から各インターフェイス・オブジェクトを作っていくのは非効率で煩雑ではないのかな。。
と思っていたら、上記の著者の方がADOPという実装パターンを考案されていて、納得感がありました。

https://nrslib.com/adop/

f:id:threecourse:20210501210236p:plain

私の理解では、以下のとおりです。

  • ドメインレイヤー(Domain Layer)、アプリケーションレイヤー(Application Layer )、アザーズレイヤー(Others Layer)に分ける。
  • Domain Layerには、ソフトウェアを適用しようとする対象領域(ドメイン)の事物を直接的に表現するコード、もしくは表現を支援するコードを記述する
  • Application Layerには、ドメインの事物を表現するコードを取り扱い、ソフトウェアで成し遂げたいユースケースを達成するコードを記述する
  • Others Layerには、アプリケーションレイヤーとドメインレイヤー以外のもの、例えばユーザーインターフェイスやデータベースに関するコードなどを記述する
  • Domain LayerのオブジェクトがApplication Layerに利用される、Domain Layer, Application LayerのオブジェクトがOthers Layerに利用されるのは問題ない。逆の場合は具体的なクラスを使用してはダメで、インターフェイスなどを通して汎化して利用する。

AtCoder Heuristic Contest 002 参加記

atcoder.jp

スコア4.32M 107位 パフォ2117でした。

解法

  • mmlang (https://github.com/colun/mmlang) を使ってビームサーチ
  • 点数は見ない
  • 36分割して一筆書きのルートを設定し、できるだけ進みが遅い方を加点、ルートからはみ出たら減点
  • 評価がタイのものは乱数を入れてランダムに評価

dfsの方が良かった説とか、焼きなましをしないと最上位は厳しいという話はありますが、ビームサーチにベットする戦略をとったのである程度しょうがないですね。

mmlang

github.com

mmlangを改造して以下のような機能を追加して使いました。結局使ったのは標準エラー出力機能のみでしたが。

  • パラメータを引数で読み込む機能
  • 標準エラー出力に出力する機能
  • ファイルに出力する機能
  • ファイルに結果をJSONで出力する機能

mmlang無しにはこのスコアは出せていないと思うので神です。 一方で、入力をバグらせて最初の1時間溶かしたので、もう少し慣れたり、デバッグ用機能を拡充したほうが良さそうですね。

Cloud Run

Cloud Runに投げて並列でパラメータチューニングを試みましたが、

  • そもそも変えるパラメータが無かった
  • 結果が安定しない、確率的にエラーが発生するなどの複数の問題が発生した

という点で、結局使用することは無く。