折り紙を折る問題だった。出来上がりが凸多角形になるものだけ解くソルバを書いて、あとは個別対応した出題はサイズ600くらいの、凸多角形ではないけどシンプルな同じパターンの問題を出した。途中の順位は最高で2位(開始37時間後(ほぼ真ん中))、順位表フリーズの時点(終了3時間前)で10位だった。入力として、折り紙の完成形の外枠の形(silhouette)と、折り目や紙の端がどこを通るか(skeleton)が与えられる出力は、元の正方形の折り紙上の点(source)が完成形のどこに対応するか(destination)、各部分はどんな形に折られるか(facets)を答えるというもので、スコアは運営サイドや他の参加者が作ったテストケースを解く(完全一致で高得点、完全一致した参加者が少ないほど高得点、問題サイズが大きいほど高得点)自分が作ったテストケースを他の参加者にむけて出題する(完全一致した参加者が少ないほど高得点、問題サイズが小さいほど高得点)のようにして決まる。概念がぜんぜん頭の中で一致せず、なにやっていいのかわかんないまま十時間とか経過した。わかんないにしてもとりあえず手でやる折り紙シミュレータを書くしかないだろうと重い腰を上げ、紙の移動・回転・頂点が特定の位置に行くように折る・頂点を特定の線で折る、の機能を実装した。完全無視することにした。手順で完全一致解ができあがるよなーと思ってそれ実装。凸多角形でない問題については、完成形の凸包を作ってそれに向かって上記手順を行うことにした。しなければ損だけど、まあ投げないよりはマシ程度のスコアしかもらえないのであんまり意味は無い。自分のシミュレータは折り紙の開く操作(折り鶴の3手目の三角形を四角形にする、みたいなやつ)を表現できてないので、そんな問題は考えないみたいなことを考えつつ、結局一つの角を起点に上下に折り返すだけというやる気の感じられないものが出来上がった汎用ソルバを作るのは最初から諦め、あとは問題を目視して個別対応→他の問題にも適応できるか走らせる、という感じ。初形を平行移動・回転させたあと、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字型くらい。座標(1/2,1/2)に重なるように折る」みたいなのをいちいちコードで書いた。思ったこと途中の時点で高順位だったのは、その時点で自分が出題した問題が解かれていなかったから。上記の通りの生成法なので初形の4頂点のうち2~3箇所は直角のまま残る左上から残りの3頂点までの距離は初形のときのままのような、いかにも解く手がかりになりそうな情報が残ってる感じだったので、汎用ソルバを作ってるチームにはさっくり解かれるだろうなあと思っていただけに、(潜伏していたUnagiチームはさておき)そんなに未回答のまま残るとは想定してなかった。順位表フリーズの時点でも3~4チームしか解いてない模様。汎用ソルバは最初から諦めていたので全然考察してなかったけど、他のチームの参加記を見た感じ、ちょっとやそっとのやり方ではあっという間に組み合わせが爆発してしまうようだ。ないかなあ、と感じた。ショートコーディングっぽいのがあったので、タスクにショートコーディング要素があるのかなあ、と思ったら、そこまででもなかった。個人的に好きなICFPCの問題のタイプは「毛色の異なる複数のサブ問題が組み合わさっていて、それぞれのサブ問題をてきとーに解いてもそれなりスコアは得られて、どのサブ問題についても注力して解けばスコアアップにつながる」みたいな感じなので、解答側にもショートコーディングするような要素があればもっと楽しかったかもなあと思った。用意されていたので自動化が楽でよかった(自動化できたとは言ってない)。時の応答のログを取るのをサボっていたので困った。CodeChefマラソン問題。(~1000桁、十進表記で各桁は0でない)と、100個の整数B[i](~10^6)が与えられる。やったこと何か整数の性質を利用した賢い方法があるのかなーとか思いつつ、わからないので、ランダムに数撃ちゃ当たる作戦を取った。文字列のまま持っておく。各桁の数字を操作したいので多倍長整数よりもそのままの方がいいんじゃないかな。多倍長を用意するのがめんどかったわけじゃないよ。初期解のスコアを(ベタに)求める前の解の2つの数字を入れ替えて差分だけ求めるという方針にした。B[i]よりすんごく大きい)ので、近傍を探索してるというよりはランダムサンプリングしてる感じなのだった。小さい場合、ようは下の方のケタ同士の入れ替えの場合は、入れ替え前後でスコアが近い可能性がそれなりにある。いうことで、処理を2段階に分けて、(第一段階)ランダムな2桁を入れ替えて、第一段階のベストスコアより良かったら第二段階へ。いうことをやったのでした。小さい)もの」の方が、第二段階でごっそり減らせるチャンスが大きかったのかなあ、みたいな。おことわりこの文章は筆者がいま書きながら思いついたことを並べてる部分がほとんどであり、筆者が実践しているわけでも、確かな効果が得られることを保証するものではありません。競技プログラミングに参加する以上、だれしも「ランキング上位に入りたい」「できれば1位になりたい」と思うものです。思わない人も思うことにしておきましょう。したコツで(暫定)1位が取れるんです。マラソンマッチならね。目指すもの1位は1位でも、暫定1位です。最終暫定順位(締め切りの後、システムテストが終わるまで表示されている順位)ではなく、ほんとうに暫定的な順位の話です。マラソンマッチは期間中、常に(暫定)順位表が公開されています。「暫定1位だよー」とつぶやくなりして悦に入りましょう。期間が長い(2週間前後)。解けた/解けなかった、ではなくスコアの良さを競う同じスコアになっても、「提出が早いほうが勝ち」などということはなく、同着扱い提出回数によるペナルティも無い*1以上の特徴をまとめると「急ぐ必要はない」といったところでしょうか。実際に、マラソン上位常連の人たちでも最初のコード提出がマラソン開始の2,3日後というのもよくあります。取るべき戦略ここまでくれば簡単ですね。「開始直後の、まだ参加者が少ないタイミングを狙う」、これです。以下では具体的な戦略を紹介していきましょう。1位/(参加者全1人)スコアボードの一番上に燦然と輝く自分のID。そこには、自分以外の誰もいない......。この戦略を取るならば当然、純粋なスピード勝負になります。いう概念はありません。点と見做す」という扱いになることがほとんどです。されてスコアボードに乗ると思っていいでしょう。問題文をひらく(この時点で、問題文を読む必要はありません)「signature」でページ内検索する以下のような部分が見つかります。public)この仕様に合うコードを書く仕様に合ってさえすれば、返す値の中身は何でも問題ありません。}};提出するいそいで順位表を確認する(たぶん)1位になってる以上です。いま挑んでいるのが何をする問題でどんな入出力が行われるのか、それさえも知らないままでのコード提出。そのコードが(運が良ければ)暫定1位。背徳感でゾクゾクしますね。勝負は試合開始前から始まっている「運が良ければ」と書いたのには理由があります。(以前は違ったのですが、)最近のマラソンマッチは、開始する日時が正式に予告されることは少なく、多くの人にとって「気付いたら始まってる」ものなのです。戦略を取る上では大問題です。「気付いたらマラソン始まってて、他の人が既に提出してた」は、戦略の失敗を意味するのですから。そこで、マラソンが始まりそう・始まったことにいち早く気付けるよう、常にアンテナを立てておくことが重要だと言えます。マラソンマッチ開催を知ることができる主な情報源としては以下があげられます。マラソンマッチは(日本時間)午前2時か3時*3に始まることが多いので、そのタイミングでチェックするようにしましょう。マラソンマッチのフォーラム。よる「来週の中頃にこんな感じのマラソンを始めるかも」といった書き込みがされる場合もあります。マラソンの個別問題用のフォーラムにも「この前やった問題の続編マッチをやるよー」といった予告がされるケースもあるので、こちらもチェックしておきましょう。ページに、稀にマラソンの予告が(日時つきで)出ていることがあります。指定された日を過ぎても音沙汰が無かったり、あるいはいつの間にか日付が変わったり、はたまた消滅していたりと、あまり信用できない感じです。マラソンマッチまとめ*4に登場するアカウントをフォローしておけば、誰かが「マラソン始まってる!」とつぶやくのに気付けるかもしれません。目にしたそのつぶやきは、その人がすでに最初の提出を済ませた後のものだった、というのもよくある話です。使えるのではないでしょうか(再提出のペナルティが痛い、1位になったところで中間の順位表に注目してる人はほとんどいない、などのデメリットに目をつぶれば)。~ちゃんとした解を提出して正のスコアを取ろう(ただし問題文はやっぱり読まない)~」を紹介できたらと思います。ありがとうございました。*1:一度提出したら2時間は再提出できない、みたいな制限はある*2:それでもちゃんと告知しといて欲しい*3:アメリカ東海岸時間(EST/EDT)の13:00。マラソンお疲れ様でした。終わってすぐにスライドを作ってたけど、ここからリンクしていなかったので改めて。1、おつかれさまでした。