まえがき この記事は、Competitive Programming Advent Calendar 2017 - Adventar 18日目の記事です。最近は、簡単にやるべきことでも、難しくやってしまうことが多く、それがマラソンマッチでの不振につながってるので、「簡単な解法」をネタに書きます。昔…

AtCoderで初の本格マラソンマッチ。楽しかったです。13位/302。最近のマラソンマッチ不振を考えれば良い結果だったけど、反省点も多かったです…。 （方針の公開がOKになったので、公開します。2ndがあるので、ちょっと迷いましたが、北大日立さんにとって良…

はじめに Topcoderで競技プログラミングをする場合、以下の２つの方法があります。 ウェブ版（ベータ）TopCoder Arena アプリ版 Competition Arena ウェブ版はずっとベータ版で開発終了停止している模様なので、懐かしのアプリ版を立ち上げたいところ（パス…

この記事は競技プログラマー向けです。 はじめに 以前、最小カットを使って「燃やす埋める」問題を解くというスライドを書きました。 最小カットを使って「燃やす埋める問題」を解く from shindannin www.slideshare.netこれに対して、tokoharuさんから、『…

問題と1位の方（chokudaiさん）の解法 TCO2017R1 結果 力学モデル（バネ）で、長さ比に応じて力を加える。その後、貪欲法（一番悪い辺の点を、最も高得点になる場所へ移動）で解を改善。 45位/146位 652,515.28点。30位ぐらいの人ともかなりの点差が開いてい…

マラソンマッチ界隈でよく知られている通称chokudaiサーチ、それと似ていると言われてるビームスタックサーチ(beam-stack search)について、ちょっと調べてみました。論文はこちらです。 R Zhou, EA Hansen (2005) Beam-Stack Search: Integrating Backtrack…