CODE FESTIVAL 参加記
CODE FESTIVALに参加しました 超楽しかったので色々書きます
(色々なことがありすぎたので、少し長めです。)
こどふぇす0日目
前泊が許されたので朝9時頃に出発した。新幹線の領収書を貰いそびれたりなんやしながら上野駅へ。
ひとまずホテルに荷物を預けて、お昼ごはんに黒いカレー(キッチン南海 本店 | カレーデータベース)を食べた。午後3時なのに人が数人並んでいて驚く
秋葉原でぶらぶらした後、Twitter経由で集まった@LazyMiiさんと@diginatuさんとつけ麺を食べ、その後2,3時間「vimは是非使うべし」とか「TopCoderがほげほげ」とかいう話をした(とっても楽しかったです ありがとうございます!)
ホテルについた頃には眠かったのですぐ寝た
こどふぇす1日目
会津の人たちに金魚のフンしながら会場に到着
Tシャツをもらったりコンテンツをチラ見しながら「金ぽよだー」とか思う
コンテスト始まるまでは、だらだらとTwitterを見てた。@konjo_pさんが近くだったのでこんにちわした。
コンテストのABCDはやるだけ、Eはdpがんばるだけ・・・だったのに、CDEが解けなかった。以下言い訳
Cは謎の実装が重い嘘方針で1時間かけて書く→いくつかWAが生える→方針を変える→焦りでバグバグする→ループの範囲ミスに気づかないまま死
Dはいわゆる誤読、「入力した数が出現する初めの段を出力する」とかいう制約を勝手に作って死、おしまい。
方針ミスとかに気付いて焦ると当社比0.5倍未満の強さになるらしい、強く生きよう。
この時点で半泣きだったけど、せっかくのお祭りなので ちょくだいさんのアルゴリズム擬人化、にくならずLT、not幾何プロLTを見に行った。
ビームサーチはコスプレ少女、目の下はツラミ、幾何は回すだけ などを覚えた(?)
そして最後に、1日目で実は一番盛り上がったイベント 本戦上位5名が出場するエキシビジョンマッチがあった。
自分は見るだけのイベントなのにものすごく盛り上がり、超難問の1つを10分でACするという圧倒的な強さ、深い考察をものの数分で紙にまとめられる思考力の高さ、問題を見て使用するアルゴリズムを決定するまでの驚異的な速さを目の当たりにすることができたことにずっと感動してた。
どれも僕からみると超人的で、見てるだけなのにものすごく感動した。やっぱり競技プログラミングが強い人は格好良いなぁ
この日も帰ったら眠かったのですぐ寝た
こどふぇす2日目
起床フェイズをクリアし、9時からのあさプロEASY*1に無事参加できた
やるだけのABを解き、Cを見ると最短経路系だけどワーシャルフロイドでは間に合わなさそう。蟻本をみながら両側からダイクストラして無事遅めの3完。
EASY 11位 /50人 だったので銀缶バッチをもらえた。ちょっとだけ嬉しい
ちょくだいさんのトーク、秋葉さんのトーク、いもすさんのトークを聞く。あの秋葉さんに会えた上に蟻本にサインをもらった!神!
次にリレー形式のプロコンをやった。僕はほとんど活躍できなかったけど、くりんぺさんやJAPLJさんとチームが組めて楽しかった(小並感
そんなこんなでいつのまにやら閉会式。つねならずさんとトイレ5個さんが泣いてて、なんだかしんみり。。。
200人とスタッフの方全員で写真撮影してついに解散
最後に@diginatuさんと東京駅でカレーを食べ、別れを惜しみながら帰ってきた。こどふぇす終わっちゃうの寂しいよぉ
まとめ
- 問題はよく読む。誤読超つらい
- 最低限のアルゴリズムくらいはちゃんと使えるようにして、競プロつよくなる
- ぼっち参加だったけど沢山の人とお話できて楽しかった
- CODE FESTIVAL神イベントだった。またあれば何度でも来たい
*1:本戦の順位によって出る難易度が変わる。僕はEASYだった。
お祭り終わり
コードフェスティバル雑感
この2日間、時間があっという間に過ぎた
思い返すとすごくすごく長かったような気がしてくる
全部のコンテンツが楽しくて途中からよくわかんなくなってた
絶対にまた行きたい
あしたがっこういきたくない
続きははまた今度書く
Mac環境へのNLTK0.7の導入(OS X Yosemite 64bit)
O'Reilly Japan - 入門 自然言語処理に記載されているプログラムを動かすため、MacBookAirにNLTKとNumpyを導入しました。
英語をテキトーに読んでるといろいろ手間取ってしまった
使用した環境
- MacBook Air (11-inch, Early 2014)
- MAC OS X Yosemite バージョン10.10
- python2.7.6
手順
1.Setup toolのダウンロード
- 一番下の方までスクロールしてグレーの表を見つけ、setuptoolをダウンロードする(今回はsetuptools-7.0.zipを選択したが、多分好きなやつでいい)
- ダウンロードが完了したら解凍する
2.Pipのインストール
- ターミナルのアプリケーションを起動し、先ほどのファイルを解凍後にできたファイルへ、cdコマンドを利用して移動する(例:「cd /Users/USER_NAME/Downloads/setuptools-7.0」)
- 「sudo easy_install pip」コマンドを実行する
5.Test installation
何もエラーがでなければ恐らくインストールは成功、”ImportError: No module named nltk”といったようなエラーが出た場合は手順を間違えているか、私の実行環境とは異なる可能性がある。
6.bookデータをダウンロードする
- 「nltk.download()」コマンドを実行する
- 以下のような画面が開くので、bookを選択し、左下のDownloadボタンを押す(この画像はbookをダウンロード後の画像なので、Statusがinstalledとなっている点は気にしなくて良い)
eclipseからJavaでMeCabを利用するためにバインディングを行った記録
Javaから形態素解析エンジンであるMeCabを利用したいと考え調べたところ、Javaバインディングが存在するとのことで導入を行った。
結構いろんなところでハマったので、メモっておく。
設定の際は、このサイトを参考にした。
Twitterから取得した「つぶやき」を品詞に分解する - 放浪するエンジニアの覚え書き
手順
1. 本家のサイトからMeCab本体をインストールする。
2. 本家のサイトからMeCab 用の辞書をダウンロードし、解凍する。
3. 本家のサイトからJavaバインディングをダウンロードし、解凍する。
4. 解凍したファイル内のMakefileを以下のように書き換える(パスなどの条件が各自異なるはずなので、同じものを利用しても実行できない可能性がある)。
TARGET=MeCab JAVAC=javac JAVA=java JAR=jar CXX=c++ INCLUDE=/System/Library/Frameworks/JavaVM.framework/Headers PACKAGE=org/chasen/mecab LIBS=`mecab-config --libs` INC=`mecab-config --cflags` -I$(INCLUDE) -I/Library/Java/JavaVirtualMachines/jdk1.8.0_20.jdk/Contents/Home/include -I/Library/Java/JavaVirtualMachines/jdk1.8.0_20.jdk/Contents/Home/include/darwin all: $(CXX) -O3 -c -fpic $(TARGET)_wrap.cxx $(INC) $(CXX) -shared $(TARGET)_wrap.o -o lib$(TARGET).so $(LIBS) $(JAVAC) $(PACKAGE)/*.java -J-Dfile.encoding=UTF8 $(JAVAC) test.java -J-Dfile.encoding=UTF8 $(JAR) cfv $(TARGET).jar $(PACKAGE)/*.class -J-Dfile.encoding=UTF8: test: env LD_LIBRARY_PATH=. $(JAVA) test clean: rm -fr *.jar *.o *.so *.class $(PACKAGE)/*.class cleanall: rm -fr $(TARGET).java *.cxx
5. Makefileと同じ階層で「sudo make」を実行する
6. 上の手順によってMeCab.jarとlibMeCab.soが生成される
7. MeCab.jarをeclipseに取り込む
※参考:クラウドサービスプラットフォーム Cosminexus:Eclipse プロジェクトのビルド・パスへライブラリーを追加するには?:ソフトウェア:日立
ハマったところ
以上で導入は完了だが、Makefile内の「INC=`mecab-config --cflags` -I$(INCLUDE) -I$(INCLUDE)/linux」の部分を、
「INC=`mecab-config --cflags` -I$(INCLUDE) -I/Library/Java/JavaVirtualMachines/jdk1.8.0_20.jdk/Contents/Home/include -I/Library/Java/JavaVirtualMachines/jdk1.8.0_20.jdk/Contents/Home/include/darwin
」のように変更しなければmakeできなかった。
これがないとjni.hがみつからず 「jni.h' file not found」といったエラーが出る。
なのでjdk内の、jni.hが保管されているディレクトリとjni_md.hが保管されているディレクトリのパスをここに記載する必要があるらしい。
これに気づくのにかなりの時間を要したが、なんとか正常にeclipseからMeCabを利用することができた。めでたしめでたし。
SRM628 div2
昨日SRM628がありました。627は寝過ごしするめだったので、結構久しぶりの参加でした。
結果はeasyのみの1完でした。medやり直したので保管しておきます。
easy
ビショップ(将棋の'角'みたいな動きするらしい)が、8*8の盤上の座標(r1,c1)から(r2,c2)に移動するための手数を求める、移動出来ない場所は-1を返す。
座標の差とか計算してごにょごにょと場合分けして解いた。
challengeの時に見たら、長くて難しそうなプログラム作ってる人もいた。
using namespace std; typedef long long ll; #define rep(i,n) for(int i=0;i<(n);i++) class BishopMove { public: int howManyMoves(int r1, int c1, int r2, int c2) { if(r1==r2&&c1==c2){ return 0; } else if(abs(r1-r2)==abs(c1-c2)){ return 1; }else if((abs(r1-r2)+abs(c1-c2)) %2 !=0){ return -1; } else return 2; } };
med
「'(',')','{','}','[',']','X'」といった、3種類の開き・閉じ括弧と'X'で構成された50文字以下の文字列が与えられる。また、'X'の数は5個以内である。'X'はワイルドカードで、任意の括弧に置き換えることができる。
以上の条件を満たした括弧を消去していき、入力された文字列全て消せるならば"possible"を、ダメなら"impossible"を返す。
(ex: "{()}[]"->"possible" "{(X}"->"possible" "[(]]"->"impossible")
深さ優先を使って'X'を6種類全ての括弧に変化させてシュミレーションする。変換候補は6種類なのでO(6^n)となる。nは5以下なので余裕で間に合う。
using namespace std; typedef long long ll; class BracketExpressions { public: string del(string s){ string ret=""; for(int i=0;i<s.size()-1;i++){ if( (s[i]=='(' && s[i+1]==')') || (s[i]=='[' && s[i+1]==']') || (s[i]=='{' && s[i+1]=='}')){ s[i]='a'; s[i+1]='a'; } } for(int i=0;i<s.size();i++) if(s[i]!='a') ret+=s[i]; return ret; } string Do(string s){ string bef; do{ bef=s; s=del(s); }while(s.size() && !(bef==s)); return s; } bool flag=false; void dfs(int n,string now,string s){ if(now.size()==s.size()){ if(Do(now).size()==0)flag=true; return ; } if(s[n]=='X'){ dfs(n+1,now+'{',s); dfs(n+1,now+'[',s); dfs(n+1,now+'(',s); dfs(n+1,now+'}',s); dfs(n+1,now+']',s); dfs(n+1,now+')',s); } else{ dfs(n+1,now+s[n],s); } return ; } string ifPossible(string expression) { string s=expression; dfs(0,"",s); if(flag)return "possible"; else return "impossible"; } };
まとめ
- medでアルゴリズムを要求されることは少ないと思っていたので、「greedyなんだろうなぁ」と決めつけてしまっていた。前もdpとか出てたし、そんなことはなかった。
- 今回翻訳サイトに頼らず解いてみたら、medの「'X'は5以内」の制約などにしっかり気付けた。誤読多いからこれからは自力でやる
- dfs書いたら一発でACしたのが嬉しかった、dfs力の高まりを感じる・・・
- 本番ではmed解けなかったのにYazaten->Yazatenになってしまった。これからはちゃんと解いてレート上がるように頑張りたい。
ICPC2014-A,B,D問題解いたやつ
Input/output data of domestic contest is now available. 国内予選の入出力データを公開しました。http://t.co/9aJSfoqTFm
— ICPC2014JP (@icpc_tokyo2014) July 16, 2014
とのことでした。
diffをとったら合ってたっぽいので、いまさらですがここに保管しておくことにします。
ちょろっと書いてある問題概要はおおまかなことしか書いてないのでここ(http://icpc.tanaka.ecc.u-tokyo.ac.jp/icpc2014/contest/all_ja.html)参照。
problemA--税率変更-- (AOJ1192)
税込み価格で全探索し、「その税込価格になりえない税込価格」の場合は除外した。
税抜で全探索した人の方が多かったようなので、方針ミスっぽい。
#include <iostream> using namespace std; int main(){ while(1){ int x,y,z; int ans; cin>>x>>y>>z; if(x==0 && y==0 && z==0)break; int maxi=-1; int nukia,nukib,komia,komib; for(int i=1;i<=z/2;i++){ for(int j=z-1;j>=1;j--){ if(j*(100+x)/100==i){ nukia=j; break; } } for(int j=z-1;j>=1;j--){ if(j*(100+x)/100==z-i){ nukib=j; } } int a=nukia*(100+x)/100; int b=nukib*(100+x)/100; if(a+b!=z)goto skip; komia=nukia*(100+y)/100; komib=nukib*(100+y)/100; maxi=max(maxi,komia+komib); skip:; } cout<<maxi<<endl; } return 0; }
problemB--連鎖消滅パズル-- (AOJ1193)
消滅は横方向のみで、フィールドの横の長さが5固定・縦の長さが1~10で可変であるパズドラ。
バグらせないようにやるだけ。
#include <iostream> #define EMP -1000 using namespace std; int stage[11][11]={}; int h; void outStage(){ for(int i=0;i<h;i++){ for(int j=0;j<5;j++){ cout<<stage[i][j]; } cout<<endl; } } bool delStage(){ bool conti=false; for(int i=0;i<h;i++){ for(int j=0;j<3;j++){ int samecount=1; int now=-1; for(int k=0;;k++){ if(now==-1){ now=stage[i][j+k]; } else if(now==stage[i][j+k] && now!=EMP){ samecount++; } if( (now!=-1 && now!=stage[i][j+k]) || k==4){ if(samecount>=3){ conti=true; for(int l=0;l<samecount;l++){ stage[i][j+l]=EMP; } samecount=1; } goto end; } } end:; } } return conti; } void downNum(){ for(int t=0;t<h;t++){ for(int i=1;i<h-t;i++){ for(int j=0;j<5;j++){ if( i-1>=0 && stage[i][j]==EMP){ swap(stage[i][j],stage[i-1][j]); } } } } } int countScore(){ int sum=0; for(int i=0;i<h;i++){ for(int j=0;j<5;j++){ if(stage[i][j]!=EMP) sum+=stage[i][j]; } } return sum; } int main(){ while(1){ int sum=0; cin>>h; if(h==0)break; for(int i=0;i<h;i++){ for(int j=0;j<5;j++){ cin>>stage[i][j]; sum+=stage[i][j]; } } //end input; while(1){ if(delStage()==false)break; downNum(); } cout<<sum-countScore()<<endl; } return 0; }
problemD--暗号化システム-- (AOJ1195)
アルファベットからなる20文字以下の文字列を先頭から見ていき、そのアルファベットが1度目の出現であれば一つ小さくする(ex: b->a , z->y)というガバガバな方式で暗号化された文字列の、変換前文字列の候補を列挙する。
それぞれのアルファベットにつき最大でも2通りしか無いので、最大で2^20回試行となり間に合う。
先頭から順に確定させていき、今見ているアルファベットが「暗号化前文字列にすでに出現しているか、'a'」であればそのまま暗号化前文字列につっこみ、「暗号化前文字列にまだ出現していない、かつ'z'ではない」であれば一つ大きくしたアルファベットを暗号化前文字列につっこむ。
みたいなことを幅優先探索でやって解いた。
これでやると自然に辞書順にソートされるのでソートは不要となり、オーダーはo(2^n)となる。
ソートが必要となるとo( 2^n + (2^n)log(2^n) )となるので(ICPC以外では)ちょっとヤバそう。
よくわからないのでまたAOJに入ったら投げてみよう。
※追記:0.02sで通りました。やったぜ!
#include <vector> #include <iostream> using namespace std; vector<string> ans; bool ap[30]; string s; int sum; void dfs(int n,char c,string now){ //cout<<"dfs(int "<<n<<",char "<<c<<",string "<<now<<")"<<endl; if(n==s.size()){ sum++; ans.push_back(now); return ; } if(ap[c-'a']==true || c=='a'){ bool bac=ap[c-'a']; ap[c-'a']=true; dfs(n+1,s[n+1],now+c); ap[c-'a']=bac; } if(ap[c-'a'+1]==false && c!='z'){ bool bac=ap[c-'a'+1]; ap[c-'a'+1]=true; dfs(n+1,s[n+1],now+(char)(c+1)); ap[c-'a'+1]=bac; } } int main(){ while(1){ while(!ans.empty())ans.pop_back(); sum=0; cin>>s; if(s=="#")break; dfs(0,s[0],""); cout<<sum<<endl; if(sum<=10){ for(int i=0;i<sum;i++){ cout<<ans[i]<<endl; } } else{ for(int i=0;i<5;i++){ cout<<ans[i]<<endl; } for(int i=ans.size()-5;i<ans.size();i++){ cout<<ans[i]<<endl; } } } return 0; }
おしまい。
C++ classのプロトタイプ宣言
「あるclass内の関数で、別のクラス型の引数を取る」ということを相互に行ったことで、コンパイルが通らなかった。
C++で
class A{ hoge(B b) };
class B{ fuga(A a) };
ってすると、Aのclassの方で「B がまだ定義されてませんし」って言われる
— やざてん (@Yazaten) 2014, 7月 19
クラスのプロトタイプでググってるけど分からなくてくじけそう
— やざてん (@Yazaten) 2014, 7月 19
みたいなことを呟いたら「クラスのプロトタイプを宣言して、うまいことやればできる」という事を教わったので書いておきます。
@Yazaten 順番の問題で, http://t.co/JDdh7E8ZWq のようにすれば通ります.
— 102 (しばらく増えなかったら煽って) (@Mi_Sawa) 2014, 7月 19
元のコード(コンパイル通らなかった)
class A{ void hoge(B x); }; void A::hoge(B b){} class B{ void fuga(A a); }; void B::fuga(A x){} int main(){return 0;}
変更後のコード(コンパイル通るし、ちゃんと動く)
class B; class A{ void hoge(B x); }; class B{ void fuga(A a); }; void A::hoge(B b){} void B::fuga(A x){} int main(){return 0;}
フォロワーさん超ありがとうございました。