他人の空似

2011 年 9 月 25 日

非想天測1.10aパッチについて

Filed under: 東方,解析 — 中の人 @ 6:49 AM

気付いた人は気付いたかもしれませんが、th123d.datというファイルが追加されています。
リプレイの互換性があるのに追加ファイルとはどういうことなのか?
気になったので調べてみました。

とりあえずtouhouSEで展開してみると、中には文のモーション定義ファイルが一個だけ入っていました。
手元のツール(非公開品)にて解析してみると、天狗の太鼓から喰らい判定が一個削除されていることがわかりました。
天狗の太鼓と言えば、意味不明なところに喰らい判定があるバグが有名ですが、もしやこっそり修正されたのか?
と思い、検証用のリプを1.10でとり、それを1.10aで再生してみたのですが、普通に喰らいました。

調べてみると、どうやらth123d.datは追加されただけで読み込む処理は入っていないようです。
そこでth123d.datの読み込み処理を追加するパッチを作って試してみたところ、天狗の太鼓バグが発生しなくなりました。
どうやら推測は当たっていたようです。

どうしてファイル入れるだけで有効化していないのかはわかりませんが(リプレイの互換性対策?)、一応天狗の太鼓バグなどを直すつもりではいるようです。
いつになるかはわかりませんがまったり待っていましょう。

2011 年 9 月 20 日

SRM519

Filed under: SRM — 中の人 @ 11:31 PM

最近topcoderさんのSRMに参加し始めました。
せっかくなので、自力をつける意味も含めて戦績などを書いていこうと思います。

WhichDay:DIV2イージー250点問題

元問題:http://community.topcoder.com/stat?c=problem_statement&pm=11553
概要:(意訳)曜日を表す文字列を6つ渡すので、その中に含まれない曜日を返しなさい。
提出したコード:


#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <limits.h>

#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <iterator>
#include <numeric>
#include <functional>
#include <algorithm>
#include <utility>


class WhichDay {
public:
  std::string getDay(std::vector<std::string> notOnThisDay) {
    const char * const list[] = {
      "Friday", "Monday", "Saturday", "Sunday", "Thursday", "Tuesday", "Wednesday"
    };
    std::sort(notOnThisDay.begin(), notOnThisDay.end());
    for(unsigned int i = 0; i < notOnThisDay.size(); i++) {
      if(notOnThisDay[i] == list[i]) {
        continue;
      }
      return list[i];
    }
    return list[6];
  }
protected:
};

説明するまでもないですがm、ソート済みのlistとソートした引数を先頭から比較し、相違した曜日、もしくはlist末尾の曜日を返しているだけです。
こういった実装は珍しく、bool配列を持たせて一致した物のフラグを立てていくものが主流、稀にbool配列の代わりに整数を用いたものがありました。
チャレンジの狙い目も特になし、強いて言うならコード中の曜日に誤字がないか、ぐらい?

ThreeTeleports:DIV2ミディアム600点問題

元問題:http://community.topcoder.com/stat?c=problem_statement&pm=11554
概要:(意訳)無限に続く格子状平面でxかy方向に1動くのに1秒、全部で3つ(入口の数で数えると6つ)のテレポートで移動するのに10秒かかる、スタートから目的地まで最短で何秒かかるか。


#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <limits.h>

#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <iterator>
#include <numeric>
#include <functional>
#include <algorithm>
#include <utility>


class ThreeTeleports {
public:
  int shortestDistance(int xMe, int yMe, int xHome, int yHome, std::vector<std::string> teleports) {
    long long int ret = LLONG_MAX;
    std::vector<std::vector<int> > list;
    for(unsigned int i = 0; i < 3; i++) {
      int start_x, start_y, end_x, end_y;
      parse_teleport(&start_x, &start_y, &end_x, &end_y, &teleports[i]);
      std::vector<int> temp;
      temp.push_back(start_x);
      temp.push_back(start_y);
      temp.push_back(end_x);
      temp.push_back(end_y);
      list.push_back(temp);
      temp.clear();
      temp.push_back(end_x);
      temp.push_back(end_y);
      temp.push_back(start_x);
      temp.push_back(start_y);
      list.push_back(temp);
    }
    ret = std::min(ret, static_cast<long long int>(point_point(xMe, yMe, xHome, yHome)));
    for(unsigned int i = 0; i < 6; i++) {
      ret = std::min(ret, static_cast<long long int>(point_teleport(xMe, yMe, &list[i])) + 10 + teleport_point(&list[i], xHome, yHome));
    }
    for(unsigned int i = 0; i < 6; i++) {
      for(unsigned int l = 0; l < 6; l++) {
        if(i == l) {
          continue;
        }
        ret = std::min(ret, static_cast<long long int>(point_teleport(xMe, yMe, &list[i])) + 10
          + teleport_teleport(&list[i], &list[l]) + 10
          + teleport_point(&list[l], xHome, yHome));
      }
    }
    for(unsigned int i = 0; i < 6; i++) {
      for(unsigned int l = 0; l < 6; l++) {
        if(i == l) {
          continue;
        }
        for(unsigned int j = 0; j < 6; j++) {
          if(i == j || l == j) {
            continue;
          }
          ret = std::min(ret, static_cast<long long int>(point_teleport(xMe, yMe, &list[i])) + 10
            + teleport_teleport(&list[i], &list[l]) + 10
            + teleport_teleport(&list[l], &list[j]) + 10
            + teleport_point(&list[j], xHome, yHome));
        }
      }
    }
    return ret;
  }
protected:
  void parse_teleport(int *start_x, int *start_y, int *end_x, int *end_y, std::string *teleport) {
    sscanf(teleport->c_str(), "%d %d %d %d", start_x, start_y, end_x, end_y);
  }
  int point_teleport(int x, int y, std::vector<int> *teleport) {
    return point_point(x, y, (*teleport)[0], (*teleport)[1]);
  }
  int teleport_teleport(std::vector<int> *start_teleport, std::vector<int> *end_teleport) {
    return point_teleport((*start_teleport)[2], (*start_teleport)[3], end_teleport);
  }
  int teleport_point(std::vector<int> *teleport, int x, int y) {
    return point_point((*teleport)[2], (*teleport)[3], x, y);
  }
  int point_point(int start_x, int start_y, int end_x, int end_y) {
    const int move_x = std::abs(start_x - end_x);
    const int move_y = std::abs(start_y - end_y);
    return move_x + move_y;
  }
};

テレポートは入口換算でも6か所しかないのと、同じテレポートを使うことは無意味なので最大でも3回しかテレポートしない事がわかります。
またテレポートを使用しない移動時間は単純計算一回で導き出せます。
以上の理由により、総当たりでもテレポートなし(1種)、1度テレポート(6種)、2度テレポート(6*6=32種)、3度テレポート(6*6*6=216種)の合計255パターンを網羅するだけで最小値を出すことが可能だとわかります。
このパターン数ならばまずどんな入力でもTLE(Time Limit Exceeded)することはないため、あとは適当に計算してやるだけで解くことができます。
(上のコード中では若干パターン数を減らす処理が入っていますが、TLEする恐れがないのにタイプ数を増やしてまで計算量を減らすのは愚の骨頂です、マネしないように)
他の人も書き方の違いこそあれ、大体同じ方法で解いていました。

チャレンジの狙い目はオーバーフローです。
返り値はINTであり、実際どんなinputでもINT_MAXを超える値が返ることはありませんが、総当たりをしている場合は計算中に超えてしまうことがあります。
単純にマイナスになるパターンはサンプルに存在するため大体対策されていますが、マイナスを超えて1以上の数値までオーバーフローした場合の対策が抜けている人が多くいました。
(おそらくこのひっかけこそが600点という高得点問題である理由でしょう)
自分もこの点に気づき撃墜できる人物を絞り込むところまではいきましたが、うまい具合に対策を潜り抜けるテストケースを作っている間に時間切れで↓。
ちなみに、自分のコードではlong long intを使うことで回避しています。

BinaryCards:DIV2ハード900点問題

元問題:http://community.topcoder.com/stat?c=problem_statement&pm=11552
概要:(意訳)2^0=1,2^1=2,2^2=4,2^3=8…2^63までの数値が書かれているカードがあり、表になっているカードの数値合計の初期値をA、そこから最小手数で、なおかつ場の数値合計が最も大きくなるようにカードを裏返してA+1,A+2,A+3…Bと数値を作っていったとき、最も大きくなった場の数値を返せ。


#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <limits.h>

#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <iterator>
#include <numeric>
#include <functional>
#include <algorithm>
#include <utility>


class BinaryCards {
public:
	long long largestNumber(long long A, long long B) {
		if(A == B) {
			return A;
		}
#define START_VALUE 0x0800000000000000LL
		long long int value = 0;
		for(long long int n = START_VALUE; ; n /= 2) {
			if(n > B) {
				continue;
			}
			if(n <= A) {
				A -= n;
				B -= n;
				value += n;
				n = START_VALUE * 2;
				continue;
			}
			return value + n*2-1;
		}
		return 0;
	}
protected:
};

(※上記のコードはSRM終了後にコーディングした物です)
初期値をなしに考えると2^x-1の数値から2^xの数値を作る際に(2^x)*2-1という最も大きな数値が現れます。
(例えば場7から8を作るとき、場の3枚全てを裏にし8を表にするため、最初に8を表にすれば15が作れます)
また、場2^x+y-1から2^x+y(xは取り得る限り最大の値)を作るときの最大数は、y-1からyを作るときの最大数+2^xである事もわかります。
なので、A<=2^x-1最後に

実際の戦績
室内順位2位/18人、Div2順位134位/950人、レート964->1036と上々の結果です。

前回に続き今回もミディアムが簡単すぎて逆に怖いぐらいでしたが、オーバーフローで落ちる人続出して納得。
サンプルでオーバーフローしていたにもかかわらずifだけで回避しようとする人が多い当たり、競技プログラミングには意外とlong long intを使用する文化はないのかもしれません。
4連続でレートUPしているため、そろそろ苦手な「数学の公式を使わないとTLEする問題」が出てきそうでビクビク。
次回は出られるかわかりませんが、出れたら同じようにレポートを上げる予定です。

2011 年 9 月 17 日

xrea広告でwordpressに不具合が発生する理由

Filed under: 未分類 — 中の人 @ 8:34 PM

無料版xreaサーバーにwordpressを設置すると管理画面において様々な不具合に遭遇します。
ですが、その件について調べても回避方法ばかりで、原因については”広告が原因らしい”以上の事がわかりませんでした。

“動けばそれでいい”は主義に反するので、きちんと調べてみましょう。
直し方を知りたいだけの方は他のサイト様をご覧ください。
なお、以降の記述はwordpress3.2.1-jaをPHP5.2.5がインストールされているXREA無料サーバーの自動広告挿入をONの上で動かした場合の物となります。


問題を正確に把握する

まずは起きている問題を正確に把握しましょう。

管理ページはどこも以下のように表示が乱れています。

どうやらスタイルシートがおかしいようなので、片っ端からソースを覗いてみます。
するとwp-admin/load-styles.php(パラメーターは省略)の中身が

このようにバイナリファイルをテキストエディタで開いたかのようになっています。
また、Content-Typeもtext/htmlとなっており(text/cssでなければいけない)、明らかに動作がおかしいことがわかります。

さらに、管理画面の外観->ウィジェット(このブログでいう右側のメニューなどを編集する機能です)では、本来D&D出来るはずの項目が全く反応しません。
今度はjavascriptが怪しいのでソースから探してみると、wp-admin/load-scripts.php(パラメーターは省略)がCSSの時と同様に化けていました。
Content-Typeも同様にtext/htmlになっていました(application/x-javascript; charset=UTF-8が正しい)。
※javascriptは色々難しい事情があり、上記のapplication/x-javascriptは見方によっては正しくないこともありますが、今回は関係ないので割愛。

ざっと調べた範囲ですが、どうやらこの二点が主な問題点のようです。

本当に原因は広告なのか

.htaccessにLayoutIgnoreURI *と記述して自動広告挿入をOFFにし、本当に治るのか確かめてみます。
すると、確かに文字化けせずContent-Typeも正常化したことがわかります。

しかし、自動広告挿入がONであってもCSSやjavascriptは広告挿入対象ではありません。
一体何が起こっているのでしょう?

xreaの広告挿入処理をハック

ハックはハックでも「調べる、解析する」の方で、クラッキング(破壊する、損害を負わせる)という意味ではありません、念のため。

ためしに「//test」の一行をjavascriptとして返すphpを作って広告の挙動を試してみます。
※実際に試したコード


<php
header('Content-Type: application/x-javascript; charset=UTF-8');
echo "//test";
exit;

すると、1行目に謎の空行が挿入されていました。
また、Content-Typeもtext/htmlになっています。
もちろん自動広告挿入がOFFだと正常動作、ますます謎です。

なぜこのようなことが起きるのでしょうか?
どうやらheader命令よりも前に空行が出力されているのが原因のようでした。
実際phpのマニュアル(http://php.net/manual/ja/function.header.php)にて

header() 関数は、 通常の HTML タグまたは PHP からの出力にかかわらず、すべての実際の 出力の前にコールする必要があることです。

と説明されています。

おそらく、自動広告挿入がONであれば必ず1行は挿入される処理なのでしょう。
そしてPHPでは(自分が知っている範囲では)Content-Typeを変更する方法はheader関数以外にないので、それが原因でPHPのデフォルトであるtext/htmlになってしまうこともわかりました。

ですが、これだけだと本来テキストであるはずの出力が化けている理由がわかりません。
今度はまた別方面から調べてみましょう。

テキストが化ける理由を探す

まずheader関数が失敗するらしいことはわかったので、広告自動挿入ONとOFFで来ているhttpヘッダーを比べてみます。
すると、自動広告挿入がOFFの時だけ「Content-Encoding: deflate」が返っていることがわかります。

ためしにload-styles.phpとload-scripts.phpを覗いてみると、最後の方にある


		header('Content-Encoding: deflate');
		$out = gzdeflate( $out, 3 );

というコードでテキストを圧縮していることがわかりました。

どうやらブラウザが対応している場合は圧縮して返すが、header関数が失敗してしまうため、ブラウザはテキストだと勘違いしてそのまま使うために化けているようです。
実際、この圧縮処理を丸々コメントアウトしてみたところ、広告挿入処理がONであってもきちんとテキストは出力されるようになりました。
(※正確には、PHPはContent-Typeによってechoやprintの処理を分岐しているため、ブラウザに送信する以前から破損データとなっています)

まとめ

・自動広告挿入がONだと、たとえどんな内容でも空行が挿入される(xrea広告自動挿入機能の弊害)
・たとえ空行だろうと1行でも出力されるとheader関数が失敗する(PHPの動作仕様)
・header関数でContent-TypeとContent-Encodingを設定しているため、これらが失敗することで不具合が発生している

ちなみにload-*.php側の修正だけで完全に回避することはできません
(どうやってもContent-Typeを設定する方法がないため)
ここまで延々調べましたが、結局LayoutIgnoreURIで広告を解除するのが一番妥当な回避策となります。

要するにPHP使うならサーバー代金ぐらい払おう、というお話でした。

2011 年 9 月 11 日

情報の外部発信をがんばれと言われたので

Filed under: 未分類 — 中の人 @ 5:41 AM

ブログを公開設定に戻してみるテスト。

アドレスは前と違うが、まぁ別に問題はなかろう。

特訓の成果

Filed under: 未分類 — 中の人 @ 4:36 AM

継続して3km程度のランニング可。
腕を胸に組んでの腹筋運動最高連続22回達成。
腕立て伏せはいまだやり方すらわからない。

後わかったこととして、筋肉痛とはまた別の継続疲労みたいなものが存在する。
今現在、ランニング3km一回では筋肉痛は出なくなった、けれど足にダルさのようなものが1~2日程度出て、揉むと気持ちいい感じになる。
今思い返してみると、筋肉痛が酷いから動けないと思っていた日も、動かない理由の大半はこの倦怠感が原因だった気がする。

ので、会社復帰した後は運動するにしても3km走るのはまずい。
引っ越しなどで忙しくはあるが、復帰後も体力作りに励むつもりなので、この期間中に継続疲労が出ないギリギリの運動量を調べないとね。

Powered by WordPress