お祭り終わり
コードフェスティバル雑感
この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;}
フォロワーさん超ありがとうございました。
ぼくの二度目のICPC
追記:A,B,D問題をときました → ICPC2014-A,B,D問題解いたやつ - あったこといろいろ
僕にとって二度目のICPCが終わりました。僕が競技プログラミングに興味をもったのは去年のICPCからだったので、実は競技プログラミング1週年記念でもありました。
結果をふりかえって
結果は0完でした。過去3度のチーム練習では最低でも1問通せていたし、帰宅後見なおすとすぐにバグが見つかりAとBのサンプルケースは通った。これについてはきっと緊張していたのがよくなかったんだろうなぁ。
アジア予選出場はほとんど諦めていたものの、「2,3完目指そう、あわよくば4完したいね。」くらいの目標はあったのでまさか1問も解けないとは思っていなかった。
コンテストが終了してからはしばらく結果や自分自身に失望していて、監督の先生の問いかけにも多少邪険に対応してしまった。自分勝手で本当に良くなかった。
反省点
- 一度ミスをすると、自分が思っているより焦ってしまう。解く速度が重要とはいえ、「方針を固めてからコードを書き始める」、「間違っていても焦らず冷静に理由を考える」あたりを徹底しなければいけないと感じた。
- 自分がA問題すら解けないのが怖くて、チームメンバーにパソコンを譲らずほとんど独占してしまった。解けないのが嫌なのは当然僕だけではないし、時間がかかりそうなら紙デバッグに早めに移行してパソコンを空けるべきだった。
- 今回一人につき先頭から順に1問を担当する方針を取ったが、解きにくい問題や不得意な問題にうまく対処したり、他人と一緒に解いて考えを聞くのも必要だと思った。チーム対抗コンテストなのだからチーム一丸となって戦うべき。
