ブログのとさか

技術的な話をしたりしなかったり

SuperCon 2016 予選問題をCSPソルバーで解く

SuperCon 2016 参加者の皆さん予選お疲れ様でした。予選通過するといいですね。 僕は高校生で無くなってしまったので本戦への参加権はありませんが、予選問題を読んだところCSPソルバーでさくっと解けそうだったのでやってみました。

※この記事はしっかりとした解説記事ではなく、紹介程度のものです。

CSPソルバーとは

CSPソルバーとは、問題の制約を決まった形式のテキストに変換し、そのファイルをCSPソルバーに渡して上げると、内部で「いい感じ」に問題を解いてくれるというツールです。予選参加者のみなさんは頑張って探索を最適化していったと思いますが、CSPソルバーを使うと簡単なテキストファイルを生成するだけでそれなりに高速に問題を解いてくれます。(とは言ってもみなさんのガチガチにチューニングしたプログラムの方がだいぶ速いと思います。)

CSPソルバーで虫喰い魔方陣を解く

百聞は一見にしかず。CSPソルバーについての詳しい説明は横において、今回の問題を解く様子を見てみましょう。CSPソルバーにはSugarを使います。
とはいっても、魔方陣の解法については自分が書くことはあまりなく、「CSPソルバー 魔方陣」で検索すると

http://bach.istc.kobe-u.ac.jp/sugar/puzzles/sugar-puzzles.pdf

というスライドのPDFが引っ掛かり、このスライドにある3×3魔方陣のCSPファイルと同じように6×6用のCSPファイルを生成するだけで解くことができます。

具体的には以下のようになります。

;それぞれの魔方陣のマスに入る数をx_i_jという変数で表す
(int x_0_0 1 36);整数変数 x_0_0 の宣言。範囲は 1 <= x_0_0 <= 36 となる。
(int x_0_1 1 36)
(int x_0_2 1 36)
(int x_0_3 1 36)
(int x_0_4 1 36)
(int x_0_5 1 36)
(int x_1_0 1 36)
(int x_1_1 1 36)
(int x_1_2 1 36)
(int x_1_3 1 36)
(int x_1_4 1 36)
(int x_1_5 1 36)
(int x_2_0 1 36)
(int x_2_1 1 36)
(int x_2_2 1 36)
(int x_2_3 1 36)
(int x_2_4 1 36)
(int x_2_5 1 36)
(int x_3_0 1 36)
(int x_3_1 1 36)
(int x_3_2 1 36)
(int x_3_3 1 36)
(int x_3_4 1 36)
(int x_3_5 1 36)
(int x_4_0 1 36)
(int x_4_1 1 36)
(int x_4_2 1 36)
(int x_4_3 1 36)
(int x_4_4 1 36)
(int x_4_5 1 36)
(int x_5_0 1 36)
(int x_5_1 1 36)
(int x_5_2 1 36)
(int x_5_3 1 36)
(int x_5_4 1 36)
(int x_5_5 1 36)

; すべての変数は互いに違う数を取る
(alldifferent x_0_0 x_0_1 x_0_2 x_0_3 x_0_4 x_0_5 x_1_0 x_1_1 x_1_2 x_1_3 x_1_4 x_1_5 x_2_0 x_2_1 x_2_2 x_2_3 x_2_4 x_2_5 x_3_0 x_3_1 x_3_2 x_3_3 x_3_4 x_3_5 x_4_0 x_4_1 x_4_2 x_4_3 x_4_4 x_4_5 x_5_0 x_5_1 x_5_2 x_5_3 x_5_4 x_5_5)

;縦、横、対角線のマスに入る数の和が111になる(ポーランド記法で書く)
(= 111 (+ x_0_5 (+ x_0_4 (+ x_0_3 (+ x_0_2 (+ x_0_1 x_0_0))))))
(= 111 (+ x_1_5 (+ x_1_4 (+ x_1_3 (+ x_1_2 (+ x_1_1 x_1_0))))))
(= 111 (+ x_2_5 (+ x_2_4 (+ x_2_3 (+ x_2_2 (+ x_2_1 x_2_0))))))
(= 111 (+ x_3_5 (+ x_3_4 (+ x_3_3 (+ x_3_2 (+ x_3_1 x_3_0))))))
(= 111 (+ x_4_5 (+ x_4_4 (+ x_4_3 (+ x_4_2 (+ x_4_1 x_4_0))))))
(= 111 (+ x_5_5 (+ x_5_4 (+ x_5_3 (+ x_5_2 (+ x_5_1 x_5_0))))))
(= 111 (+ x_5_0 (+ x_4_0 (+ x_3_0 (+ x_2_0 (+ x_1_0 x_0_0))))))
(= 111 (+ x_5_1 (+ x_4_1 (+ x_3_1 (+ x_2_1 (+ x_1_1 x_0_1))))))
(= 111 (+ x_5_2 (+ x_4_2 (+ x_3_2 (+ x_2_2 (+ x_1_2 x_0_2))))))
(= 111 (+ x_5_3 (+ x_4_3 (+ x_3_3 (+ x_2_3 (+ x_1_3 x_0_3))))))
(= 111 (+ x_5_4 (+ x_4_4 (+ x_3_4 (+ x_2_4 (+ x_1_4 x_0_4))))))
(= 111 (+ x_5_5 (+ x_4_5 (+ x_3_5 (+ x_2_5 (+ x_1_5 x_0_5))))))
(= 111 (+ x_5_5 (+ x_4_4 (+ x_3_3 (+ x_2_2 (+ x_1_1 x_0_0))))))
(= 111 (+ x_5_0 (+ x_4_1 (+ x_3_2 (+ x_2_3 (+ x_1_4 x_0_5))))))

ただし、このCSPファイルはすべての魔方陣のマスが開いている状態の制約を表しているので、既に埋まっている場所は制約として追記して上げる必要があります。 例えば次の魔方陣の場合、

18 13 35
20 33 19 7
2 32 10 9
30 3 15
29 4 26 28
5 31 16

以下の様に制約を追記します。

(= x_0_1 18)
(= x_0_3 13)
(= x_0_4 35)
(= x_1_1 20)
(= x_1_2 33)
(= x_1_3 19)
(= x_1_4 7)
(= x_2_1 2)
(= x_2_2 32)
(= x_2_4 10)
(= x_2_5 9)
(= x_3_0 30)
(= x_3_3 3)
(= x_3_5 15)
(= x_4_1 29)
(= x_4_2 4)
(= x_4_4 26)
(= x_4_5 28)
(= x_5_2 5)
(= x_5_3 31)
(= x_5_4 16)

あとはこのファイルを適当な名前(ここではmahou.cspとします)で保存し、sugarに渡すだけです。

% sugar mahou.csp
s SATISFIABLE
a x_0_0 6
a x_0_1 18
a x_0_2 25
a x_0_3 13
a x_0_4 35
a x_0_5 14
a x_1_0 11
a x_1_1 20
a x_1_2 33
a x_1_3 19
a x_1_4 7
a x_1_5 21
a x_2_0 36
a x_2_1 2
a x_2_2 32
a x_2_3 22
a x_2_4 10
a x_2_5 9
a x_3_0 30
a x_3_1 34
a x_3_2 12
a x_3_3 3
a x_3_4 17
a x_3_5 15
a x_4_0 1
a x_4_1 29
a x_4_2 4
a x_4_3 23
a x_4_4 26
a x_4_5 28
a x_5_0 27
a x_5_1 8
a x_5_2 5
a x_5_3 31
a x_5_4 16
a x_5_5 24
a

この通りに埋めると

6 18 25 13 35 14
11 20 33 19 7 21
36 2 32 22 10 9
30 34 12 3 17 15
1 29 4 23 26 28
27 8 5 31 16 24

となり、確かに解けていることが分かります。(すごい!)

実行時間をtimeコマンドで計測すると

real 0.94
user 0.46
sys 0.47

となりました。まぁまぁですかね。実行環境はVirtualBox上のUbuntu(メモリ1GB、CPU Core i7-6650U 2.20GHz)、内部で使用しているSATソルバーはMinisatです。
最悪ケースでどうなるかは自分も確かめてないので試してみてください。

このように、CSPソルバーを使うと問題の解が簡単に得られます。もちろん魔方陣以外にも様々な問題を解くことができます。
SuperConのような単一のソースファイルを提出するコンテストではこれをそのまま回答コードとして流用するのは難しいですが、覚えておくとテストケース生成の際などに役立つかもしれません。

参考

ひとりごと

本当は魔方陣のルールをdirect encodingとorder encodingで表すプログラムをそれぞれ書いて比較するっていうテーマにして、Sugarはついでで紹介するだけみたいなブログ記事にする予定だったけど、ちょっと時間が取れ無さそうだったのでとりあえずSugarの紹介だけすることにしました...
あと本当はWindows上でSugarを動作させたかったけど、うまく行かなかったので後回し中。でも大体原因がわかった(と思う)ので、もしできたらそれについてのブログも書くかも...?
SuperCon、現役としてもう一回やりたかったなあ。

SRM 677 Div1 Easy DoubleOrOneEasy

https://community.topcoder.com/stat?c=problem_statement&pm=14101&rd=16627

問題概要

整数a, b, newA, newBが与えられる。 (a, b)に対しそれぞれ同時に+1または*2する操作を繰り返して(newA, newB)に変える時の、操作の最少回数を求める。(変えられないなら-1)

ゆるふわな解法

+1を2回することは*2を1回することと等しいので、一番最初に*2をする前以外で+1を2回以上するのは無駄だよね。 という話から、最初に+1する回数をx、*2をする回数をnとすると、操作は(a * 2^n) + (x * 2^n) + (1or0 * 2^(n-1)) + ... + (1or0 * 2^1) + (1or0 * 2^0)みたいな式で表せることがわかる。
(x * 2^n) + (1or0 * 2^(n-1)) + ... + (1or0 * 2^1) + (1or0 * 2^0)をkとおくと、a * 2^n + k == newA && b * 2^n + k == newBとなる時のnが答えの操作で*2する回数になる。 このnはたかだかlog(newA)<30程度なので1から順に試せばOK。
ちなみに(1or0 * 2^(n-1))以降の1or0の並びはnewA - (a * 2^n) + (x * 2^n)を2進数で表した時と等しくなるので、この部分で+1した回数はpopcountで求められて嬉しい。
計算量O(log(newA))

コード

INT_MAXのところを始めINF(= 1 << 29)にしていて落ちたりした。不注意...
そもそもa==bの時以外はremA==remBになったらすぐreturnしてもいいんだけどね。

#include "bits/stdc++.h"
using namespace std;

const int INF = 1 << 29;

//VSでコーディングしてるので拝借してきました http://www.nminoru.jp/~nminoru/programming/bitcount.html
int popcount(int bits)
{
    bits = (bits & 0x55555555) + (bits >> 1 & 0x55555555);
    bits = (bits & 0x33333333) + (bits >> 2 & 0x33333333);
    bits = (bits & 0x0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f);
    bits = (bits & 0x00ff00ff) + (bits >> 8 & 0x00ff00ff);
    return (bits & 0x0000ffff) + (bits >> 16 & 0x0000ffff);
}

class DoubleOrOneEasy
{
public:
    int minimalSteps(int a, int b, int newA, int newB)
    {
        int kake = 1;
        int ksum = 0;
        int ans = INT_MAX;
        while (a * kake <= newA && b * kake <= newB)
        {
            int remA = newA - a * kake;
            int remB = newB - b * kake;
            if (remA == remB)
            {
                int tmp = ksum + remA / kake + popcount(remA % kake);
                ans = min(ans, tmp);
            }

            kake *= 2;
            ksum++;
        }

        return ans == INT_MAX ? -1 : ans;
    }
};

解いた問題をブログに上げるというのを初めてやってみたところ、意外と書くのが面倒で解説はもはや分からせる気も厳密に書く気もない感じになってしまった。
この問題はなんとなく競プロしようと思って最近の問題から適当に選んだけど、久しぶりに(自分にとって)やるだけじゃない問題を解いた気がする。
SRM Div1の問題を提出したのは初めてかもしれない。TopCoderCodeforcesは今までほとんどやって来なかったのでどんどんやっていきたいなあ。

(操作ミスで記事を消してしまったため再投稿です)

優秀な同世代の仲間を見つけよう

この記事について

中高生プログラマ Advent Calendar 2015 6日目です。
どうも皆さん。とさか2です。高校3年生をやっています。
「中高生プログラマ」という肩書の中では一応年長者(このアドベントカレンダーでは高専4,5年生の方も参加していますが)なので、今までの経験から、まだまだ中高生をやっていられる優秀で有望な皆さんに向けて伝えたい的な記事です。あまり技術的な話はしません。

自己紹介

この企画は学生間の交流を兼ねてるらしいので、自己紹介をします。
一番得意な言語はC#です。開発と競技プログラミングをしてます。コンピュータ部の部長を務めていたりもしました。CTFはあまりやってませんが、scryptosで準メンバー的に何回か参加してました。
他の分野だとゲームAI・機械学習ヒューリスティックアルゴリズムの勉強をしたりコード書いたりしています。
CombGigでは一応運営側として参加してたので、そこで会ったことがある人もいるかもしれません。
twitter@nanTosaka2です。( 諸事情あって鍵がかかっています。もう少ししたら外すかも。 鍵外しました)

本題

皆さん御存知の通り、一口に「プログラミング」と言っても様々な用途があります。
それに伴い、プログラマのコミュニティも用途ごとに形成されています。特に最も人口が多い「ソフトウェア開発」に関しては、使用言語やフレームワークなどでそれなりに強くコミュニティが分断されています。
それ以外の要素として、所属組織や住んでいる地域によって分けられることを考えると、各々が所属するコミュニティは必然的に小さくなります。

さらに、開発コミュニティは平均年齢が高く、中高生が同世代と同じコミュニティで出会うというのはなかなか難しいように感じます。
結果として、同世代の中で自分が一番優秀なのではないかという気がしてくるのがよくあるパターンです。
それはそれで幸せな生き方だとは思います。しかし、技術力を上げるという観点から見ても、「自分が一番優秀だ」というのが思い込みだった場合、早めにそれに気付いた方が良いでしょう。
勘違いをしていなくても、優秀な同世代の仲間がいたほうがモチベーションが上がると思います。さらに言えば、将来的に有用な人脈になるかもしれません。

というわけで、ここでは優秀な同世代の仲間と出会う方法について書いていきたいと思います。

1.twitter

すべてはtwitterのアカウント作成から始まります。 以下で紹介する方法で出会った人と繋がりを保つにはtwitterが一番です。 また、ある程度繋がりが広くなってくるとtwitterを通じて新しく知り合うことも出てきます。 アカウントを持っていない人は絶対に作りましょう。

2.セキュリティ・キャンプ

セキュリティ・キャンプは、合宿形式の情報セキュリティ技術に関する勉強会です。
大学生以下対象なので、一度に大量の同世代の人々と出会うことが出来ます。参加者は、セキュリティに詳しくない人でも、別のコンピュータ技術分野には精通している人であることが多いので、そのつもりで交流すると良いでしょう。
参加のためには選考を通る必要がありますが、それさえ通れば交通費含め全額無料で参加できるので最高です。 夏に一度ある全国大会以外にも、地方大会が行われているそうなので、地方の方はまずそちらに参加してみてもいいでしょう。

3.競技プログラミングの大会への参加

競技プログラミングは、「アルゴリズム」の設計と実装の能力を競うプログラミングを使った「競技」です。与えられた問題を解くプログラムを作成し、提出すると機械的に採点され、それの結果に応じて順位が付きます。
プログラミングコンテストと呼ばれることもありますが、アプリケーションを作成して提出するもの(U22プログラミングコンテストなど)とは全くの別物です。
順位がつくので強さがはっきりと分かります。初めたばかりの頃は上位陣の圧倒的な実力に驚かされるでしょう。

一応書いておくと、これはソフトウェア開発とは非常に異なるものなので、プログラマだからといって競技プログラミングが出来なければいけないわけでは決してありません。
しかし、プログラミングと深い関わりを持ちながらも、開発ではあまり触れることのない「アルゴリズム」を身をもって体験できるので、一度くらい取り組んで見るのが良いと思います。練習を重ねると実装速度が上がるので、開発にも役立ちます。あと単純に面白いです。

中高生向けの大会では以下の三つが有名です。 以下の全ての大会では競技時間とは別に懇親会等の時間が設けられているので、勝ち上がったら存分に交流することが出来ます。
1. 日本情報オリンピック
2. パソコン甲子園 プログラミング部門
3. SuperCon

日本情報オリンピックは予選で勝ち上がると関東にある会場に集められ本戦を行い、そこで20位以内に入ると代表選考合宿に参加できます。さらにそこで3位以内になると、日本代表として、海外で行われる国際情報オリンピックに参加できます。ここでかかる交通費や宿泊費等は全て無料です。最高。
パソコン甲子園の本戦は会津大学で行われます。勝つとガッツリ賞金をもらえます。
SuperConの本戦は大阪大学東京工業大学で行われます。この本戦は独特で、 スーパーコンピュータ上で行います。スパコンプログラミングは通常のプログラミングと異なる部分が結構多いので、結構面白いです。
ちなみに、以上の三つで結果を残せば大学受験で有利になったりもします。参加しない手はないな!

中高生向けの大会以外でも、様々なコンテストが開催されています。国内だとAtCoderが有名です。社長は@chokudaiさんです。
基本オンラインですし、参加費も無料なので気軽に参加してみましょう。

「競技プログラミングをしている」というだけで結構簡単に繋がりが広げられると思うので、おすすめです。

4.JOI夏季セミナー

夏期セミナーは先述の情報オリンピックを開催している団体が開いている合宿です。書類選考はありますが、競技プログラミングが出来なくても参加できます。
情報科学に関連する本を読んで演習(実装)したり講義を聞いたりします。これは参加者も扱う内容もレベルが高いです。
僕は日程が合わず一度も参加できなかったのでものすごく後悔しています。皆さんは後悔の無いようぜひ参加してください。

5.中高生向け勉強会

中高生向けの勉強会に参加するか、皆さんの手で開催してください。様々な人と交流できます。
CombConfCombGig・Comb Meetup等の前例があります。
開催のノウハウは@mt_caretに相談すれば喜んで教えてくれると思います。お気軽にどうぞ。
僕はもう中高生では無くなりますが、次の開催者が現れることを期待しています。


以上です。
これらのイベントに参加する際は、名刺を用意しておくのが一般的なので、作っておきましょう。twitterのハンドルを書くのを忘れずに!