Hatena::Grouptopcoder

yowa の TopCoder 日記

TopCoder yowa / twitter: @yowa

2016-08-19

ICFPC 2016 参戦記

10:02 | ICFPC 2016 参戦記 - yowa の TopCoder 日記 を含むブックマーク はてなブックマーク - ICFPC 2016 参戦記 - yowa の TopCoder 日記

毎年恒例3日間のお祭り、ICFPC <http://icfpc2016.blogspot.jp/> に参加した。

他のチームの方々の参加記(気づいた分)

ざっくりまとめ

  • チーム yowa として1人で参加した。
  • 折り紙を折る問題だった。
  • 出来上がりが凸多角形になるものだけ解くソルバを書いて、あとは個別対応した
  • 出題はサイズ600くらいの、凸多角形ではないけどシンプルな同じパターンの問題を出した。
  • 途中の順位は最高で2位(開始37時間後(ほぼ真ん中))、順位表フリーズの時点(終了3時間前)で10位だった。

  • 順位表的には過去最高に健闘できたと思う

問題

問題文はこちら: <http://icfpc2016.blogspot.jp/2016/08/task-description.html>

各テストケースは、

  • 入力として、折り紙の完成形の外枠の形(silhouette)と、折り目や紙の端がどこを通るか(skeleton)が与えられる
  • 出力は、元の正方形の折り紙上の点(source)が完成形のどこに対応するか(destination)、各部分はどんな形に折られるか(facets)を答える

というもので、スコアは

  • 運営サイドや他の参加者が作ったテストケースを解く(完全一致で高得点、完全一致した参加者が少ないほど高得点、問題サイズが大きいほど高得点)
  • 自分が作ったテストケースを他の参加者にむけて出題する(完全一致した参加者が少ないほど高得点、問題サイズが小さいほど高得点)

のようにして決まる。

やったこと

問題を見たら、座標は有理数で表されていて、分母分子が数百桁になるようなケースもあるようだったので、有理数が手軽に使える言語として Ruby を使うことにした(自分が使える言語が RubyC++ の二択だった)。

正直、普通に手でやる折り紙(この点をあの点に合うように谷折りして、こっちの線とあっちの線が合うように山折りして……)と、解答形式である facets の概念がぜんぜん頭の中で一致せず、なにやっていいのかわかんないまま十時間とか経過した。

わかんないにしてもとりあえず手でやる折り紙シミュレータを書くしかないだろうと重い腰を上げ、紙の移動・回転・頂点が特定の位置に行くように折る・頂点を特定の線で折る、の機能を実装した。

(「skeleton で定義される多角形を開いていき初形の正方形に戻す」が正攻法なんだろうなあと思いつつも)完成形が同じであれば、実際の折り手順がどうであろうと正解と判定されるので、 skeleton は完全無視することにした。

完成形が凸多角形であるような問題は、

  • 完成形がスッポリ含まれるような位置に初形の正方形を配置して、
  • 完成形からはみ出してる部分があったら内側に折り込む
  • はみ出しがなくなるまで繰り返し

という greedy な手順で完全一致解ができあがるよなーと思ってそれ実装。

凸多角形でない問題については、完成形の凸包を作ってそれに向かって上記手順を行うことにした。完全一致でない解でも一応スコアがもらえるので submit しなければ損だけど、まあ投げないよりはマシ程度のスコアしかもらえないのであんまり意味は無い。

出題は、

  • 凸多角形だとあっさり解かれる
  • (解かれにくさが同じなら)サイズが小さいほど有利なので、小さめの問題
  • 自分のシミュレータは折り紙の開く操作(折り鶴の3手目の三角形を四角形にする、みたいなやつ)を表現できてないので、そんな問題は考えない

みたいなことを考えつつ、結局一つの角を起点に上下に折り返すだけというやる気の感じられないものが出来上がった

http://i.imgur.com/8MXzT84.png

汎用ソルバを作るのは最初から諦め、あとは問題を目視して個別対応→他の問題にも適応できるか走らせる、という感じ。

  • 初形を平行移動・回転させたあと、1回だけ折って到達できないか?
  • 特定の形に特化したソルバ。下のようなL字型なら「『頂点0,1,3,4が直角で、辺1-5と辺5-4を足したら長さ1で、0-6と6-3を足したら1で、0-1の長さが1/k』という条件にマッチするなら、初形から1/kに細長く折ったあと1回折ってL字型にする」みたいにベタに書き下した。とは言っても他にやったのは最後にもう一回折るC字型、S字型くらい。
  • 手動で解く。手動で解くツールは作れてないので、「頂点 3 を座標(1/2,1/2)に重なるように折る」みたいなのをいちいちコードで書いた。

思ったこと

途中の時点で高順位だったのは、その時点で自分が出題した問題が解かれていなかったから。上記の通りの生成法なので

  • 初形の4頂点のうち2~3箇所は直角のまま残る
  • 左上から残りの3頂点までの距離は初形のときのまま

のような、いかにも解く手がかりになりそうな情報が残ってる感じだったので、汎用ソルバを作ってるチームにはさっくり解かれるだろうなあと思っていただけに、(潜伏していたUnagiチームはさておき)そんなに未回答のまま残るとは想定してなかった。順位表フリーズの時点でも3~4チームしか解いてない模様。

汎用ソルバは最初から諦めていたので全然考察してなかったけど、他のチームの参加記を見た感じ、ちょっとやそっとのやり方ではあっという間に組み合わせが爆発してしまうようだ。

以上より、運営サイドが想定してたより難しい Task だったんじゃないかなあ、と感じた。(あるいは Unagiチームを想定して出題された?)

開始前に公式アカウントのTweet でショートコーディングっぽいのがあったので、タスクにショートコーディング要素があるのかなあ、と思ったら、そこまででもなかった。個人的に好きなICFPCの問題のタイプは「毛色の異なる複数のサブ問題が組み合わさっていて、それぞれのサブ問題をてきとーに解いてもそれなりスコアは得られて、どのサブ問題についても注力して解けばスコアアップにつながる」みたいな感じなので、解答側にもショートコーディングするような要素があればもっと楽しかったかもなあと思った。

テストケースの取得や解答のsubmitなどを行う API が用意されていたので自動化が楽でよかった(自動化できたとは言ってない)。ただ「自分がこれまでに投げた解答の一覧や、一致率の一覧を得る」みたいな API は用意されておらず、ローカルで一致率を計算できてない(完全一致したかすら判定できてない)上に submit 時の応答のログを取るのをサボっていたので困った。

2015-01-13

SEAND2 (January Challenge 2015)

| 13:51 |  SEAND2 (January Challenge 2015) - yowa の TopCoder 日記 を含むブックマーク はてなブックマーク -  SEAND2 (January Challenge 2015) - yowa の TopCoder 日記

マラソン問題。

問題

巨大な整数 A (~1000桁、十進表記で各桁は0でない)と、100個の整数B[i](~10^6)が与えられる。A の数字を並べ替えたものを A' としたとき、

score(A') = Σ(A mod B[i])

ができるだけ小さくなるよう、A' を求めよ。

やったこと

何か整数の性質を利用した賢い方法があるのかなーとか思いつつ、わからないので、ランダムに数撃ちゃ当たる作戦を取った。

スコア計算

A は文字列のまま持っておく。各桁の数字を操作したいので多倍長整数よりもそのままの方がいいんじゃないかな。多倍長を用意するのがめんどかったわけじゃないよ。

スコア計算をベタにやると、1000桁 x 100個分の mod(除算)をやることになって遅いので、

  • 初期解のスコアを(ベタに)求める
  • 前の解の2つの数字を入れ替えて差分だけ求める

という方針にした。

予め 1, 10, 100, ..., 10^1000, の mod B[i] を計算しておく。A mod B[i] が既知のとき、n 桁目と m 桁目を入れ替えたものを A' とするとそのスコアは、(A の n, m桁目の数字をそれぞれ D[n], D[m] とすると)

 A' mod B[i] = ((A mod B[i]) - D[n] * 10^n + D[m] * 10^n - D[m] * 10^m + D[n] * 10^m) mod B[i]
             = ((A mod B[i]) + (D[n] - D[m])*(10^m - 10^n)) mod B[i]

なので、除算1回 x 100個分の mod でスコアが計算できる。

探索方針

「既知の解をちょっと変更してスコア計算」という流れなので、山登りや焼なまし的な問題設定なんだけど、なんせ変更前後でスコアが違いすぎる(abs(10^m - 10^n) が B[i]よりすんごく大きい)ので、近傍を探索してるというよりはランダムサンプリングしてる感じなのだった。

ただ abs(10^m - 10^n) が min(B[i]) より小さい場合、ようは下の方のケタ同士の入れ替えの場合は、入れ替え前後でスコアが近い可能性がそれなりにある。たとえば末尾2桁を入れ替えて A = xxxxxx21 を A' = xxxxxx12 にしたら、高い確率で A mod B[i] より A' mod B[i] の方が 9 小さい、みたいな。

ということで、処理を2段階に分けて、

  • (第一段階)ランダムな2桁を入れ替えて、第一段階のベストスコアより良かったら第二段階へ。
    • 全体のベストスコアとは別に、第一段階でのベストスコアを記憶しておく
  • (第二段階)末尾6桁の permutation を全探索。

ということをやったのでした。

あとで思ったこと

第一段階で選抜するのは、「スコアのいいもの」より「値が揃ってる(max(A' mod B[i]) - min(A' mod B[i]) が小さい)もの」の方が、第二段階でごっそり減らせるチャンスが大きかったのかなあ、みたいな。

2014-12-07

マラソンマッチで1位になる方法(最終順位とは言ってない)

00:04 | マラソンマッチで1位になる方法(最終順位とは言ってない) - yowa の TopCoder 日記 を含むブックマーク はてなブックマーク - マラソンマッチで1位になる方法(最終順位とは言ってない) - yowa の TopCoder 日記

この記事は Competitive Programming Advent Calendar 2014(マラソン系) の 7日目です。

おことわり

この文章は筆者がいま書きながら思いついたことを並べてる部分がほとんどであり、筆者が実践しているわけでも、確かな効果が得られることを保証するものではありません。

本文

競技プログラミングに参加する以上、だれしも「ランキング上位に入りたい」「できれば1位になりたい」と思うものです。思わない人も思うことにしておきましょう。

「とは言っても、上位に入るには相応の実力がなければ……」、そんな風に思ってませんか? でも、ちょっとしたコツで(暫定)1位が取れるんです。

そう、マラソンマッチならね。

目指すもの

1位は1位でも、暫定1位です。しかも最終暫定順位(締め切りの後、システムテストが終わるまで表示されている順位)ではなく、ほんとうに暫定的な順位の話です。

マラソンマッチは期間中、常に(暫定)順位表が公開されています。その順位表で一瞬でも1位になったら、素早く順位表のスクリーンショットを取るなり 「暫定1位だよー」とつぶやくなりして悦に入りましょう。

(SRM と比較した場合の) Marathon Match の特徴

  • 期間が長い(2週間前後)。
  • 解けた/解けなかった、ではなくスコアの良さを競う
  • 同じスコアになっても、「提出が早いほうが勝ち」などということはなく、同着扱い
  • 提出回数によるペナルティも無い*1

以上の特徴をまとめると「急ぐ必要はない」といったところでしょうか。実際に、マラソン上位常連の人たちでも最初のコード提出がマラソン開始の2,3日後というのもよくあります。

取るべき戦略

ここまでくれば簡単ですね。

「開始直後の、まだ参加者が少ないタイミングを狙う」、これです。

以下では具体的な戦略を紹介していきましょう。

戦略1. First Submit ≒ First Accept = 1位/(参加者全1人)

スコアボードの一番上に燦然と輝く自分のID。そしてそこには、自分以外の誰もいない……。美しいですね。

この戦略を取るならば当然、純粋なスピード勝負になります。

マラソンマッチはスコアを競うという性質上、WA という概念はありません。また TLE や MLE などが起きた場合でも「そのテストケースのスコアは 0 点と見做す」という扱いになることがほとんどです。

ですから、コンパイルさえ通ればそのコードは Accept されてスコアボードに乗ると思っていいでしょう。

実践例

Marathon Match 82: ColorLinker を例にとると(C++ の場合)、

  • 問題文をひらく(この時点で、問題文を読む必要はありません)
  • 「signature」でページ内検索する

以下のような部分が見つかります。

Class:  ColorLinker
Method: link
Parameters: vector <string>, int
Returns: vector <int>
Method signature: vector <int> link(vector <string> grid, int penalty)
(be sure your method is public)
  • この仕様に合うコードを書く

仕様に合ってさえすれば、返す値の中身は何でも問題ありません。

#include <vector>
#include <string>
using namespace std;
class ColorLinker {
public:
  vector <int> link(vector <string> grid, int penalty) {
    return vector<int>();
  }
};
  • 提出する
  • いそいで順位表を確認する
  • (たぶん)1位になってる

以上です。

いま挑んでいるのが何をする問題でどんな入出力が行われるのか、それさえも知らないままでのコード提出。そしてそのコードが(運が良ければ)暫定1位。背徳感でゾクゾクしますね。

勝負は試合開始前から始まっている

「運が良ければ」と書いたのには理由があります。

(以前は違ったのですが、)最近のマラソンマッチは、開始する日時が正式に予告されることは少なく、多くの人にとって「気付いたら始まってる」ものなのです。

それは、普通に参加するだけなら大した問題ではないのですが*2、今回の First Submit 戦略を取る上では大問題です。「気付いたらマラソン始まってて、他の人が既に提出してた」は、戦略の失敗を意味するのですから。

そこで、マラソンが始まりそう・始まったことにいち早く気付けるよう、常にアンテナを立てておくことが重要だと言えます。

マラソンマッチ開催を知ることができる主な情報源としては以下があげられます。

  • 開催中のマラソンマッチ一覧のページ: マラソンマッチは(日本時間)午前2時か3時*3に始まることが多いので、そのタイミングでチェックするようにしましょう。
  • マラソンマッチのフォーラム。
  • Upcoming Contests のページに、稀にマラソンの予告が(日時つきで)出ていることがあります。しかし指定された日を過ぎても音沙汰が無かったり、あるいはいつの間にか日付が変わったり、はたまた消滅していたりと、あまり信用できない感じです。
  • マラソン常連の人の TwitterTogetter のマラソンマッチまとめ*4に登場するアカウントをフォローしておけば、誰かが「マラソン始まってる!」とつぶやくのに気付けるかもしれません。ただし、目にしたそのつぶやきは、その人がすでに最初の提出を済ませた後のものだった、というのもよくある話です。

この戦略の欠点

  • 開始に出遅れたら負け
  • 仮に1位を取れても(たいてい)スコアは 0 になるのがカッコ悪い
  • というか明らかに邪道

おわりに

開幕ぶっぱ戦略、いかがでしたか?

この戦略はマラソンだけでなく、SRM にも使えるのではないでしょうか(再提出のペナルティが痛い、1位になったところで中間の順位表に注目してる人はほとんどいない、などのデメリットに目をつぶれば)。

今回紹介できた戦略は1つだけでしたが、機会があれば次なる戦略「スコア満点での暫定1位も夢じゃない? ~ちゃんとした解を提出して正のスコアを取ろう(ただし問題文はやっぱり読まない)~」を紹介できたらと思います。

ありがとうございました。

*1:一度提出したら2時間は再提出できない、みたいな制限はある

*2:それでもちゃんと告知しといて欲しい

*3:アメリカ東海岸時間(EST/EDT)の13:00。サマータイムでズレる

*4:agw さん、毎度のまとめ、お疲れさまです&ありがとう!

2014-08-17

2014 TCO Marathon Round 3 CollageMaker

15:59 | 2014 TCO Marathon Round 3 CollageMaker - yowa の TopCoder 日記 を含むブックマーク はてなブックマーク - 2014 TCO Marathon Round 3 CollageMaker - yowa の TopCoder 日記

TCO マラソンお疲れ様でした。もう1ヶ月以上前だけど。

終わってすぐにスライドを作ってたけど、ここからリンクしていなかったので改めて。

2014-04-24

2014 TCO Marathon Round 1 SquareRemover

03:09 | 2014 TCO Marathon Round 1 SquareRemover - yowa の TopCoder 日記 を含むブックマーク はてなブックマーク - 2014 TCO Marathon Round 1 SquareRemover - yowa の TopCoder 日記

TCO マラソン Round 1、おつかれさまでした。スライドつくった。