class Xylophone
{
    public static int countKeys(int[] keys)
    {
        bool[] b = new bool[7];
        foreach (var i in keys)
        {
            b[i % 7] = true;
        }
        int ans = 0;
        for (int i = 0; i < b.Length; i++)
        {
            if (b[i]) ans++;
        }
        return ans;
    }
}

XMarksTheSpot (Med)

問題

TopCoder Statistics - Problem Statement

方針

全探索。まずは盤面を調べる。
'O'の上下左右の端を調べて持っておき、'?'の位置を調べて持っておく。
'?'が'O'であるか'.'であるかを全通り場合分けして試す。ビット演算を使うとよい。

ちなみに?の場合分けをする際、毎回盤面を調べているとシステムテストで落ちる。

ソースコード(C#)

using System;
using System.Collections.Generic;
class XMarksTheSpot
{
    public static int countArea(string[] s)
    {
        int ans = 0;
        List<int> qx = new List<int>();
        List<int> qy = new List<int>();
        int l = int.MaxValue;
        int r = int.MinValue;
        int u = int.MaxValue;
        int d = int.MinValue;
        for (int i = 0; i < s.Length; i++)
        {
            for (int j = 0; j < s[0].Length; j++)
            {
                if(s[i][j]=='?')
                {
                    qx.Add(i);
                    qy.Add(j);
                }
                else if (s[i][j] == 'O')
                {
                    l = Math.Min(l, j);
                    r = Math.Max(r, j);
                    u = Math.Min(u, i);
                    d = Math.Max(d, i);
                }
            }
        }

        for (int bitcnt = 0; bitcnt < (1<<qx.Count); bitcnt++)
        {
            int ltmp = l;
            int rtmp = r;
            int utmp = u;
            int dtmp = d;
            for (int qcnt = 0; qcnt < qx.Count; qcnt++)
            {
                if (((bitcnt >> qcnt) & 1) == 1)
                {
                    ltmp = Math.Min(ltmp, qy[qcnt]);
                    rtmp = Math.Max(rtmp, qy[qcnt]);
                    utmp = Math.Min(utmp, qx[qcnt]);
                    dtmp = Math.Max(dtmp, qx[qcnt]);
                }
            }
            
            ans += (rtmp - ltmp + 1) * (dtmp - utmp + 1);
        }
        return ans;
    }
}

XYZCoder (Hard)

問題

TopCoder Statistics - Problem Statement

方針

DP。
順位が下の人間から見ていき、順位を決めた人間の数、部屋内での優勝者が決まった数をキーにしてDPすればよい。
最後に、優勝者の順列を出すために、部屋数の階乗を掛ける。
適宜modをとること。

DPの雑なイメージはこちら。

使った人数＼部屋トップが決まった人数	0		1		2		3
6	1		5		9		5
	↑	↗	↑	↗	↑	↗	↑
5	1		4		5		0
	↑	↗	↑	↗	↑		↑
4	1		3		2		0
	↑	↗	↑	↗	↑		↑
3	1		2		0		0
	↑	↗	↑		↑		↑
2	1		1		0		0
	↑	↗	↑		↑		↑
1	1		0		0		0
	↑		↑		↑		↑
0	1		0		0		0

ソースコード(C#)

class XYZCoder
{
    public static int countWays(int room,int size)
    {
        long ans = 1;
        long mod = 1000000007;

        long[,] dp = new long[room * size + 10, room + 10]; //member,winner
        dp[0, 0] = 1;
        for (int member = 1; member <= room*size; member++)
        {
            for (int winner = 0; winner <= room; winner++)
            {
                if(winner>0 && member >= winner*size)
                {
                    dp[member, winner] = (dp[member - 1, winner] + dp[member - 1, winner - 1]) % mod;

                }
                else
                {
                    dp[member, winner] = dp[member - 1, winner];
                }
            }
        }
        ans = dp[room * size, room];
        for (int i = 1; i <= room; i++)
        {
            ans = (ans * i) % mod;
        }
        return (int)(ans % mod);
    }
}

2016-10-12

AOJでC#を快適に使うための(バッド)ノウハウ

競技プログラミング AOJ

本記事では、AOJで快適にC#を使うための(バッド)ノウハウを紹介します。

warningを無視する

AOJでは、warningが出るだけでCEにされます。
1つ未使用の変数があるだけでCEになるのは非常につらい。

対策

以下の1行をコードに追加します。
これが記述された行より下の行で発生するすべての警告を無視します。
位置は冒頭がおすすめ。

#pragma warning disable

System.Numerics を使わない

これです。

using System.Numerics;

AOJでは使えない模様。
ちなみにAtCoderでは使えます。

対策

あきらめる。

C# 5 以上の機能を使わない

こんなコードは書けません。

using static Hoge;
class Program
{
    static void Main(string[] args)
    {
        int i = a(3);
    }
}
static class Hoge
{
    public static int a(int x) => x * 2;
}

対策

あきらめる。

class Program
{
    static void Main(string[] args)
    {
        int i = Hoge.a(3);
    }
}
static class Hoge
{
    public static int a(int x) { return x * 2; }
}

おわりに

有益情報や間違いがあれば、後学のためにぜひ教えてください。
C#競技プログラマはつらいよ。

2016-10-08

AOJ 1357 Squeeze the Cylinders

競技プログラミング AOJ

問題

Squeeze the Cylinders | Aizu Online Judge

n個の円柱があり、それぞれの半径が与えられる。
円柱は地面に沿って転がして動かせるが、円柱の順番は入れ替えられない。
一列に並んだ円柱を両側から壁で押したとき、壁同士の最短距離はいくらになるか求めよ。

解法

左側の壁がx=0にあるとする。
i番目の円柱のx座標は、左側の壁に接している場合、0～i-1番目の円柱に接している場合のうち、最も遠いもの。
右側の壁は、0～n-1番目円柱に接している場合のうち、最も遠いもの。
n<=500なので、全て調べても間に合う。

ソースコード(C#)

using System;
using System.Collections.Generic;
using System.Linq;

namespace _1357
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            double[] y = Console.ReadLine().Split().Select(double.Parse).ToArray();
            double[] x = new double[n];
            double xmax = 0;
            for (int now = 0; now < n; now++)
            {
                double nowx = y[now];
                for (int bef = 0; bef < now; bef++)
                {
                    nowx = Math.Max(nowx, x[bef] + Math.Sqrt(Math.Pow(y[now] + y[bef], 2) - Math.Pow(y[now] - y[bef], 2)));
                }
                x[now] = nowx;
                xmax = Math.Max(xmax, x[now] + y[now]);
            }
            Console.WriteLine(xmax);
        }
    }
}

2016-09-20

Pixivでメアドが再利用可能か試してみた

イラスト

現在登録しているメアドを別のPixiv idに紐づけできるか試してみました。

事の発端

もともとROM専するために別名義でPixivに登録していたのですが、自分の作品もUPしたほうが紹介するときに便利かな、と思ったのでidを変えたくなりました。

ところが、Pixivではidの変更はできません。仕方がないので新規登録です。

でも、どうせなら普段使っているメアドでログインできるようにしたい。果たして一度ほかのアカウントと紐づけたことのあるメアドは再利用できるのか。

実際にやってみましょう。

やったこと

id: hoge mail: hoge@example.com で登録

id: hogeの登録メアドをhoge2@example.com に変更

id: fuga mail: hoge@example.com で登録

結果

fugaさんの登録に成功しました。やったね。

というわけで、メアドは再利用できました。

2016-09-19

ISUCON6予選をwebサービス初心者が通過しました #isucon

ISUCON

ISUCON6の予選を通過しました。

私はwebサービス初心者だったのですが、初心者の視点から、チームで何を考え行ったかをメモしておきます。

ISUCONとは

いい感じスピードアップコンテスト。 webサービスが与えられるので頑張って高速化します。詳しくは公式サイトを読んでください。

isucon.net

今回のお題は、はてなスターやはてなキーワード的機能が付いたWikiサイト。

チーム

チーム: innocent:
チームメイト: @utgwkk @wass80

チームメイトのブログはこちら。

utgwkk.hateblo.jp

www.wass80.xyz

参加動機

本選参加者の名札がかっこよく、欲しかったので。

やったこと

プロファイル計測
nginxで静的ファイルをキャッシュ
SQLで呼び出すcolumnを必要最小限に
不要なHTTP通信の除去
正規表現による置換の回数を減らす
正規表現に渡す引数を減らす

ソースコードはこちら。

github.com

結果

最終スコア: 19610

学生枠8位!

isucon.net

反省

slackで情報伝達したのはよかった
GitHubのプライベートリポジトリでソースを見られるようにしたのもよかった
- commit方針は気が向いたときにスナップショットというゆるふわ運用だった
ホワイトボードやプロジェクタのある環境は便利
スキル向上、環境構築をして個々が同時並行で別の作業ができるようにしたい
キャッシュを使えるようにしたい
便利スクリプトとか用意しておくとよさそう
その場で使い方を調べる事態が多発したので事前に練習しておきたい

感想

前日までの練習はazureにvmを立てるくらいしかしていなかった。でもやっておいてよかった。ボタンを押してsshキーを登録するだけでデプロイできるのは面白かった。
最初はよくわからなかったけれどソースとチームメイトを眺めているうちに世界観が分かってきた。
途中から競技プログラミングを解いている気持ちになった。
0点だった間はつらい気持ちだったが、正の点数が取れると楽しくなってきた。
チームメイトの2人には感謝しかない。
本選では正の点数をとれるように頑張りたい。
~~はてなキーワード aho corasick 検索~~
~~松屋お持ち帰りはコスパがよい。~~

当日の様子

azureにvmをデプロイ。sshkeyの準備に手間取る。何故か私のアカウントからリソースグループが確認できないが、どうせsshするので気にしないことにした。
メンバーが慣れていることから言語はrubyを選択。とりあえず初期実装でベンチマークを走らせるもPASS 0点。動いてはいるが GET / などがタイムアウトになり減点されまくっているようだ。なんとなくperlで動かしてみたら3000点くらい取れていた。~~最悪これを提出しよう~~
rack-lineprof でプロファイルをとることにした。クリティカルに重い箇所を改善しようというISUCONの基本を再確認した。
このあたりでなぜかベンチマークがFAILで落ちる現象が発生。結構悩む。どうやらプロファイルを取りながらベンチマークを走らせると処理が追い付かずに例外を吐くらしいことが分かった。プロファイル取得のon/offを切り替えられるようにした。

htmlifyのkeywords周りが重そうということが分かった。不要な情報まで読み込んでいたSQLを改良した。

- keywords = db.xquery(%| select * from entry order by character_length(keyword) desc |)
+ keywords = db.xquery(%| select keyword from entry order by character_length(keyword) desc |)

GET / の代わりに POST /star でタイムアウトするようになったので重い箇所を探す。 keywordが存在するかチェックするところでHTTP通信をしているのを発見。 HTTP通信は重そうだったので直接SQLをチェックするクエリを投げるように変えた。点数が正(1500位)になってチームの士気が上がりだす。
こんどはまた GET / がタイムアウトするようになった。 keywordの正規表現生成を each do の中で回していることが分かった。 htmlify関数の外に出し、1度だけ呼び出すようにした。ここで3000点位。~~perl初期実装に追いついた。~~
このあたりで静的ファイルをnginxでキャッシュするように設定した。スコアへの寄与はあまり実感できなかったが、おそらく効いていると信じる。
点数は上がったものの、未だに GET / がタイムアウトする。正規表現での置換が重い問題に全てのリソースを割くことにする。
keywordをひたすら|で並べる正規表現が重いということが分かっていたので、 keywordを1つずつ正規表現で置換するアルゴリズムを試した。 8000点を取るも、ベンチマークが「ページ hoge の中に fuga へのリンクがありません」みたいなメッセージを出す。不幸な偶然だろうとベンチマークを取り直すも、点数は安定せずついにはFAILした。
アルゴリズムの再検討を始めた。トライ木の実装や、rubyでの高速な文字列処理ライブラリ導入を試みるも失敗する。キャッシュに乗せておくことも検討したが、不慣れなためredisの導入で手間取りそうだったので保留。
初期実装をベースに考え直すことに。オーダー単位での改善方法が思いつかなかったので、定数倍の改善を図る。これまでの実験により、正規表現に渡すkeywordが多いと重くなることが分かっていたので、全てのkeywordを正規表現に渡すのをやめ、 content内に出てくるkeywordのみを抽出して正規表現に渡すことにした。 12000点位になった。
この時点で残り1時間を切っていたため、これ以上のチューニングをやめて再起動チェックを行った。プロファイル計測を止め、不要なサービスを落としたうえでベンチマークを走らせた。 19610点をマークし、~~予選通過に十分な点数と判断したため、~~下手にいじってミスしたくなかったので、作業を終えた。
あとは終了時間までひたすら祈っていた。