TopCoder の Marathon Match に最近ハマっています.皆んなやろう.練習問題のようなものを作ってみました.マラソン形式のコンテストに興味があるけど,何から始めたら良いか分からない方のお役に立てれば幸いです.「最適化」だったり「NP困難」で検索してヒットする有名な問題を Marathon Match 風テスタにしているだけです,理論的な事は全く分かりません.何か間違っていれば指摘していただけるとありがたいです.また,ゲーム AI の様な問題も特に案が無いためここにはありません.
テスタは Marathon Match 風にしています.使い方は本家と同じなので診断人さん - @nico_shindanninのブログが参考になります.ついでにアカウントを作ってコンテストに出てみましょう.
git clone --depth 1 https://github.com/kosakkun/Typical-MM.git
macOS,Linux(Ubuntu) で JRE,JDK,ソルバ用の開発・実行環境があれば動くことを確認しています.これ以外の OS は分からないのですみません.テスタは一応コンパイルしたものを問題毎に用意しましたが,古い Java の環境だと多分動かないので皆さんの環境でコンパイルし直してください.
各問題は以下の様なファイル構成になっています.tester の下にはテスタ本体の Tester.java と,私の手元の環境でコンパイルして jar にした Tester.jar があります.実行出来ない場合はmake clean && make
でコンパイルできるのでそれでもう一度実行できるか確認してください.それでもダメなら連絡してください.sample の下には,C++,Java,Python のサンプルプログラムがあります.C++,Javaはmake && make run
,Pythonはsh run.sh
で実行出来ます.これも私の手元では動くことを確認していますが,無理ならすみません.
.
├── README.md
├── image
│ ├── 1.png
│ └── ...
├── tester
│ ├── Makefile
│ ├── Tester.jar
│ ├── Tester.java
│ └── tester.mf
└── sample
├── cpp
│ ├── Makefile
│ └── TravelingSalesman.cpp
├── java
│ ├── Makefile
│ └── TravelingSalesman.java
└── python
├── TravelingSalesman.py
└── run.sh
配送計画を考える問題です.巡回セールスマン問題と少し似ています.
一部過去問は Practice Contests から提出が可能です.その他の問題もテスタや問題文は今でも読めるのでトライしてみてください.
まだマラソン形式のコンテストはレートが付いていませんが,@chokudai さんが気まぐれで開催したり,企業コンが行われたり最近増えてきています.AtCoder Problems から探せますが,一応下に列挙しておきます.
- Chokudai Contest
- RCO日本橋ハーフマラソン
- HACK TO THE FUTURE