cacahuatl のあっちこっち

2015年6月11日木曜日

Tomcat7 とRFC違反のCookie

業務の都合で、Tomcat7でRFC違反のCookieを発行しなければならなくなった。
具体的には、値に"="を含むCookieをダブルクォートで囲まずに発行せよ、とのことである。

通常、TomcatのサーブレットはHttpServletResponseに定義されたaddCookieメソッドを用いる。
但し厳密にはHttpServletResponseはInterfaceであるから、通常はこれを実装したorg.apache.catalina.connector.Responseを用いる。

Tomcatでは通常RFCに従い、=を含むCookieが許可されることはなく、ダブルクォーテーションによって囲まれる。
これを嫌い、ダブルクォートで囲まれないようにするための実装について記す。

Tomcat 7 では(Tomcat HOME)/conf/catalina.propertiesに記載された設定値によって、Responseにて発行するCookieに以下のように制約が生じる。

パターン①
org.apache.tomcat.util.http.ServerCookie.ALLOW_HTTP_SEPARATORS_IN_V0がtrueの場合

　　→',', ';', ' ', '\t'が含まれている場合ダブルクォートで囲う

パターン②
org.apache.tomcat.util.http.ServerCookie.ALLOW_HTTP_SEPARATORS_IN_V0がfalseかつ
org.apache.tomcat.util.http.ServerCookie.FWD_SLASH_IS_SEPARATORがfalseの場合

　　→ '\t', ' ', '\"', '(', ')', ',',':', ';', '<', '=', '>', '?', '@', '[', '\\', ']', '{', '}'が含まれている場合ダブルクォートで囲う

パターン③
org.apache.tomcat.util.http.ServerCookie.ALLOW_HTTP_SEPARATORS_IN_V0がfalseかつ
org.apache.tomcat.util.http.ServerCookie.FWD_SLASH_IS_SEPARATORがtrueの場合

　　→パターン②に加え、'/'が含まれている場合にはダブルクォートで囲う。

従って、Tomcat 7系では"="に限らず、主要なセパレータを含む値をCookieにセットしたい場合、org.apache.tomcat.util.http.ServerCookie.ALLOW_HTTP_SEPARATORS_IN_V0をtrueにセットすることで目的を達成することが出来る。

私が参考にしたのはTomcat Ver 7.0.47のソースコードであるが、恐らく7系ではこの制約は同じものと思われる。
細かいマイナーバージョンでの動作を確認したい場合は、各自ソースコードを参照されたし。

なお、Tomcat v6やv8のソースコードは読んでいないため、仕様が本記事と異なる可能性がある。

私も技術的には非常に未熟であるため、誤っている点があれば是非ご教示頂きたい。

2012年3月28日水曜日

コミュニケーションは誤解を解くことが肝要

最近色んな人と喋っていて気付いたのだけれど、コミュニケーションを円滑に進めるためには、「いかに早期に誤解を解くか」が肝要なんだと気付いた。

前提を間違えた結論は全て偽

論理学において、前提が偽であるならば、結論は常に真だけど、現実においてこれは誤りで、現実では前提が異なっているならば、得られた結論は全てニセモノであると考えるのが正しい。

他人と議論を進める場合、前提を確認した後、議論を展開していくのだけれど、前提を間違えて議論を展開した場合、殆どの場合結論は合致しないのだけれど、稀に合致したとして、それは合致とは言えない。だって前提条件が違うんだから。

例えば、「TPPは推進するべき」という結論で合致したとして、片方が「日本の農業は強い、だから開放しても安心だ」という前提に立っていて、片方が「日本の農業は弱い、だが更に手厚い補償をするので安心だ」という前提に立っていたとすると、結論は同じでも、思考の過程が全く違ったものになる。

簡単な議論ならいいけど、複雑な議論になるにつれ、前提が違っているとなると、意味が無かったものになるコミュニケーションの量が膨大になる。早い段階で軌道修正を行わないと、進めていったところで、やっぱり前提が違いましたね、戻りましょう、となると、それは膨大な時間の消費になる。

では、どうやって議論の道筋が正しい、つまり誤解の無いことを確認すればよいのか。

理解は自分自身の言葉によってしか生まれない

「レジデント初期研修用資料～～医療とコミュニケーションについて～～」という書籍に、以下のような記述が存在する。以下引用する。

理解というものは、最終的に「主治医から押し付けられた見解の型枠を、自分の言葉で満たす」作業として完成する。 資料「レジデント初期研修用資料～～医療とコミュニケーションについて～～」58頁

これは医療の現場以外にも通じると僕は考えていて、これは一般化すると「聞き手の理解は『話者によって話された内容を、聞き手の言葉で満たす』という作業として完成する」こととなる。
話された後、「分かった」「なるほど」で終わってしまう人ほど、何にも理解していなくて、「それはつまり～～ということですか？」「要するに～～ということですか？」と返し、了解が得られた時は、かなりの確率で安心出来る。
なので、区切りの良い所で、相手に理解した内容を語ってもらうのが、恐らく一番良い策になる。
もっと言えば、あえて質問が起こるように、説明をやや舌足らずにするのが、意外にも良策であるのかもしれない。
分かり易い説明は、質問の必要性を奪ってしまうから。

現実の運用

しかしこれを現実の世界に適用するとなると、また勝手が違う。

このような慎重なコミュニケーションが必要な状況というのは、顧客への説明だとか、上司への報告だとかになるが、基本的に社会人は時間がない。ぐだぐだと舌足らずな説明を行い、質問させようとすると、途端に無能の烙印を押され、二度と会話してくれなくなること請け合いである。

現実的な運用方法としては、誤解がなされていると思った段階で説明を加えつつ、話の最後に、箇条書きのような調子で確認し、念の押す、といったところが関の山だろう。
ここで重要なことは主張のコンポーネント化になる。
自分の言いたいことを、「前提」「思考過程１～ｎ」「結論」というピースに分け、箇条書き形式にすることで、聞き手の理解をスムーズにする。

長々と書いてみたけれど、やっぱり、頭の中で考えたことを現実に適用するのは難しいな、という結論に至った。
現実の運用についてはもう少し追記したいこともあるのだけれど、それはまた今度の話。

2012年1月17日火曜日

TopCoder 529 過去問

卒論が終わりました。CS関連に全力注入出来るのがうれしいです。早速SRM 529 の過去問を解きました。

今回から、やるだけの問題は載せません。面白くないので。

Div2 Hard

MinskyMistery Div2

マーブルに関するゲームを行うというもの。
ゲームの詳細を書くのは面倒くさいので割愛。
この問題は、与えられたN(>=2)に関する約数のうち、１を除く最小のものと最大のものを足したものを出力する問題に帰着出来る。ちなみに素数の場合は例外で、自身と1を足したものを返す。
N<2の時はループが終了しない。
なので気付いてしまえば瞬殺。

コード

#include <algorithm>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <string>
#include <vector>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <stack>
#include <deque>
#include <queue>
#include <functional>
 
using namespace std;
 
#define REP(i,s,e) for (int i = int(s); i != int(e); i++)
#define rep(i,e) REP(i,0,e)
#define foreach(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ALL(c) ((c).begin(), (c).end())
#define ll long long
#define VI vector<int>
 
class MinskyMysteryDiv2 {
 
 public:
 
 long long computeAnswer(long long N) {
  if(N < 2) return -1;
  for(ll i = 2;i*i <= N;i++) if(N%i == 0) return i + N/i;
  return N+1;
 }
 
};

2011年12月15日木曜日

TopCoder SRM 525 過去問

TopCoder SRM 525 Div2 Easy と Medium を解きました。

Easy

幅2マス、長さNマスの道がある。マス目は、濡れている場合と乾いている場合がある。
左上からスタートし、右上まで、濡れたマスを通らないように移動したい。
移動は、縦、横、斜めが可能。
可能な場合はYESを、不可能な場合はNOを出力せよ。

解法

まぁ、やるだけです。

提出コード

#include <algorithm>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <string>
#include <vector>
#include <cstdio>
#include <functional>
#include <numeric>
 
using namespace std;
 
#define REP(i,s,e) for (int i = int(s); i != int(e); i++)
#define rep(i,e) REP(i,0,e)
#define foreach(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ALL(c) (c).begin(), (c).end()
 
class RainyRoad {
 
 public: string isReachable(vector<string> road) {
  rep(i,road[0].length()) if(road[0][i] == 'W' && road[1][i] == 'W') return "NO";
  return "YES";
 }
 
};

Medium

長方形の上にコインが幾つか乗っている。
プレイヤーは一回につき、上下右左を選び、全てのコインをその方向に動かしてよい。
この操作によって、与えられた長方形からコインがはみ出た場合、コインは落ちて消える。
コインがK枚になるような最小の操作回数を出力せよ。なお、K枚に出来ない場合は-1を出力せよ。

解法

操作を何回行っても、残るのは長方形になる。(或いは何も残らない。。。)
部分長方形を考え、その長方形に対して何枚コインが残るかが分かれば、最小の命令回数は一意に定まる。
例えば、下の行を1つ、上の行を2つ削るような部分長方形を作る場合、下、上、上、上となり、命令回数は四回である。
下と上の順番を逆にしてしまうと、上、上、下、下、下となり、5回となってしまう。
反対側の辺も削るような長方形を作る場合、順番に注意。

提出コード

#include <algorithm>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <string>
#include <vector>
#include <cstdio>
#include <functional>
#include <numeric>
 
using namespace std;
 
#define REP(i,s,e) for (int i = int(s); i != int(e); i++)
#define rep(i,e) REP(i,0,e)
#define foreach(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ALL(c) (c).begin(), (c).end()
 
 
int cum[51][51];
 
class DropCoins {
 
 public: int getMinimum(vector<string> board, int K) {
  int width = board[0].length();
  int height = board.size();
  int ans = -1;
  memset(cum,0,sizeof(cum));
  REP(i,1,height+1) REP(j,1,width+1){
   cum[i][j] = cum[i-1][j] + cum[i][j-1] - cum[i-1][j-1] + (board[i-1][j-1] == 'o');
  }
  rep(y,height) rep(x,width) REP(y2,y,height+1) REP(x2,x,width){
   int coins = cum[y2+1][x2+1] - cum[y2+1][x] - cum[y][x2+1] + cum[y][x];
   if(coins == K){
    int up = y, left = x, down = height - y2 - 1, right = width - x2 - 1;
    int move = 2*min(up,down) + max(up,down) + 2*min(left,right) + max(left,right);
    if(ans == -1 || ans > move){
     ans = move;
    }
   }
  }
  return ans;
 
 }
 
};

最近サボりがひどく、いざTopCoderを開いてもついついTwitterを見に行くなどしてしまっていたため、ニコ生で放送しつつ解くということを試しにやってみた。
すると、なんと放送初回から@chokudai 先生が視聴するというミラクルが発生。これにはおいらもびっくり。もっとも、放送している時は全然気付かなかったし、@chokudai 師匠のありがたいアドバイスも勘違いしていて迷走していたのだが(笑)

次はCodeForcesが近いので、久しぶりに出るつもり。

TopCoder SRM 526 過去問

SRM526 の Div2 Easy Medium を解きました。

Easy

ABC三種類の文字からなる文字列が存在する。
先頭からi文字目以降に何種類の文字があるかを格納したvectorを返す。

解法

ケツからみていくだけです。

提出コード

#include <algorithm>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <string>
#include <vector>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <stack>
#include <deque>
#include <queue>
#include <functional>
 
using namespace std;
 
#define REP(i,s,e) for (int i = int(s); i != int(e); i++)
#define rep(i,e) REP(i,0,e)
#define foreach(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ALL(c) ((c).begin(), (c).end())
#define ll long long
#define VI vector<int>
 
class CheatingQuiz {
 
    public: vector<int> howMany(string answers) {
        int count = 0;
        bool abc[3];
        memset(abc,false,sizeof(abc));
        vector<int> ans;
        for(int i = answers.length()-1; i >= 0;i--){
            if(count == 3){
                ans.push_back(3);
                continue;
            }
            switch(answers[i]){
            case 'A':
                if(!abc[0]){
                    abc[0] = true;
                    count++;
                }
                break;
 
            case 'B':
                if(!abc[1]){
                    abc[1] = true;
                    count++;
                }
                break;
 
            case 'C':
                if(!abc[2]){
                    abc[2] = true;
                    count++;
                }
                break;
            }
            ans.push_back(count);
        }
        reverse( ans.begin(), ans.end() );
        return ans;
    }
 
};

Medium

n行m列の行列がある。
各行、各列ごとに最大１羽、アヒルが居る。
アヒルを移動させて、縦でも横でもいいから整列させたい。
アヒルは、移動先が空いていればどこへでも移動が可能で、移動にかかる時間はハミルトン距離によって算出される。
整列するのにかかる最小の時間を求めよ。

解法

どういう整列のさせ方をするかが決まれば、その整列の実現にかかる最小の時間は一意に定まる。
よって、全通り試して最小の時間を返せばよい。
より具体的には、例えば横に並べる場合、最も左に居るアヒルを列の最も左に移動させ、そのアヒルの次に最も左に居るアヒルをその右へ移動させ。。。と整列させる。
縦に並べる場合も同じである。
この整列のさせ方が最小の時間を取ることは、図を書けば直ちに分かる。
実装では、二次元の構造体にアヒルの位置を記憶させ、vectorにしまったのち、xとyそれぞれに対してバブルソートを行わせる関数を実装して対処した。

提出コード

#include <algorithm>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <string>
#include <vector>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <stack>
#include <deque>
#include <queue>
#include <functional>
 
using namespace std;
 
#define REP(i,s,e) for (int i = int(s); i < int(e); i++)
#define rep(i,e) REP(i,0,e)
#define foreach(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ALL(c) (c).begin(), (c).end()
#define ll long long
#define VI vector<int>
#define INF 1<<30
 
typedef struct pos{
    int x;
    int y;
 
    int hamiltone_distance(int _x, int _y){
        return (abs(x - _x) + abs(y - _y));
    }
};
 
void sort_column(vector<pos>& s){
    bool recursive = false;
    REP(i,1,s.size()){
        if(s[i-1].y > s[i].y){
            swap(s[i],s[i-1]);
            recursive = true;
        }
    }
    if(recursive) sort_column(s);
}
 
void sort_row(vector<pos>& s){
    bool recursive = false;
    REP(i,1,s.size()){
        if(s[i-1].x > s[i].x){
            swap(s[i],s[i-1]);
            recursive = true;
        }
    }
    if(recursive) sort_column(s);
}
 
class DucksAlignment {
 
    public: int minimumTime(vector<string> grid) {
        int ans = INF;
        int column = grid.size();
        int row = grid[0].length();
        vector<pos> ret;
        rep(i,column) rep(j,row){
            if(grid[i][j] == 'o'){
                pos tmp = {j,i};
                ret.push_back(tmp);
            }
        }
        int sum;
        sort_row(ret);
        rep(i,column) rep(j,row-ret.size()+1){
            sum = 0;
            rep(k,ret.size()) sum += ret[k].hamiltone_distance(j+k,i);
            ans = min(sum,ans);
        }
        swap(column,row);
        sort_column(ret);
        rep(i,column) rep(j,row-ret.size()+1){
            sum = 0;
            rep(k,ret.size()) sum += ret[k].hamiltone_distance(i,j+k);
            ans = min(sum,ans);
        }
        return ans;
    }
};

2011年12月7日水曜日

何故エンジニアを適正に評価出来ない会社に務めてはいけないのか。経済学的に考察する

このエントリはCompetitive Programming Advent Calendar(Day7)用に書かれたものです。

みなさんこんにちは、cacahuatlと申します。
競技プログラミングクラスタのAdvent Calendarですが、私はそんなに実力が高くないし、技術的なことも、他の方々に比べると正直ひよっこ以下です。

なので、私の経済学部出身という地の利(?)を利用して、ちょっと変わった記事を書くことにしました。

たびたび、エンジニアを適正に評価出来ない会社に勤めてはいけないという話を聞きます。
これは何故でしょうか？直感的には合っているような気がしますが、本当でしょうか？
このエントリでは、上記の、「何故エンジニアは自身を適正に評価出来ない会社に勤めてはいけないのか」という問題を経済学的に考察していきたいと思います。

注意：筆者は経済学に関して素人です。経済学者様などにドヤ顔でこの話をするとフルボッコにされる可能性があるため、注意して下さい。

考察するにあたり、現実を単純化した「モデル」を考えます。シムシティやシムズを想像してくれると早いかと思います。

この世界では、エンジニアを雇う企業は２つしかありません。一つは、エンジニアの能力を適切に評価出来る企業。もう一つは、エンジニアの能力を全く評価出来ない企業です。
この世界では、どちらの企業も常に人材が不足していて、エンジニアの求人を常に出しています。どちらの企業も、自分が適正だと思った報酬以上の額をエンジニアに支払うことはありません。

「何だか現実の世界と随分違うなぁ。。。」そう思った貴方。はい、その通りです。しかし、

　　　　　　　　　　　　／）
　　　　　　　　　　　／／／）
　　　　　　　　　／,.=ﾞ''"／
　　　／　　　　 i f　,.r='"-‐'つ＿＿＿_　　　こまけぇこたぁいいんだよ！！
　　/　　　　　 /　　　_,.-‐'~／⌒　　⌒＼
　　　　／　　,i　　　,二ﾆ⊃（ ●）.　（●）＼
　　　/　　　ﾉ　　　 ilﾞフ::::::⌒（__人__）⌒::::: ＼
　　　　　　,ｲ｢ﾄ､　　,!,!|　　　　　|r┬-|　　　　　|
　　　　　/　iﾄヾヽ_/ｨ"＼　　　 `ー'´ 　　／

現実を精密に再現する必要は無いのです。現実を単純化し、現実の世界を理解する手がかりを掴めれば、それだけで素晴らしいことであるとは思いませんか？

この不思議な世界では、エンジニアは自分の能力が分かっています。ですから当然、自分の能力に対する適正な報酬も分かっています。
企業も同じです。エンジニアを適切に評価出来る企業は、適正報酬が分かっていますし、そうでない企業は、適正報酬も分かりません。

エンジニアを適切に評価出来る企業は、その人材に対してどのくらい払えばいいのか分かっていますから、面接に来た人に対して、その報酬を提示すればいいですよね。
でも、そうでない企業の場合、どうすればいいのでしょう？

。。。と、いうところで。
これはCompetitibe Programming Advent Calendarであることを思い出して。
今回は、競技プログラミング風に、問題を解くことで考えてみましょう。

Div2 Easy 250

Adverse Selection

貴方はエンジニアの能力を適正に評価することの出来ない会社の採用担当をしています。
貴方の会社に雇われる可能性があるエンジニアの能力が、abillityとして与えられます。
エンジニアは、自身のabillityを下回る報酬を提示する会社に雇用されることはなく、常に自分のabillity以上の報酬を支払う会社に雇用されようとします。
貴方の会社はエンジニアを適正に評価することが出来ないため、エンジニアへの報酬として、貴方の会社に雇われる可能性のあるエンジニア達の能力の平均を提示します。
平均は常に整数で、小数点以下は切り捨てられます。
初期状態では、全エンジニアが雇われる可能性のあるものとします。

最終的に貴方の会社にくる可能性があるエンジニア達の能力を返しなさい。

Class :                      Company
Method:                   adverseSelection
Parameters:              vector<int>
Returns:                   vector<int>
Method signature:    vector<int> adverseSelection(vector<int> abillity)

この問題は再帰関数で愚直にシミュレーションを行うことで解けそうです。
実装してみましょう。

#include <vector>
 
using namespace std;
 
#define REP(i,s,e) for (int i = int(s); i != int(e); i++)
#define rep(i,e) REP(i,0,e)
#define foreach(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
 
class Company{
public:
 // 平均を計算するヘルパ関数
 int mean(vector<int> ability){
  int sum = 0;
  foreach(iter,ability) sum += *iter;
  return sum/(int)ability.size();
 }
 
 vector<int> solve(vector<int> ability,int numPeople){
  int reward = mean(ability);
   
  /* 自分の能力より報酬が低ければくる可能性はない。 */
  foreach(iter,ability) if(*iter > reward){ ability.erase(iter); iter--;} 
 
  /* 来社する可能性があるエンジニアの数が減少していれば、平均が変わるため、再帰する。 */
  return ((int)ability.size() == numPeople)? ability:solve(ability, (int)ability.size());
 }
 
 vector<int> adverseSelection(vector<int> ability){
  // 再帰一発。
  return solve(ability, (int)ability.size());
 }
};

この解答を実行すると分かりますが、最終的に会社に来る可能性のあるエンジニアは、常に能力の最も低いエンジニアとなり、報酬も最低値を取ります。

何故こうなるのか？

初期状態では、全エンジニアは雇われる可能性があります。
これらの平均を報酬として提示すると、平均より高い実力を持ったエンジニア達は「うわっ、私の年収、低すぎ・・・？」となり、雇われようとしなくなります。
結果、雇われる可能性があるのは、平均以下の実力を持ったエンジニアだけになります。
ここで再び、実力の平均を再計算すると、当然、以前の平均よりも低下します。
すると、下がった平均より高い実力を持ったエンジニア達は「うわっ、私の年収、低すぎ・・・？」となって、雇われようとしなくなります。

このループは全てのエンジニアが同じ実力となるまで続き、最終的に実力が最低値の人間のみになると終了します。

つまり、エンジニアの能力を適切に評価出来ない企業は、このモデルにおいて、最低の実力を持ったエンジニアしか雇いません。

このことが指し示すのは、エンジニアの能力を適切に評価出来ない企業で働くと、報酬が低く、周囲にいるエンジニアの能力も低いという劣悪な環境に置かれる可能性が高い、ということです。

なるほど、確かに、エンジニアを適切に評価出来ない企業で働くことは、合理的とは言えなさそうです。

このように、自分が購入しようと考えているものの価値が自分では分からない時、とにかく安いものを求めた結果、品質の悪いものを買ってしまうようなことを、経済学では「逆選択」と言います。

教科書的には、アメリカの中古車市場で品質の悪い車ばかりが出回っている理由を説明する時に、用いられます。

消費者は中古車の品質が分からないので、安い物を買おうとする
↓
品質の良い中古車を売っている業者は、品質に見合った値段を付けても売れないため、市場から退出する
↓
市場には品質が悪く安い車しか残らなかった。

ということが起こったのだと言われているそうです。

競技プログラミングとは殆ど関係の無い記事でしたが、ご愛嬌ということで(笑

最後に一つ申し上げておきますが、本記事は、エンジニアの方をdisるものでは決してありません。念のため。

このような楽しい企画を主催して下さった@_tanzaku_様、有り難うございました。

2011年11月16日水曜日

CodeForces #94 Div2 Only

Problem A Cookies

Passed System Test

クッキーがの入った袋がいくつか並んでいる。

一つを取って、残った袋に入っているクッキーの数が偶数になるような取り方は何通りあるか。

解答

完全にやるだけ。

#include <algorithm>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <string>
#include <vector>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <stack>
#include <deque>
#include <queue>
#include <functional>
 
using namespace std;
 
#define REP(i,s,e) for (int i = int(s); i != int(e); i++)
#define rep(i,e) REP(i,0,e)
#define foreach(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ALL(c) ((c).begin(), (c).end())
#define ll long long
#define VI vector<int>
 
int main() {
 int n;
 int cookie[100];
 cin >> n;
 rep(i,n) cin>>cookie[i];
 int even = 0,odd = 0;
 rep(i,n) if(cookie[i]&1) odd++; else even++;
 if(odd&1){
  cout << odd << endl;
  return 0;
 }
 cout << even << endl;
 return 0;
}

Problem B Students and Shoelaces
Wrong Answer on pretest 8

n人の生徒がおり、m個の生徒の対が紐で結ばれている。
ちょうど一人のみと紐で結ばれているような生徒が居た場合、それらの生徒を排除する。
再び残った生徒を見て、１人のみと紐で結ばれている生徒を排除する。
この操作を繰り返し、何回排除が行われたかを数える。

解法
シミュレートすればよい。
生徒の数は高々１００人なので、O(n^3)のループまで間に合う。
このコードの場合0(2n^2)なのでもう少し余裕がある。

#include <algorithm>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <string>
#include <vector>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <stack>
#include <deque>
#include <queue>
#include <functional>
 
using namespace std;
 
#define REP(i,s,e) for (int i = int(s); i != int(e); i++)
#define rep(i,e) REP(i,0,e)
#define foreach(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ALL(c) ((c).begin(), (c).end())
#define ll long long
#define VI vector<int>
 
bool tied[100][100];
int num[100];
int n,m;
void check(){
 int count;
 rep(i,n){
  count = 0;
  rep(j,n) if(tied[i][j]){
   count++;
  }
  num[i] = count;
 }
}
 
int main(){
 int repri,ans = -1;
 memset(tied,false,sizeof(tied));
 int kid1,kid2;
 cin>>n>>m;
 rep(i,m){
  cin>>kid1>>kid2;
  tied[kid1-1][kid2-1] = true;
  tied[kid2-1][kid1-1] = true;
 }
 do{
  check();
  //rep(i,n) cout << num[i] << endl;
  ans++;
  repri = 0;
  rep(i,n) if(num[i] == 1){
   rep(j,n){
    tied[j][i] = false;
    tied[i][j] = false;
   }
   //cout << i << "th student kicked" << endl;
   repri++;
  }
 }while(repri > 0);
 //rep(i,n) cout << i << "th student tied" << num[i] << " student" << endl;
 cout << ans << endl;
 return 0;
}

Problem C Statues
Passed System Test
8*8マスのチェスボードの対角線にMariaとAnnnaの駒が配置されている。
Mariaは左下隅。Annnaは右上隅。
Mariaはターンごとに将棋の王の駒と同じ動き方が可能である。同じマスに留まることも可能。
マス目にはStatueが配置されている場合があり、MariaはStatueの存在するマスには移動出来ない。
また、１ターンごとにStatueは１マス落下し、潰されるとゲームオーバーになる。
Statueは一番最後のマスを超えると消え去る。
MariaがAnnnaのマスに到達することは可能か。

解法
8*8マスなので、Statueは最悪でも７ターン経過すれば害が無くなり、８ターン目で全て消え去る。
DPを行い、7ターン後に生き延びていれば勝利とした。
実装はStatues[8][8]として、各マス目に対応する二次元配列を作成。
該当するメモリのnビット目にビットがセットされていれば、そのターンそこに居るとゲームオーバーになるとして枝刈りを行っている。
ちなみに、像は１ターンにつき、自分の存在するマスと、自分が落下する対象のマスとの合計２マスを制限している。

提出コード

#include <algorithm>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <string>
#include <vector>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <stack>
#include <deque>
#include <queue>
#include <functional>
 
using namespace std;
 
#define REP(i,s,e) for (int i = int(s); i != int(e); i++)
#define rep(i,e) REP(i,0,e)
#define foreach(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ALL(c) ((c).begin(), (c).end())
#define ll long long
#define VI vector<int>
 
 
int statue[8][8];
 
typedef struct pos{
 int x;
 int y;
 int turn;
 
 bool is_valid(int _x, int _y,int turn){
  if(x+_x < 0 || y+_y < 0) return false;
  if(x+_x > 7 || y + _y > 7) return false;
  if(statue[x+_x][y+_y] & 1<<turn) return false;
  return true;
 }
 
} pos;
 
int main(){
 string map[8];
 memset(statue,false,sizeof(statue));
 rep(i,8) cin >> map[i];
 rep(i,8) rep(j,8) if(map[i][j] == 'S'){
  for(int k = 0;i+k < 8;k++){
   statue[i+k][j] |= 1<<k;
   statue[i+k][j] |= 1<<(k+1);
  }
 }
 queue<pos> dp;
 pos init = {7,0,0};
 dp.push(init);
 while(!dp.empty()){
  pos tmp = dp.front(); dp.pop();
 
  tmp.turn++;
  if(tmp.turn == 8){
   cout << "WIN" << endl;
   return 0;
  }
  REP(i,-1,2) REP(j,-1,2){
   if(tmp.is_valid(i,j,tmp.turn)){
    pos next = {tmp.x+i, tmp.y+j, tmp.turn};
    dp.push(next);
   }
  }
 }
 cout << "LOSE" << endl;
 return 0;
}

レート　1329　→　1416 (+87)

レートは少し上がり、Specialistに復帰しましたが、まだまだです。
次は青コーダーですね。

登録: 投稿 (Atom)