思い出の問題を解いた
ICPC2013国内予選Cの 階層民主主義 ( Hierarchical Democracy | Aizu Online Judge )を解きました。
2013年7月 ICPC国内予選
興味本位で出たICPC国内予選でこの問題を読み、全くもって意味がわからなかった。*1
当時は プログラミングチョットデキル と天狗になっていただけに衝撃で、なんかもやもやしたので競技プログラミングを始めることにした
問題について
問題概要は省略。
解いてからググったら深さ優先でやるのが一番スマートみたいだったけど、思いつかなかったからゴリ押しで地獄のようなコードを書いた。ゴリ押しの手順を以下に雑に示すが、おそらく読む価値はない。※括弧内は一例
- はじめ ( [[[1][3][5]][[11][9][7]][[15][17][13]]] )
- "]["を" "に置き換える ( [[[1 3 5] [11 9 7] [15 17 13]]] )
- 一番深い階層の選挙区それぞれを有権者数でソートする ( [[[1 3 5] [7 9 11] [13 15 17]]] )
- それぞれの選挙区で勝つために必要な票の最小を求め、置き換える ( [[3] [9] [15]] )
- 空白をつめる ( [[3][9][15]] )
- 2~5を繰り返し、'['や']'が無くなったらそのときの結果を出力する ( [[3][9][15]] → [[3 9 15]] → [12] → 12)
手もつけられなかった問題が、ゴリ押しではあるが一応通せるようになって少しうれしい。
string pre(string s){ // "][" を空白に置き換え
string b="";
rep(i,s.sz-1){
if(s[i]==']' && s[i+1]=='['){
b+=' ';
i++;
}
else{
b+=s[i];
}
}
b+=s[s.sz-1];
return b;
}
string solve(int n,bool check,string s){
n++;
string tmp[10000]={};
int count=0;
REP(j,n,s.sz){
if(s[j]!=']'){
if(s[j]!=' '){
tmp[count]+=s[j];
}
else{
count++;
}
}
else break;
}
vi a;
rep(i,count+1){
a.pb(stoi(tmp[i]));
}
sort(ALL(a));
int sum=0;
rep(i,count/2+1){
if(check==false)
sum+=a[i]/2+1;
else
sum+=a[i];
}
return to_string((sum));
}
string delSpace(string s){ // "] [" を "][" に置き換え
string ret="";
rep(i,s.sz-2){
if(s[i]==']' && s[i+1]==' ' && s[i+2]=='['){
ret+="][";
i+=2;
}
else{
ret+=s[i];
}
}
ret+=s[s.sz-2];
ret+=s[s.sz-1];
return ret;
}
int main(){
int t;
cin>>t;
rep(times,t){
string s;
cin>>s;
int check=false;
s=pre(s);
while(1){
if(s.find("[",0)==-1)break;
string n="";
rep(i,s.sz){
if(s[i+1]>='0' && s[i+1]<='9'){
n+=solve(i,check,s);
while(s[i]!=']')i++;
}
else{
n+=s[i];
}
}
s=n;
check=true;
}
cout<<s<<endl;
}
return 0;
}
*1:A問題とB問題は一緒に出ていた先輩が解きました。
CODE FESTIVAL 参加者の参加記一覧
たくさん参加記読みたいし、需要もあるっぽいのでつくった
(togetter版はこっち CODE FESTIVAL 参加記まとめ - Togetterまとめ)
参加記収集アルゴリズム
これに引っかからなかった場合、ここにまとめられていない可能性が高いです。
- 「("code" "festival”) OR "codefestival" OR "コード祭" OR “こどふぇ” OR “謎コン” OR "こどふぇす" OR "コドフェ" OR "コドフェス"」の検索結果のうち、"http"を含むツイートをTwitter4Jで拾ってくる(150ツイートくらい引っかかった)
- それぞれツイート読んで、参加記っぽいやつを絞り込む
- URLに飛んでみて、非公開でないブログであればここにまとめる
参加記
記事内にコードを含むものと、含まない(参加記っぽい)もの に分けました。
参加記っぽいブログ
コードの割合が高いブログ
参加記が増えているのに気付いたらまた更新するかもしれません。
Yosemite で MinecraftとかArduino IDEとかが起動できなかった
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を利用することができた。めでたしめでたし。
