第20回
先日、「オフラインリアルタイムどう書く」が開催されました。今回で20回目でした。コンスタントに優良なお題と、みんなで集まって解くという場を提供され続けていることに尊敬と感謝の念を抱くばかりです。
…。
とはいえ、いまだにオフラインリアルタイムで参加せずに、オンラインで非同期に問題を解くという開催の主旨に真っ向勝負なことをしているわけですが（苦笑）。
今回のお題。
オーソドックスな解き方としては、各人の毎分の状態を真偽値で持ち、その状態を重ね合わせて条件にあう状態が指定された期間連続する箇所を特定する、というのがあります。
そのアイディアで解いてみたものがこれ。
再挑戦
解いてはみたものの、なんとなく面白味に欠けるという理由で別解を探していたところ。
虎塚さんが書かれたブログのエントリの、
あらかじめ人数分の配列を作るのではなく、走査を1回だけにして、あるタイミング（分）ごとに、「お前今ヒマ？」と全員に確認するメソッド（おまひまメソッド）を作るとよいかもしれません。
という記述を見て、このアイディアで解けないか試みてみました。
その結果がこちら。
書きなぐったコードで半年もすると解読不能になりそうなので、主に未来の自分のために、書き直したコードと解説を書いておきます。
スケジュールの作り方
文字列から予定を読み出すところまでは基本的に同じです。
読み出した予定を記憶する部分で少し工夫しました。
予定の時刻というのは、予定が入っている人の状態を変えるタイミングになります。最初のアイディアでは１日分の状態をビット列に展開していましたが、これを状態が変わるタイミングだけを記憶するようにします。
次の図で言うと{ 1002 => 1, 1008 => 1 }だけを記憶しておきます。
初期状態を0として、カウントアップするごとにscheduleの値とxorをとります（scheduleに値が格納されていない場合は0とします）。xorをとったあとの値が、そのときの状態になります。
人数が増えたばあいは人数分のビット列を用意して、演算を1ビットのxorから人数分ビットのビット列のxorに変えればよいので演算の回数は増えずにすみます。
状態の変化で記憶しているので、開始時刻と終了時刻を区別する必要がないため、格納する情報を減らすことができます。
実装上の工夫として、予定を格納するときもxorを使って格納しています。こうすることで前の予定の終了時刻と次の予定の開始時刻が重なったばあいに対処しています（前の予定が終わる前に次の予定が始まるということが往々にしてありますが、そういう場合は考慮していないです）。
加えて、10時以前の予定はすべて10時によせるようにしています。これによって10時以降の状態だけを調べればよいことになります。開始終了とも10時以前のばあいにどちらも10時によせられてしまいますが、上記のようにxorをとって格納しているので、開始終了が同時刻のばあいには記録されないことになります。
会議時間を見つける
あとは初期状態を与えて、時間ごとに予定で更新し、「お前今ヒマ？」と全員に訊いて回り、連続して全員がヒマと答えた回数が指定した回数になったら、全員がヒマと答え始めた時刻（と指定回数に達した時刻）を出力すればよいことになります。
このとき、座間川さんだけ初期状態を反転しておくことで、ほかの人と同じように扱うことができるようになります。
全員がヒマかどうかを調べるには、全員の状態のビットが0のときを探せばよいことになります（座間川さんは初期状態を反転しているので、0のときが忙しいとき、つまりほかの人にとって都合のよいときになります）。
状態をビット列として整数値として扱えば、数値として0のときを判定すればよいことになります。
印旛沼さんと陣場山さんの状態はどちらかが0になっていればよいので、それぞれのビットをマスクした上でそれぞれ値を調べます。
コードにしてみる
C++でコードにした結果です。
#include <iostream> #include <sstream> #include <iomanip> #include <string> #include <map> static const int A = 1 << 0; static const int B = 1 << 1; static const int I = 1 << 2; static const int J = 1 << 3; static const int Z = 1 << 4; inline int charToPerson(char c) { static const std::string person("ABIJZ"); return (1 << person.find(c)); } inline int toMin(int hm) { return (hm / 100) * 60 + (hm % 100); } inline int toHourMin(int min) { return (min / 60) * 100 + (min % 60); } std::map<int, int> read(const std::string& source) { std::map<int, int> schedule; std::istringstream iss(source); while(iss.good()) { char c; char separator; int head; int tail; iss >> c >> head >> separator >> tail; int person = charToPerson(c); schedule[toMin(std::max(head, 1000))] ^= person; schedule[toMin(std::max(tail, 1000))] ^= person; iss >> separator; } return schedule; } void write(int start_time, const std::string& expected) { std::ostringstream oss; if(start_time) { oss << toHourMin(start_time) << "-" << toHourMin(start_time + 60); } else { oss << "-"; } std::string actual = oss.str(); std::string result = (expected == actual) ? "o" : "x"; std::cout << "expected: " << expected << ", actual: " << actual << ", result: " << result << std::endl; } int search(std::map<int, int>& schedule) { int count_i = 0; int count_j = 0; int status = Z; for(int i = toMin(1000); i < toMin(1800); ++i) { status ^= schedule[i]; count_i = ((status & ~J) == 0) ? (count_i + 1) : 0; count_j = ((status & ~I) == 0) ? (count_j + 1) : 0; if((count_i == 60) || (count_j == 60)) { return i - 59; } } return 0; } void test(const std::string& source, const std::string& expected) { std::map<int, int> schedule = read(source); int start_time = search(schedule); write(start_time, expected); } int main(int argc, char* argv[]) { /*0*/ test( "A1050-1130,B1400-1415,I1000-1400,I1600-1800,J1100-1745,Z1400-1421,Z1425-1800", "1425-1525" ); // 以下テストパタン、略 return 0; }
いつか読むはずっと読まない：人生はサーフィンのように
竹内義晴さんのITmedia エンタープライズの連載「人生はサーフィンのように」を元にした電子書籍です（くわしくはこちらへ）。
実は思い入れのある連載です。
ちょうどこれらの記事が連載されていた時期に、荒波にもまれていたところでした。これらの記事でずいぶん勇気づけられたのを覚えています。その後竹内さんとはセミナーで機会があって知り合いになることができました。
結局この年の秋には荒波に抗えず難破状態になりましたが、このとき復帰に向けて手を貸して頂いたのも竹内さんでした。
それから１年半ほどがたった今。
今も荒波の渦中にあります。ただ当時のようにもまれるのでなく、ヘタながらも波に乗れる（少なくとも乗る努力ができる）ようになったような気がします。
