業務の都合で、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のソースコードは読んでいないため、仕様が本記事と異なる可能性がある。
私も技術的には非常に未熟であるため、誤っている点があれば是非ご教示頂きたい。
2015年6月11日木曜日
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を出力せよ。
解法
まぁ、やるだけです。
提出コード
Medium
長方形の上にコインが幾つか乗っている。
プレイヤーは一回につき、上下右左を選び、全てのコインをその方向に動かしてよい。
この操作によって、与えられた長方形からコインがはみ出た場合、コインは落ちて消える。
コインがK枚になるような最小の操作回数を出力せよ。なお、K枚に出来ない場合は-1を出力せよ。
解法
操作を何回行っても、残るのは長方形になる。(或いは何も残らない。。。)
部分長方形を考え、その長方形に対して何枚コインが残るかが分かれば、最小の命令回数は一意に定まる。
例えば、下の行を1つ、上の行を2つ削るような部分長方形を作る場合、下、上、上、上となり、命令回数は四回である。
下と上の順番を逆にしてしまうと、上、上、下、下、下となり、5回となってしまう。
反対側の辺も削るような長方形を作る場合、順番に注意。
提出コード
最近サボりがひどく、いざTopCoderを開いてもついついTwitterを見に行くなどしてしまっていたため、ニコ生で放送しつつ解くということを試しにやってみた。
すると、なんと放送初回から@chokudai 先生が視聴するというミラクルが発生。これにはおいらもびっくり。もっとも、放送している時は全然気付かなかったし、@chokudai 師匠のありがたいアドバイスも勘違いしていて迷走していたのだが(笑)
次はCodeForcesが近いので、久しぶりに出るつもり。
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を返す。
解法
ケツからみていくだけです。
提出コード
Medium
n行m列の行列がある。
各行、各列ごとに最大１羽、アヒルが居る。
アヒルを移動させて、縦でも横でもいいから整列させたい。
アヒルは、移動先が空いていればどこへでも移動が可能で、移動にかかる時間はハミルトン距離によって算出される。
整列するのにかかる最小の時間を求めよ。
解法
どういう整列のさせ方をするかが決まれば、その整列の実現にかかる最小の時間は一意に定まる。
よって、全通り試して最小の時間を返せばよい。
より具体的には、例えば横に並べる場合、最も左に居るアヒルを列の最も左に移動させ、そのアヒルの次に最も左に居るアヒルをその右へ移動させ。。。と整列させる。
縦に並べる場合も同じである。
この整列のさせ方が最小の時間を取ることは、図を書けば直ちに分かる。
実装では、二次元の構造体にアヒルの位置を記憶させ、vectorにしまったのち、xとyそれぞれに対してバブルソートを行わせる関数を実装して対処した。
提出コード
先頭から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であることを思い出して。
今回は、競技プログラミング風に、問題を解くことで考えてみましょう。
この問題は再帰関数で愚直にシミュレーションを行うことで解けそうです。
実装してみましょう。
この解答を実行すると分かりますが、最終的に会社に来る可能性のあるエンジニアは、常に能力の最も低いエンジニアとなり、報酬も最低値を取ります。
何故こうなるのか？
初期状態では、全エンジニアは雇われる可能性があります。
これらの平均を報酬として提示すると、平均より高い実力を持ったエンジニア達は「うわっ、私の年収、低すぎ・・・？」となり、雇われようとしなくなります。
結果、雇われる可能性があるのは、平均以下の実力を持ったエンジニアだけになります。
ここで再び、実力の平均を再計算すると、当然、以前の平均よりも低下します。
すると、下がった平均より高い実力を持ったエンジニア達は「うわっ、私の年収、低すぎ・・・？」となって、雇われようとしなくなります。
このループは全てのエンジニアが同じ実力となるまで続き、最終的に実力が最低値の人間のみになると終了します。
つまり、エンジニアの能力を適切に評価出来ない企業は、このモデルにおいて、最低の実力を持ったエンジニアしか雇いません。
このことが指し示すのは、エンジニアの能力を適切に評価出来ない企業で働くと、報酬が低く、周囲にいるエンジニアの能力も低いという劣悪な環境に置かれる可能性が高い、ということです。
なるほど、確かに、エンジニアを適切に評価出来ない企業で働くことは、合理的とは言えなさそうです。
このように、自分が購入しようと考えているものの価値が自分では分からない時、とにかく安いものを求めた結果、品質の悪いものを買ってしまうようなことを、経済学では「逆選択」と言います。
教科書的には、アメリカの中古車市場で品質の悪い車ばかりが出回っている理由を説明する時に、用いられます。
消費者は中古車の品質が分からないので、安い物を買おうとする
↓
品質の良い中古車を売っている業者は、品質に見合った値段を付けても売れないため、市場から退出する
↓
市場には品質が悪く安い車しか残らなかった。
ということが起こったのだと言われているそうです。
競技プログラミングとは殆ど関係の無い記事でしたが、ご愛嬌ということで(笑
最後に一つ申し上げておきますが、本記事は、エンジニアの方をdisるものでは決してありません。念のため。
このような楽しい企画を主催して下さった@_tanzaku_様、有り難うございました。
みなさんこんにちは、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)
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
Problem B Students and Shoelaces
Wrong Answer on pretest 8
n人の生徒がおり、m個の生徒の対が紐で結ばれている。
ちょうど一人のみと紐で結ばれているような生徒が居た場合、それらの生徒を排除する。
再び残った生徒を見て、１人のみと紐で結ばれている生徒を排除する。
この操作を繰り返し、何回排除が行われたかを数える。
解法
シミュレートすればよい。
生徒の数は高々１００人なので、O(n^3)のループまで間に合う。
このコードの場合0(2n^2)なのでもう少し余裕がある。
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ビット目にビットがセットされていれば、そのターンそこに居るとゲームオーバーになるとして枝刈りを行っている。
ちなみに、像は１ターンにつき、自分の存在するマスと、自分が落下する対象のマスとの合計２マスを制限している。
提出コード
レート 1329 → 1416 (+87)
レートは少し上がり、Specialistに復帰しましたが、まだまだです。
次は青コーダーですね。
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に復帰しましたが、まだまだです。
次は青コーダーですね。
2011年10月23日日曜日
School Regional Team Contest, Saratov, 2011
Code Forces で開催された 「School Regional Team Contest, Saratov, 2011」に参加してきました。
しょうもないミスでCまでしか解けていません。
Problem A
Elevator
Passed System Test
簡単という比喩ではなく本当にやるだけ。
School Contestなので、慣れない人たち向けのウォーミングアップ問題の意味合いで設けたのでしょう。
Problem B
Quiz League
Passed System Test
ランダム選択式クイズリーグの途中である。
全部でN問問題が存在し、既に幾つかの問題が解かれている。
今、問題が１〜N番目の中からランダムに選択されようとしているが、既に解かれてしまった問題が選択された場合、その次の問題を解くことになる。それも解かれていた場合、同じことを繰り返す。
N番目の次の問題は、１番目の問題とみなす。
K番目の問題が選ばれたとして、実際に解くことになるのは何番目の問題か。
１行目にN K、
２行目にはN個の０か１かの数字が入力されており、０であれば既に解かれている。
解法
やるだけ。
Problem C
Winnie-the-Pooh and Honey
Passed System Test
問題文
ハチミツの入ったつぼがN個ある。
それぞれのつぼにはAi キログラムのハチミツが入っている。
プーさんは飢えており、つぼを取っては、そのつぼに入っているハチミツをKキロ食べる。
選んだつぼに入っているハチミツがKキロ未満の場合か、既にそのつぼから３Kキロ食べていた場合、そのつぼをピグレットに渡す。
この操作を、つぼをピグレットに全て渡すまで繰り返す。
ピグレットは合計で何キロのハチミツを得ることが出来るか？
解法
やるだけ。問題文には、実はハチミツの一番多く入っているつぼを常に食べると書いてあるのですが、これは解法には全く関係しないため、省略しました。
Three sons
Wrong Answer on Pretest 3
n*m行列が与えられる。行列のij要素はそれぞれの領域におけるとうもろこしの収量を表す。
この畑を、互いに平行な２本の線を引くことで３つに分割し、それぞれの畑の収量がA,B,Cとなるように分割する方法は何通りあるか？なお、畑は斜めに斬ってはならず、それぞれの畑は最低でも１つの領域を持っていなければならないとする。
ソート関数のメモリ指定を間違えるというポカをやらかした挙句、それに気付かず、ロジック部分に問題があると思い込んで粗を探していました。
終了後に気付き、落ち込む。
解法はnext_permutationを使った至って単純な全探索でした。
データセットが非常に軽いため(最大でも50*50行列)、全探索でも何の問題もありません。
Rating 1446 → 1420 (-26)
少し落ちてしまいました。D問題が解けて入れば、少しはマシだったかもしれませんが、今更嘆いても仕方がありません。
精進あるのみですね。
しょうもないミスでCまでしか解けていません。
Problem A
Elevator
Passed System Test
簡単という比喩ではなく本当にやるだけ。
School Contestなので、慣れない人たち向けのウォーミングアップ問題の意味合いで設けたのでしょう。
Problem B
Quiz League
Passed System Test
ランダム選択式クイズリーグの途中である。
全部でN問問題が存在し、既に幾つかの問題が解かれている。
今、問題が１〜N番目の中からランダムに選択されようとしているが、既に解かれてしまった問題が選択された場合、その次の問題を解くことになる。それも解かれていた場合、同じことを繰り返す。
N番目の次の問題は、１番目の問題とみなす。
K番目の問題が選ばれたとして、実際に解くことになるのは何番目の問題か。
１行目にN K、
２行目にはN個の０か１かの数字が入力されており、０であれば既に解かれている。
解法
やるだけ。
#include <string>
#include <iostream>
#include <algorithm>
#include <queue>
#include <map>
#include <vector>
#include <set>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <fstream>
using namespace std;
#define REP(i,s,e) for(int i = s;i < e;i++)
#define rep(i,e) REP(i,0,e)
#define ll long long
int main(){
ifstream input("input.txt");
ofstream output("output.txt");
int yet[1000];
int n,m;
input >> n >> m;
rep(i,n) input >> yet[i];
for(int i = m-1;i < m+n;i++){
if(yet[i%n]){
output << (i)%n + 1 << endl;
return 0;
}
}
}
Problem C
Winnie-the-Pooh and Honey
Passed System Test
問題文
ハチミツの入ったつぼがN個ある。
それぞれのつぼにはAi キログラムのハチミツが入っている。
プーさんは飢えており、つぼを取っては、そのつぼに入っているハチミツをKキロ食べる。
選んだつぼに入っているハチミツがKキロ未満の場合か、既にそのつぼから３Kキロ食べていた場合、そのつぼをピグレットに渡す。
この操作を、つぼをピグレットに全て渡すまで繰り返す。
ピグレットは合計で何キロのハチミツを得ることが出来るか？
解法
やるだけ。問題文には、実はハチミツの一番多く入っているつぼを常に食べると書いてあるのですが、これは解法には全く関係しないため、省略しました。
#include <string>
#include <iostream>
#include <algorithm>
#include <queue>
#include <map>
#include <vector>
#include <set>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <fstream>
using namespace std;
#define REP(i,s,e) for(int i = s;i < e;i++)
#define rep(i,e) REP(i,0,e)
#define ll long long
#define INF 1 << 30
int main(){
ifstream input("input.txt");
ofstream output("output.txt");
int jars[100];
memset(jars, 50000, sizeof(jars));
int n,k;
int ans = 0;
input >> n >> k;
int limit = k * 3;
rep(i,n) input >> jars[i];
sort(jars, jars+99);
rep(i,n){
if(jars[i] < limit) ans += jars[i] % k; else ans += jars[i] - limit;
}
output << ans << endl;
}
Problem DThree sons
Wrong Answer on Pretest 3
n*m行列が与えられる。行列のij要素はそれぞれの領域におけるとうもろこしの収量を表す。
この畑を、互いに平行な２本の線を引くことで３つに分割し、それぞれの畑の収量がA,B,Cとなるように分割する方法は何通りあるか？なお、畑は斜めに斬ってはならず、それぞれの畑は最低でも１つの領域を持っていなければならないとする。
ソート関数のメモリ指定を間違えるというポカをやらかした挙句、それに気付かず、ロジック部分に問題があると思い込んで粗を探していました。
終了後に気付き、落ち込む。
解法はnext_permutationを使った至って単純な全探索でした。
データセットが非常に軽いため(最大でも50*50行列)、全探索でも何の問題もありません。
Rating 1446 → 1420 (-26)
少し落ちてしまいました。D問題が解けて入れば、少しはマシだったかもしれませんが、今更嘆いても仕方がありません。
精進あるのみですね。
2011年10月2日日曜日
CaBoCha on Ubuntu 11.04 with charset UTF-8
構文解析器CabochaをUbuntuに実行する際、詰まった点がそこそこあったので、メモしておく。
特に後半に関してはWebでエラーログを検索しても情報がほとんど無かったため、手探り感があった。
Cabochaのインストールそのものについては、他にたくさんのBlogが存在しているので、それについては省く。
このブログに辿り着いた人は多分、
まず前者であるが、これはもうエラーログ通り /etc/cabocharc が存在していないことがエラーの原因だ。
sudo find / -name cabocharc
としてやると、おそらく、
/usr/local/etc/cabocharc
というものが見つかる筈だ。
これを
/etc/cabocharc
にコピーしてやればよい。
次に後者である。
これは、 charset-file.txt に書いてある文字コードと、cabocha の文字コードが一致していないことによって生じている。
sudo find / -name charaset-file.txt
としてやり、セッティングファイルを探す。
いくつか出てくるかもしれないし、一つかもしれない。
それは色々な場合があるので分からないが、そのうちの一つがUTF-8になっていることを確認し(無ければ編集し)する。
次に、先ほどコピーしてやったcabocharcを開く。
コメントアウトされた charaset-filr = PATH という行が見つかる筈だ。
コメントアウトを解除し、先ほどUTF-8と書いてあったファイルへのPATHを記入し、保存してやる。
これで、問題なく動くようになるはずだ。
特に後半に関してはWebでエラーログを検索しても情報がほとんど無かったため、手探り感があった。
Cabochaのインストールそのものについては、他にたくさんのBlogが存在しているので、それについては省く。
このブログに辿り着いた人は多分、
param.cpp(70) [ifs] no such file or directory: /etc/cabocharcこういうログか、あるいは
morph.cpp(108) [charset() == decode_charset(dinfo->charset)] Incompatible charset: MeCab charset is UTF-8, Your charset is EUCJP-WINこういうログで困っているのだろう、と推測する。
まず前者であるが、これはもうエラーログ通り /etc/cabocharc が存在していないことがエラーの原因だ。
sudo find / -name cabocharc
としてやると、おそらく、
/usr/local/etc/cabocharc
というものが見つかる筈だ。
これを
/etc/cabocharc
にコピーしてやればよい。
次に後者である。
これは、 charset-file.txt に書いてある文字コードと、cabocha の文字コードが一致していないことによって生じている。
sudo find / -name charaset-file.txt
としてやり、セッティングファイルを探す。
いくつか出てくるかもしれないし、一つかもしれない。
それは色々な場合があるので分からないが、そのうちの一つがUTF-8になっていることを確認し(無ければ編集し)する。
次に、先ほどコピーしてやったcabocharcを開く。
コメントアウトされた charaset-filr = PATH という行が見つかる筈だ。
コメントアウトを解除し、先ほどUTF-8と書いてあったファイルへのPATHを記入し、保存してやる。
これで、問題なく動くようになるはずだ。
2011年10月1日土曜日
GCJJ
GCJJに行ってきた。
起きたのが17：50ぐらい。
とりあえず軽くメシ食って、始めたのが18：20分ちょい前ぐらいだったか。
時間がヤバ過ぎたので正解率の高いCを選択。
正の整数Nを、0以上の整数であるa と b を使い
a + b = N
と表す。
f(x)を、xを二進数で表した場合の１の数とし、
f(a) + f(b) = k
のkが最大になる場合のkの値を求めよ。
という問題。
例えば、９ならば、
f(9) + f(0) = 2
f(8) + f(1) = 3
f(7) + f(2) = 4
f(6) + f(3) = 4
f(5) + f(4) = 3
と、それぞれなるので、正解は4となる。
初めは愚直に探索していくのかなと思ったが、largeの制約が N < 10^18だったため、どう考えてもそれでは間に合わない。
二進数ならではの考え方がある。
ビット単位で考えてやると、 10 < 2^4であるから、最大でも4*18 = 72より少ない計算量で達成出来る。
a + b の形になっているので、二進数の特質が大いに生かせそうだ。
暫く考えていたところ、0がキーになっていることが分かった。
11100100111のような場合、右から考えてやって、最初に0が出るまでの1は、aかbどちらかの該当ビットだけに1を設定してやることによってしか表現出来ないが、それ以降の1は、aとbの両方の該当ビット一つ下に１を設定してやることで表現出来そうだ。
これを拡張して、1001001のように0が続いている場合、a = 0111111, b = 0001010 のように表現できることが分かる。
これを実装したのが以下
起きたのが17：50ぐらい。
とりあえず軽くメシ食って、始めたのが18：20分ちょい前ぐらいだったか。
時間がヤバ過ぎたので正解率の高いCを選択。
正の整数Nを、0以上の整数であるa と b を使い
a + b = N
と表す。
f(x)を、xを二進数で表した場合の１の数とし、
f(a) + f(b) = k
のkが最大になる場合のkの値を求めよ。
という問題。
例えば、９ならば、
f(9) + f(0) = 2
f(8) + f(1) = 3
f(7) + f(2) = 4
f(6) + f(3) = 4
f(5) + f(4) = 3
と、それぞれなるので、正解は4となる。
初めは愚直に探索していくのかなと思ったが、largeの制約が N < 10^18だったため、どう考えてもそれでは間に合わない。
二進数ならではの考え方がある。
ビット単位で考えてやると、 10 < 2^4であるから、最大でも4*18 = 72より少ない計算量で達成出来る。
a + b の形になっているので、二進数の特質が大いに生かせそうだ。
暫く考えていたところ、0がキーになっていることが分かった。
11100100111のような場合、右から考えてやって、最初に0が出るまでの1は、aかbどちらかの該当ビットだけに1を設定してやることによってしか表現出来ないが、それ以降の1は、aとbの両方の該当ビット一つ下に１を設定してやることで表現出来そうだ。
これを拡張して、1001001のように0が続いている場合、a = 0111111, b = 0001010 のように表現できることが分かる。
これを実装したのが以下
#include <algorithm>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <cmath>
#include <time.h>
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 ISEQ(c) (c).begin(), (c).end()
#define ll long long
#define INF 1<<30
int main(){
unsigned ll n;
int testCase,bits_after_zero,bits_before_zero,num_zero;
scanf("%d", &testCase);
rep(i,testCase)
{
bits_after_zero = 0; bits_before_zero = 0; num_zero = 0;
scanf("%lld", &n);
do{
if(n & 1) bits_before_zero++; else{
n >>= 1;
break;
}
}while( (n >>= 1) > 0);
do{
if(!(n > 0)) break;
if(n & 1) bits_after_zero++; else num_zero++;
}while( ( n >>= 1 ) > 0);
printf("Case #%d: %d\n", i+1, bits_after_zero * 2 + bits_before_zero + num_zero);
}
}
残りの問題は後でまた解く
2011年9月18日日曜日
Pythonスクリプトの実行時間をメソッドごとに評価する「Python-profiler」が凄い」
Hacker Newsに上がっていた記事「Run,Python,Run!」で扱っているスクリプト、Python Profilerが凄い。
何が凄いって、Pythonでかかれたスクリプトの実行時間を、メソッドごとに計測し、グラフィカルに表示してくれるのだ。
試しに使ってみたが、これは素晴らしかった。
#vim encoding=utf8
def loop(x):
for i in range(x):
print "やっほー"
def loop_list(x):
yahho = []
for i in range(x):
yahho.append("やっほー")
yahhoi = loop_list(1000)
loop(1000)
上記のスクリプトを実行し、プロファイルしてみたのが以下
loopが時間を食っていること、更に、loop_list内で実行されているappend()の実行にどれだけ時間を食っているかも分かるのだ。
ちなみにこれ、モジュール内で更に関数を実行していた場合、再帰的に実行時間を計測出来る。
例えば、関数内でurllibのurlopenを実行していた場合、urlopen内で実行されているsocketオブジェクトのメソッドであるconnect_ofの実行時間を計測出来たりもする。
更に深いところになるとまた違う手法を求められるのであろうが(筆者にその知識はない)、しかし、手掛かりを簡単に掴めるというだけでも、使ってみる価値はあるのではなかろうか。
では、インストール方法の説明である。
コンソールに行き、
何が凄いって、Pythonでかかれたスクリプトの実行時間を、メソッドごとに計測し、グラフィカルに表示してくれるのだ。
試しに使ってみたが、これは素晴らしかった。
#vim encoding=utf8
def loop(x):
for i in range(x):
print "やっほー"
def loop_list(x):
yahho = []
for i in range(x):
yahho.append("やっほー")
yahhoi = loop_list(1000)
loop(1000)
上記のスクリプトを実行し、プロファイルしてみたのが以下
loopが時間を食っていること、更に、loop_list内で実行されているappend()の実行にどれだけ時間を食っているかも分かるのだ。
ちなみにこれ、モジュール内で更に関数を実行していた場合、再帰的に実行時間を計測出来る。
例えば、関数内でurllibのurlopenを実行していた場合、urlopen内で実行されているsocketオブジェクトのメソッドであるconnect_ofの実行時間を計測出来たりもする。
更に深いところになるとまた違う手法を求められるのであろうが(筆者にその知識はない)、しかし、手掛かりを簡単に掴めるというだけでも、使ってみる価値はあるのではなかろうか。
では、インストール方法の説明である。
コンソールに行き、
sudo apt-get install python-profiler python-wxgtk2.8 python-setuptoolssudo easy_install SquareMap RunSnakeRun
たったこれだけだ。
プロファイルの作成方法であるが、
python -m cProfile -o outputfilename pythonscript script_arguments
こちらのフォーマットに従ってくれれば問題ない。
筆者の行った例で言えば、計測したいスクリプト名が「test.py」、出力したいプロファイル名が「output」であったから、
python -m cProfile -o output test.py
と、した。
プロファイルを見る場合は、
runsnake output
とすればよい。
日頃行っているサービスのパフォーマンス改善は勿論のこと、競技プログラミングで手詰まりを起こした際にも役立つ場面がある(?)のではなかろうか。
2011年7月14日木曜日
CodeForces Beta Round #76 Div2 Only
A
Restoring Password
日本語でおｋ
B
Friends
Passed System Test
5人の人間が居て、誰と誰が知り合いか、という情報が与えられる。
知り合い同士の３人グループが存在するか、互いに全く知り合いでない３人グループが存在する場合 WIN と、そうでない場合 FAIL と出力せよ
解法
やるだけ
Problem C
Frames
Passed System Test
PC上にあるディレクトリ削除の問題
全部n個のフォルダが、m列まで並べられる空間に並べられている。
例
１１個のフォルダを３列に並べる場合
１ ２ ３
４ ５ ６
７ ８ ９
10 11
こんな感じ
a番目からb番目にあるフォルダを全て削除したい。
Shiftキーを押しながら選択することで、複数のフォルダからなる矩形を作成することが出来、矩形に含まれるフォルダは一度に削除することが可能。
全て削除するまでに、何回の操作が必要か？
解法
やるだけ。と言いたいところだが。
前提条件から、操作回数は３以下。
そして、削除すべきフォルダの存在する行数が3以上の場合、考慮すべき問題は全て3
行の時と変わらなくなる。
後は考えられる条件を全て挙げていけば良い。
コード
Rating 1367 → 1483
かなり上昇しました。
あと、Wrong Answerの場合、正解した時に取得出来るスコアが減少するということを知りました。
次から気を付けてやりたいと思います。
最近は時間が合わず、コンピティションになかなか参加出来ていません。
上手く時間を作って行きたいものです
Restoring Password
日本語でおｋ
B
Friends
Passed System Test
5人の人間が居て、誰と誰が知り合いか、という情報が与えられる。
知り合い同士の３人グループが存在するか、互いに全く知り合いでない３人グループが存在する場合 WIN と、そうでない場合 FAIL と出力せよ
解法
やるだけ
#include <iostream>
#include <vector>
#include <string>
#include <string.h>
#include <map>
#include <set>
#include <algorithm>
#include <time.h>
#include <cmath>
#include <queue>
#define REP(i,s,e) for(int i = s;i<e;i++)
#define rep(i,e) REP(i,0,e)
using namespace std;
int main(){
int pair[6][6];
memset(pair,0,sizeof(pair));
int n;
cin>>n;
int a,b;
rep(i,n){
cin>>a>>b;
pair[a][b] = 1;
pair[b][a] = 1;
}
int count[2];
REP(i,1,6){
memset(count,0,sizeof(count));
REP(j,1,6){
if(i==j) continue;
if(pair[i][j]) count[0]++; else count[1]++;
}
if(count[0] >= 3 || count[1] >= 3){
cout << "WIN" << endl;
return 0;
}
}
cout << "FAIL" << endl;
}
Problem C
Frames
Passed System Test
PC上にあるディレクトリ削除の問題
全部n個のフォルダが、m列まで並べられる空間に並べられている。
例
１１個のフォルダを３列に並べる場合
１ ２ ３
４ ５ ６
７ ８ ９
10 11
こんな感じ
a番目からb番目にあるフォルダを全て削除したい。
Shiftキーを押しながら選択することで、複数のフォルダからなる矩形を作成することが出来、矩形に含まれるフォルダは一度に削除することが可能。
全て削除するまでに、何回の操作が必要か？
解法
やるだけ。と言いたいところだが。
前提条件から、操作回数は３以下。
そして、削除すべきフォルダの存在する行数が3以上の場合、考慮すべき問題は全て3
行の時と変わらなくなる。
後は考えられる条件を全て挙げていけば良い。
コード
#include <iostream>
#include <vector>
#include <string>
#include <string.h>
#include <map>
#include <set>
#include <algorithm>
#include <time.h>
#include <cmath>
#include <queue>
#define REP(i,s,e) for(int i = s;i<e;i++)
#define rep(i,e) REP(i,0,e)
#define ll long long
using namespace std;
int main(){
ll n,m,a,b;
cin>>n>>m>>a>>b;
ll column = (b-1)/m - (a-1)/m;
ll row_a = a%m;
ll row_b = b%m;
if(m == 1){
cout << 1 << endl;
return 0;
}
switch(column){
case 0:
cout << 1 << endl; // 一行で済む場合
return 0;
case 1:
if(row_a == 1 && (row_b == 0 || n == b)){ // 二行だが、一回で囲えてしまう場合
cout << 1 << endl;
return 0;
}
cout << 2 << endl; // そうではない場合
return 0;
default: // 三行以上の場合
if(row_a == 1 && (row_b == 0 || n==b)){ // 一回で全て囲えてしまう場合
cout << "1" << endl;
return 0;
}else if( (a-1)%m == b%m || row_b == 0 || row_a == 1 || b == n){ //
cout << 2 << endl;
return 0;
}
cout << 3 << endl;
return 0;
}
}
Rating 1367 → 1483
かなり上昇しました。
あと、Wrong Answerの場合、正解した時に取得出来るスコアが減少するということを知りました。
次から気を付けてやりたいと思います。
最近は時間が合わず、コンピティションになかなか参加出来ていません。
上手く時間を作って行きたいものです
社会科学×テキストマイニングに役立ちそう(?)な論文
卒業論文で社会科学とテキストマイニングを融合させたものを書こうと思っているので、そのための参考資料をGoogle Scholarで探してみました。
自分はまだ自然言語処理のための理論を学んでいる途中ではありますが、後々必要になると思うので、自分用のメモに。
blog ページの自動収集と監視に基づくテキストマイニング
http://pricai-02.nii.ac.jp/papers/SIG-SWO-A401/SIG-SWO-A401-01.pdf
追記：上記はblogWatcherというサービスに関する文書で、論文というよりも報告書に近い模様。私の立場(情報知能に興味のある経済学部生)からは余り見る価値はなかった。
テキストマイニングによる評価表現の収集
http://www.syncha.org/papers/signl154.pdf
追記：テキストマイニングにおける概念抽出の前段階となる辞書の作成に役立ちそうな論文。
「テキストマイニングを使う技術/作る技術」に載っている手法を用いた方が良いか、こちらが良いかはやってみないと分からん。
Weblog を対象とした評価表現抽
http://www.jaist.ac.jp/ks/labs/kbs-lab/sig-swo/papers/SIG-SWO-A401/SIG-SWO-A401-02.pdf
テキストを対象とした評価情報の分析に関する研究動
http://www.nlp.mibel.cs.tsukuba.ac.jp/~inui/paper/nlp2006-survey.pdf
人口市場とテキストマイニングの融合による市場分析
http://www.ymatsuo.com/papers/jsai07kiyoshi.pdf
自分はまだ自然言語処理のための理論を学んでいる途中ではありますが、後々必要になると思うので、自分用のメモに。
blog ページの自動収集と監視に基づくテキストマイニング
http://pricai-02.nii.ac.jp/papers/SIG-SWO-A401/SIG-SWO-A401-01.pdf
追記：上記はblogWatcherというサービスに関する文書で、論文というよりも報告書に近い模様。私の立場(情報知能に興味のある経済学部生)からは余り見る価値はなかった。
テキストマイニングによる評価表現の収集
http://www.syncha.org/papers/signl154.pdf
追記：テキストマイニングにおける概念抽出の前段階となる辞書の作成に役立ちそうな論文。
「テキストマイニングを使う技術/作る技術」に載っている手法を用いた方が良いか、こちらが良いかはやってみないと分からん。
Weblog を対象とした評価表現抽
http://www.jaist.ac.jp/ks/labs/kbs-lab/sig-swo/papers/SIG-SWO-A401/SIG-SWO-A401-02.pdf
テキストを対象とした評価情報の分析に関する研究動
http://www.nlp.mibel.cs.tsukuba.ac.jp/~inui/paper/nlp2006-survey.pdf
人口市場とテキストマイニングの融合による市場分析
http://www.ymatsuo.com/papers/jsai07kiyoshi.pdf
2011年7月13日水曜日
自分用メモ
確率を勉強し始めたのでメモ
ポアソン分布
単位時間中にある事象が平均でλ回発生している(前提)
では、単位時間中に事象がk回発生する確率はいくらか？
P(X=k) = (λ^^k*e^^-λ)/k!
これがポアソン分布
exp(x) = e^^x
ポアソン分布
単位時間中にある事象が平均でλ回発生している(前提)
では、単位時間中に事象がk回発生する確率はいくらか？
P(X=k) = (λ^^k*e^^-λ)/k!
これがポアソン分布
exp(x) = e^^x
2011年6月26日日曜日
2011年6月21日火曜日
Google先生...
いつからか知らないが、Google先生が検索結果に出てきたページを何回閲覧したかという情報を残すようになっていた。
読者諸兄。エロサイトを見るときはログオフして使わないとな！
ちなみに僕はオキニのエロサイトを73回閲覧していたそうだ。
CodeForces Beta Round #74 Div2
報告です
A Cable Way
Passed System Test
R、G、Bそれぞれの乗り場にそれぞれr,g,b人の子供が居る。
この子供らを全員乗せ、山頂まで送り届けたい。
乗り場にケーブルカーが到着する度に、乗り場に居る生徒を二人までケーブルカーに載せることが出来る。
ケーブルカーはR→G→B→R→G→B。。。とぐるぐる回り、全員ケーブルカーに載せることが出来れば、そこから山頂へと出発する。
R乗り場からスタートし、各乗り場間の移動には一分、山頂まで行くにはどの乗り場からであっても30分かかる。
全員を載せて山頂に着くのは何分後か？
B African Crossword
Passed System Test
n行m列の、全て小文字のアルファベットで構成されたクロスワードがある。
i行j列の文字は、同じ行、或いは同じ列に、同じ文字が無ければ出力される。
法則にしたがい文字を出力せよ。
Rating 1344→1338(-6)
C,D,Eは見たが分からず。
Eは問題を解けそうだったが、Stack Overflowを起こしてしまい、断念。
他の人の回答を見たところDPっぽかったが、パッと見ただけなのでよく分からず。
要復習。
A Cable Way
Passed System Test
R、G、Bそれぞれの乗り場にそれぞれr,g,b人の子供が居る。
この子供らを全員乗せ、山頂まで送り届けたい。
乗り場にケーブルカーが到着する度に、乗り場に居る生徒を二人までケーブルカーに載せることが出来る。
ケーブルカーはR→G→B→R→G→B。。。とぐるぐる回り、全員ケーブルカーに載せることが出来れば、そこから山頂へと出発する。
R乗り場からスタートし、各乗り場間の移動には一分、山頂まで行くにはどの乗り場からであっても30分かかる。
全員を載せて山頂に着くのは何分後か？
#include <iostream>
#include <vector>
#include <string>
#include <string.h>
#include <map>
#include <set>
#include <algorithm>
#include <time.h>
#include <cmath>
using namespace std;
bool check(int r,int g, int b){
return (r>0||g>0||b>0);
}
int main()
{
int r,g,b;
cin>>r>>g>>b;
int ans = 0;
if(!check(r,g,b)){
cout << ans << endl;
return 0;
}
while(1){
r-=2;
if(!check(r,g,b)) break;
ans++; g-=2;
if(!check(r,g,b)) break;
ans++; b-=2;
if(!check(r,g,b)) break;
ans++;
}
cout << ans+30 << endl;
}
B African Crossword
Passed System Test
n行m列の、全て小文字のアルファベットで構成されたクロスワードがある。
i行j列の文字は、同じ行、或いは同じ列に、同じ文字が無ければ出力される。
法則にしたがい文字を出力せよ。
#include <iostream>
#include <vector>
#include <string>
#include <string.h>
#include <map>
#include <set>
#include <algorithm>
#include <time.h>
#include <cmath>
using namespace std;
int main(){
string ans = "";
int row,column;
cin>>row>>column;
string code[100];
bool flag;
for(int i = 0;i < row;i++) cin>>code[i];
for(int i = 0;i < row;i++) for(int j = 0;j < (int) code[i].length();j++){
flag = true;
for(int f = 0;f < row;f++){
if(f == i) continue;
if(code[f][j] == code[i][j]){
flag = false;
break;
}
}
if(!flag) continue;
for(int f = 0;f < (int) code[i].length();f++){
if(f == j) continue;
if(code[i][f] == code[i][j]){
flag = false;
break;
}
}
if(!flag) continue;
ans += code[i][j];
}
cout << ans << endl;
}
Rating 1344→1338(-6)
C,D,Eは見たが分からず。
Eは問題を解けそうだったが、Stack Overflowを起こしてしまい、断念。
他の人の回答を見たところDPっぽかったが、パッと見ただけなのでよく分からず。
要復習。
CodeForces Beta Round #75 Div2
懲りずに参加
A Chips
Passed System Test
n人が円形に並んでおり、m人のチップを順番に与えていく。
i番目の人間にi枚のチップを与え、最後まで与え終わったら初めに戻る。
与えるチップ数が足りない場合は、動作を中止し、余ったチップを回収。
回収できるチップの枚数を求める。
B Binary Number
Passed System Test
100001010のような2進数が与えられる。
与えられた数が偶数ならば、2で割り、奇数ならば、1を足す。
この操作を繰り返して、最終的に1にしたい。
何回の操作が必要になるか？
C Newspaper Headline
Compilation Error
文字列が二つ(s1,s2)与えられる。
s1を幾つか繋げた後、繋げた文字列から幾つかの文字を消去し、s2を作りたい。
s2を作成するために、必要とするs1の最小個数を出力せよ。
なお、作成出来ない場合は-1を出力せよ。
例
abcd
dabc
の場合
abcd+abcd→abcdabcdとし
abcdabcdから初めのabc、最後のdを消去すれば
dabcとなるため、出力は2である。
1≦s1≦10^4 かつ 1≦s2≦10^6
であるため、ナイーヴな実装だと確実にTLEになる。
s1における文字の出現箇所をインデックスとして保持してやり、二部探索でやろうとするも、upper_boundではうまくいかず。
aaabbb
aaabbbのような時に、
upper_boundのため最初の文字が認識されず、出力が2となってしまう。
lower_bound + 1でやろうとするも、何故かバグる。
もうちょい修行してきます。
Rating 1338→1367(+29)
以前出来なかったことが少しずつ出来るようになってきた。
ただ、コンテストに出場するよりも、今までやってきた問題の復習をした方が良い気はする。
A Chips
Passed System Test
n人が円形に並んでおり、m人のチップを順番に与えていく。
i番目の人間にi枚のチップを与え、最後まで与え終わったら初めに戻る。
与えるチップ数が足りない場合は、動作を中止し、余ったチップを回収。
回収できるチップの枚数を求める。
#include <iostream>
#include <vector>
#include <string>
#include <string.h>
#include <map>
#include <set>
#include <algorithm>
#include <time.h>
#include <cmath>
#include <queue>
using namespace std;
int main(){
int n,m;
cin >> n >> m;
while(1){
for(int i = 1;i <= n;i++){
if(i <= m) m -= i;
else{
cout << m << endl;
return 0;
}
}
}
}
B Binary Number
Passed System Test
100001010のような2進数が与えられる。
与えられた数が偶数ならば、2で割り、奇数ならば、1を足す。
この操作を繰り返して、最終的に1にしたい。
何回の操作が必要になるか？
#include <iostream>
#include <vector>
#include <string>
#include <string.h>
#include <map>
#include <set>
#include <algorithm>
#include <time.h>
#include <cmath>
#include <queue>
#define REP(i,s,e) for(int i = s;i<e;i++)
#define rep(i,e) REP(i,0,e)
using namespace std;
int main(){
string arg;
cin>>arg;
int len = (int)arg.length()-1;
int ans = len;
bool flag = false;
rep(i,len+1){
if(arg[len-i] == '1' && !flag && len != i){
flag = true;
ans+=2;
}
if(arg[len-i] == '0' && flag) ans++;
}
cout << ans << endl;
}
C Newspaper Headline
Compilation Error
文字列が二つ(s1,s2)与えられる。
s1を幾つか繋げた後、繋げた文字列から幾つかの文字を消去し、s2を作りたい。
s2を作成するために、必要とするs1の最小個数を出力せよ。
なお、作成出来ない場合は-1を出力せよ。
例
abcd
dabc
の場合
abcd+abcd→abcdabcdとし
abcdabcdから初めのabc、最後のdを消去すれば
dabcとなるため、出力は2である。
1≦s1≦10^4 かつ 1≦s2≦10^6
であるため、ナイーヴな実装だと確実にTLEになる。
s1における文字の出現箇所をインデックスとして保持してやり、二部探索でやろうとするも、upper_boundではうまくいかず。
aaabbb
aaabbbのような時に、
upper_boundのため最初の文字が認識されず、出力が2となってしまう。
lower_bound + 1でやろうとするも、何故かバグる。
もうちょい修行してきます。
Rating 1338→1367(+29)
以前出来なかったことが少しずつ出来るようになってきた。
ただ、コンテストに出場するよりも、今までやってきた問題の復習をした方が良い気はする。
2011年6月7日火曜日
家計管理入門
自分が毎月いくらぐらい使っているのか？
いま自分が持っている資産はどの程度あるのか？
ビジネス(法人)においては言わずもがな、個人レベルに落としても、それらを知っておくことは非常に重要である。
と、いうわけで家計管理入門。
僕は今まで家計簿というものを付けようとして継続したためしがなく、大抵2～3日間の記録だけが記入された家計簿が机の中で埃をかぶっている状態だ。
しかしまぁ、そんな僕も流石にそろそろ資産を管理しておかないと不味いな、と思い立ち、エクセルで家計簿を作ってみることにした。
しかしこれが面倒くさい。
「そうだ、家計簿のシートスケルトンを持ってきて、それに記入すればいいんだ！」←体の良いサボリ
といことで、色々探ってみた結果。
http://fpdiary.blog23.fc2.com/blog-entry-136.html
これである。
試しに少し使ってみたが、ズボラの権化のような僕でも何とか続きそうだ。
おそらく、初めはこういう低いライン、つまり、細かい品目を気にせず、とりあえず書く、というところから始めて、少しずつ品目を足していくのが一番良いのだろう。
@nico_shindannin さんが物凄く良いことを仰っていたので、引用
いま自分が持っている資産はどの程度あるのか？
ビジネス(法人)においては言わずもがな、個人レベルに落としても、それらを知っておくことは非常に重要である。
と、いうわけで家計管理入門。
僕は今まで家計簿というものを付けようとして継続したためしがなく、大抵2～3日間の記録だけが記入された家計簿が机の中で埃をかぶっている状態だ。
しかしまぁ、そんな僕も流石にそろそろ資産を管理しておかないと不味いな、と思い立ち、エクセルで家計簿を作ってみることにした。
しかしこれが面倒くさい。
「そうだ、家計簿のシートスケルトンを持ってきて、それに記入すればいいんだ！」←体の良いサボリ
といことで、色々探ってみた結果。
http://fpdiary.blog23.fc2.com/blog-entry-136.html
これである。
試しに少し使ってみたが、ズボラの権化のような僕でも何とか続きそうだ。
おそらく、初めはこういう低いライン、つまり、細かい品目を気にせず、とりあえず書く、というところから始めて、少しずつ品目を足していくのが一番良いのだろう。
@nico_shindannin さんが物凄く良いことを仰っていたので、引用
「高すぎる目標をたてる」→「全く達成できず」→「惜しくないので自分の能力が計れない」→「また、高すぎる目標をたてる」ループに陥っている人・会社は本当に多い。そういう人はまずは簡単な目標を立て、簡単と思っている目標すら達成するのは実は難しいのを知るべき
2011年6月1日水曜日
今更ながらTopCoder SRM507 Div1参加日記
TopCoderのSRM507に参加してきました。
Easy
Passed System Test 182.37
サイコロがある。
６つ以上の要素を持った色の配列が与えられるので、隣接する面が同じ色にならないように塗り分けられればYES、無理ならばNOを出力せよ。
要素は重複して与えられることもある。
解答
違う色が6色与えられればYES、サイコロの性質を考えれば分かることだが、同じ色でも反対側に塗れば問題ないため、同じ色は2回までなら違う色としてカウントしても良い。
提出コード
Medium
Challenge Succeeded 0
Ns個の1*1*1立方体と、Nb個のL*L*L立方体がある。
これらをまとめて一つの大きい立方体の中に入れたい。
最小になるような立方体の体積を求めよ。
L*L*Lの立方体をひたすら縦に積み上げていく方法(一次元解法)と、ひたすら三次元に拡大していく方法(三次元解法)を試したのですが、あっけなくChallenge Succeded。
修正して提出したコード(りんごさんのコードの丸パクリ)
Easy
Passed System Test 182.37
サイコロがある。
６つ以上の要素を持った色の配列が与えられるので、隣接する面が同じ色にならないように塗り分けられればYES、無理ならばNOを出力せよ。
要素は重複して与えられることもある。
解答
違う色が6色与えられればYES、サイコロの性質を考えれば分かることだが、同じ色でも反対側に塗れば問題ないため、同じ色は2回までなら違う色としてカウントしても良い。
提出コード
#include <algorithm>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <cmath>
#include <time.h>
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 ISEQ(c) (c).begin(), (c).end()
#define MIN 1<<31
#define MAX 1<<30
class CubeStickers {
public:
string isPossible( vector <string> sticker ) {
int n = (int)sticker.size();
map<string,int> colors;
map<string,int>::iterator iter;
rep(i,n){
if( (iter = colors.find(sticker[i])) != colors.end()) iter->second = 2; else colors.insert(pair<string,int>(sticker[i], 1));
}
int ans = 0;
for(iter = colors.begin();iter != colors.end();iter++) ans += iter->second;
return (ans > 5)? "YES":"NO";
}
};
Medium
Challenge Succeeded 0
Ns個の1*1*1立方体と、Nb個のL*L*L立方体がある。
これらをまとめて一つの大きい立方体の中に入れたい。
最小になるような立方体の体積を求めよ。
L*L*Lの立方体をひたすら縦に積み上げていく方法(一次元解法)と、ひたすら三次元に拡大していく方法(三次元解法)を試したのですが、あっけなくChallenge Succeded。
修正して提出したコード(りんごさんのコードの丸パクリ)
#include <algorithm>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <cmath>
#include <time.h>
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 ISEQ(c) (c).begin(), (c).end()
#define ll long long
#define INF 1<<30
class CubePacking {
public:
int getMinimumVolume( int Ns, int Nb, int L ) {
ll D=L,ss=Ns,bb=Nb,tmp,c,minimum=D*D*D*bb+ss,ans=INT_MAX,M=INT_MAX;
for(ll a=L;a*a*a<=M;a++) for(ll b=L;a*b*b<=M;b++){
tmp = (a/D) * (b/D);
c=((bb+tmp-1)/tmp)*D;
ll vol=a*b*c;
ll in=a*b;
if(minimum>vol) c+=((minimum-vol)+in-1)/in;
ans=min(a*b*c,ans);
}
return (int)ans;
}
};
登録:
投稿 (Atom)