2017-01-01から1年間の記事一覧

マラソンマッチの簡単な解法

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

Hokkaido Univ.& Hitachi 1st New-concept Computing Contest 2017の反省

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

Topcoder Arenaを起動する方法とJavaブロックの回避

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

最小カットを使って「燃やす埋める」問題を解くスライドのフォロー

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

TCO17 Marathon Round 1 (GraphDrawing) の反省

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

ビームスタックサーチについての勉強メモ

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