2012-09-19

任意の数 s を k-bonacci数の同じ数を使わずに、和で表現できることの証明

http://codeforces.com/contest/225/problem/B
この問題をgreedyでとける証明

k-bonacci数列とは

$A_0 = 0, A_1 = 1, A_{n} = \sum^{n-1}_{i = max(0,n-k)}A_i$

となる数列のことです。

たとえば k = 2の時、 $\{A_n\} = \{0,1,1,2,3,5,8,13,21\}$ となります(fibnacci数列)

[1]
まず、i = 2..k+1 において、 $A_i = 2^{i-2}$
これは数学的帰納法で証明可能
よって、 $S <= 2^{k}$ となる数Sは、 $A_i (i <= k+1)$ の和を用いて Sを表すことができる

[2]
次に、 $S > 2^{k}$ の時
$A_{m+1} > S >= A_{m}$ なるmを一意に選択できる。
$S' = S - A_m$ と置くと
$2 * A_n > A_{n+1} > A_n (A_n != 1)$ が成り立つことより(帰納法で証明可)
$2 * A_m - A_m > A_{m+1} - A_m > S' > 0$
つまり、 $A_m > S'$ となる

ここで、 $A_{m'+1} > S' >= A_{m'}$ なる m'を一意に選択可能で
かつ m' < m である (∵ m >= m'+1)

この時、 S' <= 2^kなら[1]、そうでなければ[2]に当てはめることができるため
greedyで可能

2012-05-15

pythonでvisual studioを操作して、Topcoderを楽にする

秀丸エディタから VisualStudio を制御するマクロ - とりあえず日記を参考にさせていただきました。

eclipseには、SRM用のプラグインがあると聞いたのですが、visual stadioにはプラグインがないので、自分で作ってしまおうというお話

また、topcoderへのプラグインの入れ方は TopCoderでCodeProcessor+TZTester+FileEdit - Gulfweed を参考にさせて頂きました。

このプラグインは、

SRMで問題を選択した後、vsにcppファイルを登録するのめんどくさい…
英文読めねえ！

な人が作ったものなので、英語が普通に読める方には不要かと思われます。

機能

SRMで問題を選択すると、visual studioのprojectに追加されているcppファイルを自動的にremove(削除はしない)します。
問題と同時に出力されるhtmlで書かれた問題を、googleさんに自動翻訳してもらい、その後ブラウザで開きます。

ちなみに自分用のスクリプトなので、何が起こっても責任は負えません、一応。
現在テスト中なので、時々アリーナが固まるという致命的な欠陥を持っています、pythonのプロセスが終わらない時が時折発生して…

なぜわざわざpython？

pythonの練習
javaでSRM用にプラグイン書きたくなかった…(結局書いてしまいましたが)
VB.netでVSのマクロでもよかったけど、導入はpythonの方が楽そうだった
google翻訳にhtmlを投げて翻訳してもらう機能をpythonで作ってもらったので、それも一緒に使いたかった

環境

windows7 32bit home edition と windows7 64bit home edition で確認
visual stadio 2010 Pro と visual stadio 11 beta　Pro (Expressでは動きません)
python2.7(32bit or 64bit)
pywin32(http://sourceforge.net/projects/pywin32/files/pywin32/Build%20217/)
java 7 update 4

pywin32を入れないと動かないので注意
また、java 6でもpluginが動かない可能性があるので、動かなかった場合はjava7を公式http://java.com/からインストールして下さい。

ソース

ソースはgithubで公開しています。 https://github.com/math314/srm_helper

導入手順

既にSRMのプラグイン、FileEditとTZtester,CodeProcessorが入っている前提で話をします。

まず、pythonのスクリプトを好きなディレクトリにダウンロードして下さい。
https://github.com/math314/srm_helper/tree/master/helper ここに置いてあります。

ここにあるmain.pyに、cppファイルの絶対パスを渡すと、visual studioにファイルが追加されて、htmlファイルが自動翻訳されます。

次に、FileEditを https://github.com/math314/srm_helper/blob/master/FileEdit/FileEdit.jar こちらにあるファイルと入れ替えます。
その後アリーナを起動して、Editor Preferences > CodeProcessor Configuration > FileEdit Configurationに行くと以下のような画面が表示されていると思います。

Enter directory to read/write problem to: は各々設定があると思うのでスルーします。

この画面が表示されていたら成功です、下の方に"Enter execute Script:"というのがあると思います。
そこに以下のように入力します。

私の場合C:\math\Projects\competition\topcoder\helperに、pythonのスクリプトを置いてあるので、「python C:\math\Projects\competition\topcoder\helper\main.py」と入力しました。

動作を確認するために何かSRMの問題を選択すると、
既に起動していたvsの、ソースファイルがいつの間にか変わっていて、ブラウザでは自動翻訳された問題文が開いている…はずです！

これでread phaseの短縮 & vsにcppファイルを追加する手間が省けるかなと思います。

ちなみにスクリプトは例外処理などをしていないという中々ひどい状態なので、どなたかpythonがわかる方に書き直していただきたい…

2012-04-12

SRM540 DIV1 easy

easy : ImportantSequence

普通に難しい、intだと通らなかったりするので…

元の数列 {1,2,3,4}と、符号 {+-+} があり、それを計算した結果{3,-1,7}となったが、
元の数列がほしくなった為、{3,-1,7}と{+-+}から元の数列を求めたい。

この場合{1,2,3,4}と{2,1,2,5}の2通りがあるため
答えは2通りとなる。

a[0]が決まれば、自動的にa[3]が決まるので、a[3]の範囲が求まればいい。
1 <= a[0]なので、1 <= a[1] <= 2, 2 <= a[2] <= 3, 4 <= a[3] <= 5
となること利用して、答えを出す。

#ifdef TEST_CODE
#define typeof(X) std::identity<decltype(X)>::type //C++0x
#else
#define typeof(X) __typeof__(X) // for gcc
#endif

#define sz(a)  int((a).size())
#define FOREACH(it, c) for (typeof((c).begin()) it=(c).begin(); it != (c).end(); ++it)
#define FOR(i,n) for(int i = 0; i < (n); i++)

using namespace std;
static const double EPS = 1e-5;
typedef long long ll;

class ImportantSequence {
public:
  int getCount(vector <int> B, string operators) {
	  ll mn = 1,mx = LLONG_MAX;
	FOR(i,sz(B)){
		ll nmn,nmx;
		if(operators[i] == '+'){
			if(mn > B[i]) return 0;
			nmn = max<ll>(B[i] - mx,1);
			nmx = B[i] - mn;
		} else {
			if(mx <= B[i]) return 0;
			nmn = max<ll>(1, mn- B[i]);
			nmx = (mx == LLONG_MAX) ? LLONG_MAX : mx - B[i];
		}
		mn = nmn; mx = nmx;
	}
	if(mx == LLONG_MAX) return -1;
	return (int)(mx - mn) + 1;
  }

};

2012-03-22

C# + yahoo翻訳で、日本語、英語の変換を行う

書いた内容忘れそうなのでここにメモ。

EmacsからYahoo翻訳を使う - しょんぼり技術メモ
を参考にしつつ、c#で似たようなものを作ってみました。

C# .net 3.5

        static void Main()
        {
            Translate tl = new Translate();
            Console.WriteLine(tl.EN2JA("This is a pen."));
            Console.WriteLine(tl.JA2EN("これは、ペンです。"));
        }

結果

これは、ペンです。
This is a pen.

これで、翻訳結果が表示されます。

以下ソース

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Net;
using System.IO;
using System.Text.RegularExpressions;
using System.Web;

namespace csharp
{
    public class Translate
    {
        const string INIT_URL = "http://honyaku.yahoo.co.jp/transtext/";
        const string BASE_URL = "http://honyaku.yahoo.co.jp/TranslationText";
        static readonly Encoding ENC = Encoding.UTF8;
        static readonly Regex _valReg = new Regex("value=\"([^\"]+)\"", RegexOptions.Compiled);
        static readonly Regex _transReg = new Regex("\"TranslatedText\":\"([^\"]+)\"", RegexOptions.Compiled);
        static readonly Regex _utf16Reg = new Regex(@"\\u([0-9a-fA-F]{4})", RegexOptions.Compiled);

        public string EN2JA(string text)
        {
            return Trans(text, TransType.EN2JA);
        }

        public string JA2EN(string text)
        {
            return Trans(text, TransType.JA2EN);
        }

        enum TransType
        {
            EN2JA, JA2EN
        }

        /// <summary>
        /// crumbを取得
        /// </summary>
        /// <returns></returns>
        private string GetTTcrumb()
        {
            HttpWebRequest req = (HttpWebRequest)WebRequest.Create(INIT_URL);
            using (var res = req.GetResponse())
            using (var s = res.GetResponseStream())
            {
                StreamReader sr = new StreamReader(s, ENC);
                string html = sr.ReadToEnd();
                //htmlのparseは重そうなのでゴリ押しする
                var match = _valReg.Match(html, html.IndexOf("id=\"TTcrumb\""), 256);
                return match.Groups[1].Value;
            }
        }

        private string Trans(string text, TransType tt)
        {
            //crumbの取得
            string crumb = GetTTcrumb();

            //訳
            return GetTranslatedText(text, crumb, tt);

        }

        private string GetTranslatedText(string origin, string crumb, TransType tt)
        {
            HttpWebRequest req = (HttpWebRequest)WebRequest.Create(BASE_URL);

            req.Method = "POST";
            //header
            req.Referer = INIT_URL;
            req.ContentType = "application/x-www-form-urlencoded; charset=UTF-8";
            //body
            byte[] body = MakePostBody(origin, crumb, tt);
            req.ContentLength = body.Length;
            using (var rs = req.GetRequestStream())
                rs.Write(body, 0, body.Length);

            using (var res = req.GetResponse())
            using (var s = res.GetResponseStream())
            {
                StreamReader sr = new StreamReader(s, ENC);
                string json = sr.ReadToEnd();
                //やっぱりjsonのparseも面倒なのでゴリ押しする
                var matches = _transReg.Matches(json);
                return string.Join("\n",
                    matches.Cast<Match>()
                    .Select(m => _utf16Reg.Replace(m.Groups[1].Value, new MatchEvaluator(StrToChar)))
                    .ToArray()
                    );
            }
        }

        //MatchEvaluatorデリゲートメソッド
        private string StrToChar(System.Text.RegularExpressions.Match m)
        {
            //3000 ---> ' ' のように、16進数を元に文字列(UNICODE文字列)に変換する
            return new string(new char[] { (char)Convert.ToInt16(m.Groups[1].Value, 16) });
        }

        /// <summary>
        /// postするbodyを作成する
        /// </summary>
        /// <param name="tt"></param>
        /// <param name="crumb"></param>
        /// <param name="text"></param>
        /// <returns></returns>
        private byte[] MakePostBody(string text, string crumb, TransType tt)
        {
            Dictionary<string, string> dic = new Dictionary<string, string>();
            //アイテムを追加
            dic.Add("ieid", tt == TransType.EN2JA ? "en" : "ja");
            dic.Add("oeid", tt == TransType.EN2JA ? "ja" : "en");
            dic.Add("results", "1000");
            dic.Add("formality", "0");
            dic.Add("output", "json");
            dic.Add("p", HttpUtility.UrlEncode(text));
            dic.Add("_crumb", crumb);
            //"key=value"を&で繋げる
            string body = string.Join("&", dic.Select(pair => pair.Key + '=' + pair.Value).ToArray());
            return ENC.GetBytes(body);
        }
    }
}

元のライセンスが修正BSDなので、こちらも修正BSDとしておきます。要するに自己責任でどうぞ。
はてな記法わかんない :p

2011-12-21

テスト

記事テスト