AOJ0090
問題:Overlaps of Seals
半径1のシールが重なっている枚数の最大を求める問題．
接触している場合(中心どうしの距離が２)の場合も重なっているとみなす.
すなわち，最大枚数になっている領域は必ずいずれかの交点を含む．
すべての交点を求め，そこから半径１以内の円の中心をカウントすれば良い．
サンプルが貧弱すぎてやばい．+1e-15してなかったらWAになる．
交点座標はcomplex型で楽させてもらった．
#include<iostream> #include<vector> #include<complex> #include<cstdio> #include<cmath> using namespace std; complex<double> I(0,1); int main() { int n; while( cin >> n , n ) { vector<complex<double> > in; for( int i=0; i<n; ++i ) { double x,y; scanf("%lf,%lf",&x,&y); in.push_back( complex<double>(x,y) ); } vector<complex<double> > cp; for( int i=0; i<n-1; ++i ) { for( int j=i+1; j<n; ++j ) { if( norm( in[i]-in[j] ) <= 4.0 ) { complex<double> a( (in[i]-in[j])*0.5 ); complex<double> b( a*I ); b /= abs(b); b *= sqrt(1-norm(a)); cp.push_back( in[j]+a+b ); cp.push_back( in[j]+a-b ); } } } int ans = 1; for( int i=0; i<cp.size(); ++i ) { int a = 0; for( int j=0; j<n; ++j ) { if ( norm( cp[i]-in[j] ) <= 1.0 + 1e-15 ) { a++; } } ans = max( ans , a ); } cout << ans << endl; } return 0; }
AOJ0041
問題:Expression
なんか数字が4つ与えられるので演算子や（）をつかって値が10になる式を出力する問題.
超頭が悪い事をしてしまった.黒歴史だけど記念に掲載.
あー頭わるい
#include <iostream> #include <string> #include <sstream> #include <vector> #include <algorithm> #define DEBUG(a) //cerr << #a << ":" << a << endl; using namespace std; //Table const string symbol ="*+-"; //（）の入っていない文字列を計算して結果を文字列で返す string _calcStr(string in){ DEBUG(in); string str = in; vector<int> svi,nvi; for(int i=1;i<str.size()-1;++i) { for(int j=0;j<3;++j) { if(str[i] == symbol[j]) { svi.push_back(j); str[i] = ' '; if(str[i+1] == '-') { i++; } break; } } } stringstream ss; DEBUG(str); ss << str; int n; while(ss>>n) { nvi.push_back(n); } for(int i=0;i<svi.size();++i) { if(svi[i]==0) { nvi[0] *= nvi[1]; DEBUG(nvi[0]); nvi.erase(nvi.begin()+i+1); svi.erase(svi.begin()+i); } } while(nvi.size()!=1) { if(svi[0]==1) nvi[0] += nvi[1]; if(svi[0]==2) nvi[0] -= nvi[1]; nvi.erase(nvi.begin()+1); svi.erase(svi.begin()); } ss.clear(); str.clear(); ss << nvi[0]; ss >> str; DEBUG(str); return str; } //（）の入っている文字列を計算して結果を文字列で返す string calcStr(string in){ int pnum; if( (pnum = count(in.begin(),in.end(),'(')) != count(in.begin(),in.end(),')') ) { cerr << "error" << endl; } for(int i=0;i<pnum;++i){ unsigned int from,to,num; to = in.find_first_of(')'); from = in.substr(0,to).find_last_of('('); num = to - from ; string str = in.substr(from+1,num-1); in.erase(from,num +1); in.insert(from,calcStr(str)); } return _calcStr(in); } vector<string> createStrComb(string in) { vector<string> ret; string s; for(int i=0;i<in.size();++i) { if(in[i]>='0' && in[i]<='9') { s += in[i]; } } sort(s.begin(),s.end()); do{ for(int i=0;i<3;++i) { for(int j=0;j<3;++j) { for(int k=0;k<3;++k) { char cstr[20]; string created; sprintf(cstr,"((%c%c%c)%c%c)%c%c" ,s[0],symbol[i],s[1],symbol[j],s[2],symbol[k],s[3]); created = cstr; ret.push_back(created); sprintf(cstr,"(%c%c(%c%c%c))%c%c" ,s[0],symbol[i],s[1],symbol[j],s[2],symbol[k],s[3]); created = cstr; ret.push_back(created); sprintf(cstr,"%c%c(%c%c(%c%c%c))" ,s[0],symbol[i],s[1],symbol[j],s[2],symbol[k],s[3]); created = cstr; ret.push_back(created); sprintf(cstr,"%c%c((%c%c%c)%c%c)" ,s[0],symbol[i],s[1],symbol[j],s[2],symbol[k],s[3]); created = cstr; ret.push_back(created); sprintf(cstr,"(%c%c%c)%c(%c%c%c)" ,s[0],symbol[i],s[1],symbol[j],s[2],symbol[k],s[3]); created = cstr; ret.push_back(created); } } } }while(next_permutation(s.begin(),s.end())); return ret; } int main() { string in; while( getline(cin,in) ) { if(in == "0 0 0 0") { break; } vector<string> vs = createStrComb(in); for(int i=0; i<vs.size(); ++i) { if(calcStr(vs[i]) == "10") { cout << vs[i] << endl; break; } else if(i==vs.size()-1) { cout << 0 << endl; } } } return 0; }
AOJ0037
問題:Path on a Grid
グリッド上の壁情報を与えられ，初期位置から右手づたいに進んでいき，初期位置まで帰ってくるまでの移動方向を出力する問題．
壁情報を配列で扱いやすいよう整理し，それをたどればOK.
自分はサンプル入力の
1111
00001
0110
01011
0010
01111
0010
01001
0111
これを
00000000000
01111111110
00000000010
00011111010
00010001010
00010111010
00010101010
00010111010
00010000010
00011111110
00000000000
のようにして配列に格納しています.
#include<iostream> #include<string> #include<vector> using namespace std; static const int X = 11; static const int Y = 11; static const int DIR = 4; static const string dirchar= "RDLU"; static const int dirx[DIR] = {1,0,-1,0}; static const int diry[DIR] = {0,1,0,-1}; int main() { int field[X][Y] = {0}; string s; int x,y; y=0; while( getline(cin,s) ) { for(x=0;x<s.size();++x) { field[x*2+1][y+1] = s[x]-'0'; } y++; } //横情報を右に引き延ばし for(y=1;y<Y;y+=2) { for(x=1;x<X;x+=2) { if(field[x][y]) { field[x+1][y] = 1; } } } //縦情報を上下に引き延ばし for(y=2;y<Y;y+=2) { for(x=1;x<X;x+=2) { if(field[x][y]) { field[x][y+1] = 1; field[x][y-1] = 1; } } } //field上の１をたどっていく vector<int> ans; x=y=1; int dir=0; while(true) { for(int i=0; i<DIR; ++i) { const int tdir = (dir+DIR-1+i)%DIR; if( field[x + dirx[tdir]][y + diry[tdir]] ) { //fieldを2倍に引き延ばしてるので2マスずつ移動 x += dirx[tdir]*2; y += diry[tdir]*2; ans.push_back(tdir); dir = tdir; break; } } if( x==1 && y==1 )break; } //解答出力 for(int i=0;i<ans.size();++i) { cout << dirchar[ans[i]]; }cout << endl; return 0; }
SRM531
div2-mid
めもめも
#include<iostream> #include<algorithm> using namespace std; class NoRepeatPlaylist { public: int numPlaylists(int N, int M, int P) { long long dp[105][105] = {0}; dp[0][0] = 1; for(int i=1; i<=P; ++i) { for(int j=1;j<=N;++j) { dp[i][j] += ( dp[i-1][j-1]*max(N-(j-1),0) + dp[i-1][j]*max(j-M,0) ) % 1000000007; } } int result = dp[P][N]; return result; } };
第22回高専プロコン競技部門参加記
12月22日から2日間にわたって開催された全国高等専門学校プログラミングコンテストの競技部門に参加してきました．
結果は準決勝敗退という悪い成績でした（人権ない）．
今回の府立高専の方針と敗因について書いていきたいと思います．
・方針
1.問題の読み込みと差分画像（初期画像と最終画像のxor）を生成する．
2.スタンプのすべての押し方を試し，そのテーブルを生成する．
3.１ｘ１のスタンプを用いて自明な解を生成する
4.解からある矩形範囲に影響のあるスタンプの適用を取りだす．
5.4で取り出したスタンプをランダムで数個取り出し，全て0の画像に適用する．
6.5で生成した画像を新たな問題だと思って貪欲法で解き，短い手数になっていればこれを置き換える．
7.4〜6を時間が許す限り繰り返す．
これだと局所解に落ちるのは目に見えてるので，4〜6は別スレッドで別々に行い，1周するごとに解を併合している．
取り出すスタンプの範囲はスレッドで別々にし．画像の左上から順に少しずつずらしている．
＜解の併合について＞
2つの解をそれぞれ解１、解２とし，併合した解を解３とする．
1.解１，解２に共通するスタンプの適用を解３に追加する．
2.解１から解３に含まれている物を取り除く．解２についても同様にする．
3.解１から適当に１つのスタンプの適用を取り出す．
4.取り出したスタンプの適用に影響のあるスタンプの適用を解１と解２から取り出す．
5.4を繰り返し，取り出すスタンプがなくなったら取り出した個数の少ない方を確定し解３に追加する．
6.解１，解２が空になるまで3〜5を繰り返す．
幅優先チックな解のマージ方法です．割と良い感じに解をマージできます．
・敗因
上で示した方針は，最初に最低限の解を出力し，時間が立つに連れて良い解に収束していくけれど，競技時間が予想よりかなり短かい上に問題サイズが大きくて，解が収束する前に競技が終わってしまいました．
貪欲法で上から順に確定するだけの方が時間内に良い解が出せたようです．
競技終了後，優勝の久留米高専のチームにお話をする事ができました．
アルゴリズムや高速化の話が聞けたり，ソースを少し見せてもらった，レベルの違いに驚かされるあまりでした.
自分は今年で最後ですが，久留米高専の彼らは来年も出場するそうです．
来年もアルゴリズムの問題だったら久留米高専が強豪になることは間違い無いでしょう．
府立高専の後輩たちは，直前まで何もしない癖を何とかしましょう..orz
エクストリーム就職活動
忙しすぎて備忘録を忘れていたがぁ君です．
前回面接を受けさせて頂いたＩＴ企業，
なかなかハードなスケジュールだったのですが，インターンシップを経て内定をいただきました．
インターンではとても濃密な１週間を過ごさせて貰いました．
許可も一応貰ったので，今回はそのインターンシップについてグダグダ書いていこうと思います．
企業名は働き始めるまでは伏せておきます．
期間は通常2週間．
なぜか自分の場合1週間で，4日目に成果発表プレゼンがあるため作業出来るのは実質3日．
勤務時間は9:30〜18:30なのですが，9:30に来てもほとんど誰も居ませんし，18:30になってもほとんど帰りません．（すばらしい）
交通チケット・宿手配，昼食代まで出して貰って，
インターン期間中に取り組む内容は自分で決めることができます．（すばらしい）
新しい技術や発想が好まれるようですが，メンターの方との合意が取れれば本当に何でも良いみたいです．
自分は３Ｄなテトリスを作りました．
また，大学3回生や高専4年生等学年を限定している訳でもなく，意思とそれなりの実力があれば参加可能なようです．
実際，大学院へ進学が決まっている大学4回生の方がインターンに来られていて，同じ机で作業し成果発表も一緒に行いました．
昼食はメンターの方と他数人で一緒に食べに行くことになっています．
東京の昼食代（ハンバーガー1200円とか）ぱない．
ここで飛び交う会話のレベルもぱない．ついていけないどころか半分程度しか理解出来なかったorz
また，定期的に行われている勉強会にお誘い頂き，情報のような数学のような内容勉強しました．
疲れたを頭フル回転しながら頑張って理解しようとしてました，がこれも「だいたいこういうこと言ってるんだろうな〜」程度しかorz
大学への進学が諦めきれず，とりあえず就活という感じでここまで来ていましたが，社員の方々のレベルと向上心の高さに圧倒され，
とんでもない所に来てしまったという感じと同時にこの職場で働きたいと思い始めました．
3日目終わる頃には当初予定していた機能の8割は実装完了し，なんとか人に見せれるレベルにはなった．
しかし4日目はプレゼン資料の作成に思いの外時間を取られてしまって，結局そのまま成果発表．
成果物は後日どこかにアップロードする予定．
成果発表で工夫した点や反省点などを発表した後，自分では気づけなかった所，勘違いしていた所をたくさん指摘して頂きました．
一緒だったインターン生と再開を誓いお別れ．
その後もう一度面接をして頂き，インターンの感想と今の自分の心境を伝えた所，その場で内定が決まりました．
学生のうちに取り組んでおく事，これから意識すべき事などについて少し相談．
実は明日が内定式なんだよね！とかいうサプライズが用意されてて吹き出しそうになった．
この日は早めに宿に帰り荷物をまとめた後，東京夜の街をひとり歩きしてお酒飲んだりした．
内定式後のパーティで酔って社員のおじさん（50代くらい）とハグした記憶が////////////////
GoogleCodeJamJapan予選
参加しました.
13時開始で,14時頃に外出しなければなかったという事件（参加登録してから気づいた）
問題はABCの3種類,それぞれにSmallとLargeという2つの制約があり,愚直に書くとSmallは解けるがLargeは一捻りいる感じ.
ただし,Largeはコンテストが終わるまで正解か分からない.
3問中1問でもLargeが解ければ決勝に出場出来るらしい.
気づくと13時15分になってたので慌てて参加.
Aを見て問題を理解するも,Largeが解ける解法を思いつかなかったのでパス.
Cを開く,問題理解
数字Nが与えられ,a+b=Nを満たすa,bの1のビット数が最大となるとき1のビット数を答える問題.
紙の上で1から6まで解答してみる.
全てのビットが１の数(2^n-1)のうち,N以下で最大の物と,残り.で解けそうな気がする.
サンプルのケースで実験も出来るだろうという甘い考えの元,ダラダラと書く.
#include <iostream> using namespace std; typedef unsigned long long uint; int bitCount(uint x){ int count = 0; for(uint mask = 1; mask != 0; mask <<= 1) { if( (x & mask) != 0 ) count += 1; } return count; } int main(){ uint n,t; cin >> t; for(int i=0;i<t;++i){ cin >> n ; uint k=0,j; while( ( n > (((uint)1<<(++k))-1) ) ); k-=1; n -= (((uint)1<<k)-1); k += bitCount(n); cout << "Case #" << i+1 << ": " << k << endl; } }
1のビット数を数えるのにstd::bitsetが使えそうなのは知ってたけど,使った事なかったのでヤメ.
「ビット数 数える C言語」とかいうナメたワードでググッて見つけたソースをコピペしてちょいちょいと書き換えた.
サンプル合った.
Small正解.
Large提出.
この時点で14時前だったので，Aを愚直に書いてみたりしたがサンプル合うのにSmall通らなくて涙目．
時間過ぎてたのでしぶしぶと外出．
後々確認してみるとC-Large通ってたようで良かった．
542位という素晴らしい成績で決勝進出のようです．
Tシャツ欲しいよ！
