Joken Marathon Contest #1

WELCOME TO Joken Marathon Contest

Information

  • The contest is running now.

JMC魔法陣予選大会

 Joken魔法陣委員会(Joken Mahojin Committee)はJoken内部で発足した魔法陣を研究するための委員会である。るーなのば魔法学校との魔法陣対抗戦を控えたJMCの面々は、対抗戦への出場者を決定するために、委員会内で予選を開催することにした。

 魔法陣予選大会は次のルールで行われる。

  • 参加資格はJMC会員あるいはJoken会員、あるいはJoken会員に招待された人間であること。
  • 幾つかの既に用意された魔法陣について、これを改良する。最もよく改良できた参加者が、その魔法陣に関して1位となり、1位相当の点を得る。次点の魔法陣の作成者については2位相当の点を得る。すべての魔法陣についてこれを行い、総合得点の最も大きい者が総合1位となる。なお、ある魔法陣について、同程度の改良が行われた場合、より早く改良を行ったものが上位となる。
  • 各魔法陣への改良によって得られる点数は、その魔方陣の改良に着手した人数をnとすれば、順位rの参加者には n - r + 1点が与えられる。ただし、r=1の場合に限り、n - r + 1 + 5点が与えられる。たとえば、ある魔法陣について、A, B, Cの三人が改良手法を提出していて、順位が、A、B、Cの順番なら、Aには8ポイント、Bには2ポイント、Cには1ポイントが与えられる。
  • 魔法陣の改良について、詳細は後述するが、魔法陣の良さを評価する手法が存在し、その手法では評価値(スコアとも言う)が小さいほど良い魔法陣であるとされる。
  • 各会員の地力の差を考慮してハンディキャップを採用する。会員はハンディキャップとして、自分の魔法陣のスコアをn(1 <= n <= 1.1)倍してもよい。このnをハンディキャップ係数と呼び、競技終了の24時間前まで変更が可能である。ハンディキャップ係数はすべての魔法陣の評価値に適用される。たとえば、ある魔法陣について、Aがスコア1000であるような提出をおこない、Bがスコア1010であるような提出を行った場合、素点ではAが上位になるが、Aがハンディキャップとして自身のスコアを1.02倍するような設定にしていた場合にはAのスコアは1020として計算されるから、Bの方が上位になる。
  • 開催期間は、JSTで2/18 10:00から2/21 23:59までの86時間である。その間、何度でも魔法陣を改良することができる。また、この期間中に魔法陣の改良手法について、他の参加者と議論することは禁止する。
  • 協議についての質問はSlackで受け付ける。また、問題の訂正などの連絡すべき事項がある場合には、このページの最上部に掲載する。

客員、魔法陣対抗戦代表への切符を勝ち取るために鋭意努力して貰いたい。

魔法陣について、その評価手法について

 魔法陣は n2-1パズルと酷似した形状を有する。つまり、n*nの正方形の升のような形をしている。各升には1からn-1までの数字が一度ずつ書き込まれている。そして、何も値が書き込まれていないマスが1つだけ存在する。

 魔法陣は適当に扱うと、その効力が変わってしまったり、効力を失ったりしてしまうが、四種類の操作が許可されている。それらはhjklと呼ばれる魔法である。

  • h……空白マスと、その左にあるマスの値を入れ替える。ただし、空白マスの左にマスがない場合にはこの魔法は失敗する。
  • j……空白マスと、その下にあるマスの値を入れ替える。ただし、空白マスの下にマスがない場合にはこの魔法は失敗する。
  • k……空白マスと、その上にあるマスの値を入れ替える。ただし、空白マスの上にマスがない場合にはこの魔法は失敗する。
  • l……空白マスと、その右にあるマスの値を入れ替える。ただし、空白ますの右にマスがない場合にはこの魔法は失敗する。

 これらの魔法を何度でも使って、魔法陣を変形し、改良を行うことができる。魔法陣の良さを表す値、評価値(スコア)については、以下の方法で算出される。

  1. 魔方陣の各行、各列、左上頂点から右下頂点への一列のそれぞれについて、その総和を求める。これをXと呼ぶ。
  2. 集合Xの平均の値μを求める。
  3. Xの各値Xiについて、(Xi - μ)2を求める。このように計算された値の集合をX'とする
  4. X'の平均値σ2を求める。この値が魔方陣の評価値である

 現在の魔法陣については、次の形式で与えられる。

  • ファイルの先頭1行目には、数値nが示されている。この値が魔法陣の大きさを表す。
  • 続くn行に渡って、空白区切りでn個の数字が与えられる。これが魔法陣の本体である。ただし、魔方陣の空白マスについては数値0で表す。
 魔法陣の改良魔法については、次の形式で出力する必要がある。
  • 出力は1行で、hjklからなる文字列である。各文字で示される魔法が左から順に実行される。

 例 3*3の魔法陣について、入力ファイルは次のようになる。

3
6 8 0
4 5 3
1 7 2

 この魔方陣の初期状態での評価値は、およそ17である。これに次のような改良魔法を与える。

jhjkkljjhlkh

 改良後の魔法陣は以下のようになる。改良後の魔法陣の評価値はおよそ5である。

6  3  5
4  0  8
1  7  2