C++のupper_bound,lower_boundについて
何度書いても覚えないし,バグって悲しい思いをしたのでまとめることにした.
基本事項
- ソート済みのコンテナに対して呼ぶ.
- ランダムアクセスできないコンテナに対しても呼ぶことができる.
- lower_boundは指定した値以上の先頭の要素を指すイテレータを返す.
- upper_boundは指定した値より大きい先頭の要素を指すイテレータを返す.
#include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { vector<int> v = {0,0,0,1,1,1,4,4,4}; cout << lower_bound(v.begin(), v.end(), 2) - v.begin() << endl; cout << upper_bound(v.begin(), v.end(), 2) - v.begin() << endl; cout << lower_bound(v.begin(), v.end(), 1) - v.begin() << endl; cout << upper_bound(v.begin(), v.end(), 1) - v.begin() << endl; cout << lower_bound(v.begin(), v.end(), 5) - v.begin() << endl; cout << upper_bound(v.begin(), v.end(), 5) - v.begin() << endl; cout << lower_bound(v.begin(), v.end(), -1) - v.begin() << endl; cout << upper_bound(v.begin(), v.end(), -1) - v.begin() << endl; }
実行結果
6 6 3 6 9 9 0 0
比較関数を渡す
operator<として用いる比較関数を渡すことができる.
#include <iostream> #include <vector> #include <algorithm> using namespace std; bool comp(int a, int b) { return a > b; } int main() { vector<int> v = {4,4,4,1,1,1,0,0,0}; cout << lower_bound(v.begin(), v.end(), 2, comp) - v.begin() << endl; cout << upper_bound(v.begin(), v.end(), 2, comp) - v.begin() << endl; cout << lower_bound(v.begin(), v.end(), 1, comp) - v.begin() << endl; cout << upper_bound(v.begin(), v.end(), 1, comp) - v.begin() << endl; cout << lower_bound(v.begin(), v.end(), 5, comp) - v.begin() << endl; cout << upper_bound(v.begin(), v.end(), 5, comp) - v.begin() << endl; cout << lower_bound(v.begin(), v.end(), -1, comp) - v.begin() << endl; cout << upper_bound(v.begin(), v.end(), -1, comp) - v.begin() << endl; }
実行結果
3 3 3 6 0 0 9 9
比較関数の第一引数,第二引数には,upper_bound/lower_boundで指定した範囲,値のどちらも入る可能性がある.(うまく表現できない)
これを知らずに,第一引数に指定した範囲から取った値入れて,第二引数に探す値入れて比較するだろとか適当なこと考えながら書いたらバグって悲しい思いをした.
#include <iostream> #include <vector> #include <algorithm> #include <cstdlib> using namespace std; int N; bool comp(int a, int b) { if(a == N) cout << "first" << endl; else if(b == N) cout << "second" << endl; else cout << "else" << endl; return a < b; } int main() { vector<int> v; for(int i = 0; i < 1000000; i++) v.push_back(i); sort(v.begin(), v.end()); N = 1346; lower_bound(v.begin(), v.end(), N, comp); cout << endl; upper_bound(v.begin(), v.end(), N, comp); }
実行結果
second second second second second second second second second second second second second second second second second second second first first first first first first first first first first first first first first first first first first first first first
備忘録的記事：vimでファイルの種類ごとに設定を分ける方法について。
vimでファイルの種類ごとに設定を分けるのには定石があるらしい。設定を進めていくなかで困ったことに出会ったので備忘録的に。
ファイルの種類ごとに設定ファイルを作り、~/.vim/ftplugin/ に置くのが定石らしい。設定ファイルの名前は hoge.vim (hogeはファイルの種類の名前であり、通常は拡張子) とする。例えば、C言語のソースコード用の設定ファイルはc.vimとする。 ~/.vimrc に
filetype plugin on
の一行を書いて設定終わり。
TeXのソースファイルを開くときに困った話.
vim hoge.tex
などとして起動するとtex.vimに記述した設定が反映されない。これは、.texが複数の種類のファイルの拡張子であることが理由らしい。この類いのファイルを開くときはvimのファイルの自動判別がうまく働かないことがあるらしい。ここ(http://vimdoc.sourceforge.net/htmldoc/filetype.html#ft-tex-plugin)を参照しながら、~/.vimrc に
と書くとうまくいく。
AOJ Volume1 全埋め終わりました
本日16:22頃、AOJ0132:Jigsaw Puzzle をACしてAOJ Volume1が終わったので記念に記事を書きます。
今までに埋めた問題が267問で、このうち200問がVolume0, Volume1に含まれる問題です。Volume0全埋め達成が2013年の10月15日。Volume1埋めるのに1年ちょっとかかってしまいました。今年のうちにVolume1が埋まってしまって良かったです。
Volume1はPCKの問題なので例によって実装が辛い問題が結構あります。アルゴリズム的には蟻本のbitDPの章までの知識で解ける問題しか入っていないので、そのぐらいのレベルの人が埋めるにはちょうどいいVolumeだと思いました。Volume1で特に辛い問題はAOJ0132:JigsawPuzzleとAOJ0182:Beakerの2問なので、この2問は解けないと思ったら後回しにするのが吉だと思います。
次はVolume2埋めなのですが、これはVolume5埋めと並行しようかなと思ってます。競技プログラミングが嫌いにならない程度にのんびり埋めていきます。ICPCメインで対策しないといけないはずなんですけどね、本当は。
CODE FESTIVAL 2014 参加記
乱文・長文注意。
CODE FESTIVAL2014に参加してきました。オンサイトコンテストに参加するのはJAG合宿以来で三度目です。
CODE FESTIVAL予選前
CODE FESTIVALが開催されるらしいという情報が出たのは夏休み突入前で、交通費全額支給+本選人数200名というコンテストが開催されるらしいという話が出た時点でtwitterはお祭り騒ぎでした。twitterで「ある程度のレベルがあるプログラミングサークルは部員旅行に連れて行ってもらうぐらいな気分でいい」という話があったので、自分の所属するプログラミングサークルの夏休みの活動目標にCODE FESTIVAL予選通過が設定された。
CODE FESTIVAL予選
予選A104位通過。D問題の満点解法が貪欲だろうという検討はついたが、解法を詰めるのに時間がかかりそうだったのでさっさと部分点を取りに行った。Dの満点解法を実装しようとして初期化ミスでprintf消すと動かない事案を踏んで1時間つぶしたのは悔しかった。結局330点だった。
予選Bは全完で56位。私は実装苦手な人間なのでDの部分点までに時間をかけすぎてDの満点を取るまで散々な順位だった。とりあえず予選Bでも予選通過順位に入れたので良かった。
ちなみに、所属しているプログラミングサークルの部員で、予選に参加した人は8割くらい通過していた。リクルートさん部員旅行ありがとうございます。
CODE FESTIVAL前日
3限の講義が終わって東京へ出発。前泊の宿泊費も持ってくれるとはリクルート社恐るべし。本選参加前アンケートで保安検査場の通過やら手荷物の受け取りやらを考慮したら最短で3時間以上かかるな。という感じだったが、実際には会場近辺のホテル到着まで4時間以上かかった。前泊申請しといてよかった。
R&Bホテル上野広小路に宿泊だった。明らかにCODE FESTIVAL参加者だなという人たちが居る。しかしコミュ障をこじらせてどうこう。
JAG夏合宿のときもそうだったが、競プロ勢というのは一目でそれとわかる独特の雰囲気を持っているらしい。
CODE FESTIVAL一日目
本選前
受付に立っていたのがJAG合宿でチームを組ませてもらったyuustiさんで「あっ」という感じになる。交通費精算の書類に判子を押したあと、CODE FESTIVAL Tシャツをもらう。初めてのプロコン系Tシャツで嬉しい。6完してパーカー獲得するぞと意気込む。twitterのぞいたら向かいの席にYazatenさんが居ることが分かりお話してた。
開会式
なんか格好良い映像が流れる。twitterではどんだけ金かけたんだという雰囲気に。しかも後援がアカデミック。CODE FESTIVALやべぇという雰囲気になる。indeed社の方がお話を英語でする。英語できないのでtwitterに集合してた。適当に拍手を送る。
開会式終了後、OpenContestとLA賞がらみのルールの穴が突かれる。ルールの穴が仕様になった。
本選
5完で150位でした。D問題ではまった。辛い。B-D問題で1回ずつWAを叩いていて作問者が用意した落とし穴すべてに落ちたり、自分で掘った落とし穴に落ちたりしてた。
A,Bはやるだけ。B問題で制約|S| <= 3000を見て、intに入るな。intで大丈夫と思ったのはダメだった。Sは数字の列でした。Sをstringで受け取り無事AC。これで10分無駄に。
C問題、fが単調増加だったら嬉しいなと思って単調増加であることを示そうとするがうまくいかなかった。小さい数で実験すると単調増加のように見えたので、単調増加と仮定してプログラムを組む。ループまわして確認してみるとfが単調増加だったので提出したらACした。
D問題、はまった。後回し。パスカルの三角形を描いて問題文をよく読むと入力受け取って足し算して吐き出すだけ。この問題のACが142:23。辛い。
E問題。明らかにDP。ぬるっと実装してAC。
私を含む多くの人が解けたのはこの五問。5完が110人ぐらい居た。
5完した時点で残された時間は30分ちょっと。J問題はO(1)解が存在しそうな雰囲気だったので、思いつけば実装は簡単だと判断してJ問題に挑む。結果爆死。
休憩
大学の先輩や同期と、あの問題はああやって解いたとか、パーカー取れなくて悔しいとかそういう話をしていた。近くにkoyumeishiさんを見つけたけど、コミュ障をこじらせてどうこう。
解説
A-D問題はやるだけ的な扱いを受けていた。E問題からちょっと難しくなりますねーみたいなことをちょくだいさんが言ってたけど、個人的にはE問題はB問題の次ぐらいに簡単だったのでなんかなー。小さい例で実験するのは大切だと思い知らされた。F問題の解法を聞いて、JよりFに取り組むべきだった感じもする。
TALK SESSION 01
ちょくだいさんを見に行く。アルゴリズム擬人化の話だった。それなりにぶっ飛んでた。「Brute ForceでTLEしたら実装したお前の責任」らしい。ビームサーチといわれても何のことだか分からなかったけど、説明を受けて再発明したアレだと気付く。ビームサーチなんて名前で呼ばれてたのね。
Food Challenge
ごはんを食べたかったので、FoodChallengeした。診断人さんのニコ生を後日タイムシフトで見て、FoodChallengeしてる場合じゃなかったと思った。FoodChallenge中は同じ大学の先輩や同級生、そしてYazatenさんと本選の感想だったり、AOJの進捗どうですかとかそういう話をしていた。そこにちょくだいさんが現れてお話できて嬉しかった。本選Bで入力間違えてintで受け取ったとかいう話をしたら、sampleに3000を超す入力あったじゃんと怒られた。sampleは注意深く読みましょう。絶対に。
LIGHTNING TALK 01
肉LTと幾何問題の美しい解き方について。肉LTは「肉はアルファベットより数字に拘れ」という話だった。幾何問題の美しい解き方はコンピュータジオメトリに載ってるらしい。
TYPING
LT終わってぶらーっとしてたらTYPINGやってみませんかーと言われてやってみた。ミスタイプでGAME OVERしました。（翌日リベンジ。5分弱でクリアしました。）
エキシビジョン
本選上位者が実況付きでコーディングをするという企画。amylase伯爵の実況・解説もあってとても面白い企画だった。そして、コーディングを眺めながら問題の解説を受けるだけで盛り上がれる観戦者もなかなかだった。準急さんがやべぃ。slが走っていたり、コンテスト中にブログを更新したり、たこ焼きclerを投げたりと、エキシビジョン出場者の遊びも見ていて面白かった。
CODE FESTIVAL二日目
あさプロ
「朝からプロコン」の略らしい。コンテストページには「asa!」の文字列。CODE FESTIVAL 前にはtwitterで「あさプロ（朝までプロコン）」の文字列が流れていたりしたけど、朝までプロコンやってた人居たのかな。朝までプロコンは来年に期待ですね。会場入り口で配られた、チーム対抗早解きリレーのチーム割から、隣の席がichyoさんらしいことが分かる。やはりコミュ障をこじらせてどうこう。
あさプロはeasy, middle, hardの3つのコンテストが存在して、二問づつ問題がかぶっているという説明を受けた。本選150位だったので、middle最底辺として参加。結果は2完の16位でした（大躍進）。参加者のレベルが制限されているとはいえ、AtCoderの順位表一ページ目に名前を載せたのは初めてなので嬉しかった。
あさプロmiddle
A問題は両側からdijkstraやるだけ。類問がQUPCで出てました。QUPCでこの問題の類問を作問してたkyosさんは爆速で提出していたはずである。
B問題は貪欲にやるだけ。ちょっとだけデータ構造の知識が必要。
C問題は本番中に解けなかったのですが、あとから考えてみたら遷移確率行列の積を繰り返し二乗法をつかってとるだけだった。twitterでは誤差どうこう言われてたけど、コンテスト終わって実装した感じだと大して誤差に気を使う必要は無かった。遷移確率行列の考え方は大学の講義で習っていたのに解けなかったのは情けない。情報理論の＊＊先生ごめんなさい。
D問題はDPだったらしい。帰り道、空港まで行く電車の中でDarseinさんに教えてもらった。この日の個別指導塾で「ぽよぽよがN*L*Lで通ったんだけど、、、」という質問が来ていたらしく、Food Challengeしていたらamylase伯爵が個別指導塾のほうに呼び出されていた。
本選でA問題のLA賞狙いに行った同級生のn*kollsonとかいうやつが真面目にやっていれば本選151位でeasy全完（1位）＋middle2完(16位＋）で両入賞だったのになーとぼんやり考える。
TALK SESSION 02
ちょくだいさんと坂本一憲さん（国立情報学研究所助教）のトークセッション。プロコンがらみの雑談で盛り上がったあと、AI Challenge用のAIをペアプロ。次に出す手を選ぶとき、相手が何を出すかの予測を入れるために、次の手を決定する部分を複数回ループさせるというテクニックを学んだ。chokudAI Contestが走っていたり、サーバー落として「これがレッドコーダーの撃墜力だ（ﾄﾞﾔｧ」と言ったりと笑いもあって面白かった。
書道コーディング
面白そうな企画だと思ったので参加。
#defien WA AC
#define TLE AC
#define MLE AC
#define RE AC
と願望を書いた。#define CE ACが抜けていると指摘されたりした。
LECTURE 02
あの秋葉さんのトークということで参加不可避だった。開始時間ぎりぎりに入室した人は立ち見だったので、早めに会場に行っておいて良かったと思った。あきばやばかった。競プロの練習方針について聞けたり、サイン貰えたりしてよかった。匿名質問できる制度大切ですね。
チーム対抗早解きリレー
チーム11(チー無名)で参加。C問題を担当。明らかにO(1)解の存在が見える。チームの人に確認とったところ、自分の見てたO(1)解が嘘だったらしく、別のO(1)解を教えてもらった。早解きリレーなので、提出を押してそのままコーディング。コンパイルもせずに出したのでちゃんとコンパイル通ってくれるか不安だったけど、無事ACしてくれた。多分、コーディングしてた時間より、スリープからの復帰を待ってた時間とsubmissionsのページをリロードしてた時間のほうが長かった。
そのあとは特にやることもなく、「あれどんな問題なんです？」とか聞きながら他の人たちがコーディング進めていく様子を眺めていた。Color Gameが偶奇判定で解けるという証明を考えてるけど、まだ証明が完成してなくて辛い。k = 0で偶奇判定で解けるのは自明なので、kに関しての帰納法で証明できそうな気がしてる（気がするだけ）。早解きリレー。リレーが終わった後のほうが話題がたくさんあって、チームの人と仲良くなれそうな気がするのだけど、リレー終了後にそんなに時間なくてお話できなかった。つらい。
閉会式
チーム対抗リレーが終わり、そのまま閉会式へ。二日間の様子を収めた映像が流れる。楽しかったなーと思いながら眺めてた。indeed社からTシャツのプレゼントがあるという話があって、記念撮影したら解散だった。会場出口でtunenarazuさんとchako0407さんが待っていた。握手して帰宅するシステムらしい。確か、会場側から眺めて右側にtunenarazuさん、左側にchako0407さんが居た気がする。左側のほうから会場を出たので、chako0407さんとだけ握手して帰ることになるのかなーと思ってたら、tunenarazuさんが、「あ、逃げた」と言ったので「そういうシステムになってたのか」と思ってtunenarazuさんと握手して帰宅。tunenarazuさんごめんなさい。
帰り道
kyosさんとclimpetさんと会場出口で出会えたので、ここにDarseinさんともう一方が加わって空港へ。同じ大学の同期は別班で空港に行ったらしい。climpetさんが空港までのコストが最小になる経路を知っていたのでclimpetさんについていく。climpetさんとkyosさんはDarseinさんと知り合いなので、Darseinさんと接点無いのが私だけという状況。「JAG合宿のときは『あれがDさんかー』と遠目に見てました」という話をしたら「どうぞ気軽に、welcome!」みたいなことを言われた。
空港までの電車の中で、来年以降もCODE FESTIVALがあるのなら、大学の競プロサークルに入部してきた一年生が目指す一番最初の大会としていいですよねーという話になっていた。そこそこのレベルの競プロerが相当数存在することが確認できたので、来年本選に出れるかどうかかなり危ういと思っているので、プログラミング暦半年の人が目指すにはかなり高い目標な気もしたが、ICPC国内予選で1完するという目標よりはだいぶましらしい。とても充実したプロコンだったので来年は予選参加者が激増してさらにレベル上がりそうな気がしているのだが。。。
他にも、DさんからあさプロMidDの解法を教えてもらったり、kyos氏がじゃんけんの比較関数みたいな比較関数を使ってsortしたら停止性は保証されるのかとかそういう疑問を投げたりしてた。
空港に着くと、同じ大学の人々がほとんど同じ飛行機で帰るらしいということが分かった。久留米高専の某氏も（話しかけなかったけど）発見した。帰りの飛行機がポケモンジェットだった。飛行機の到着後、手荷物が最後の最後まで出てこないというちょっとしたトラブルに遭遇したが、ちゃんと手荷物見つかった。
空港から大学方面の自宅まで、climpetさんやj_gui0121さんと来年のICPCどうなりますかねーとかいう話をしながら帰宅してた。
おわりに
CODE FESTIVAL予選と本選、あさプロを通じて、競プロ欲が刺激されました。自分とおなじぐらいのレベルに100人以上居て、ここから頭一つ抜け出さなければと強く感じました。また、予選B・あさプロを通してAC数で差をつけられるように問題が調整されている場合に限って言えば、抜け出せるだけの実力になっているが分かり、自信につながりました。ARCとかSRMだと問題の難易度差が大きくてなかなか実力向上を実感できないんですよね。
CODE FESTIVALが終わり、なにやら寂しい気分に。いつまでもCODE FESTIVALの余韻に浸っていたい気もしますが、そろそろ次の大会（ICPCの2015年国内予選かな）に向けて練習をしなければ。
次の目標は
・TopCoder SRMでyellowになること。
・2015年のICPCでアジア大会に進出すること。（2チーム突破の壁を越えること）
・ARCで3完の壁を突破すること。
の三つでしょうか。院試に落ちない程度に、留年しない程度にがんばります。
CODE FESTIVAL 2014 こちらがお金を払わないといけないのではないかと思うほどにとても充実した大会でした。来年度もぜひ開催してほしいです。
リクルート社の皆様、運営サポーターの皆様、その他CODE FESTIVALの運営に携わられた皆様、ありがとうございました。
2014年JAG夏合宿参加記
ご無沙汰しております。JAGの夏合宿に参加したので参加記をば。
0日目、JAG合宿参加のため夜行バスで東京へ向け出発しました。航空機や新幹線と比べて片道1万円ほど浮くのは魅力的ですね。
1日目、東京新宿駅に到着。同じ夜行バスに乗っていたチームメイトと時間を潰し、航空機で来たチームメイトと合流しました。また、@nisshy nisshy(@nsd_fb)さんと合流し昼食後オリンピックセンターへ向かいました。
この日はコンテストはなく、自己紹介と懇親会がありました。懇親会の時点で、既に競プロ勢のコミュニティが出来上がっていると感じ、twitterでも競プロ勢を積極的にフォローしていない自分は気後れ。同部屋の人や同大学、同大学に編入予定の方とばかり話していました。
2日目、この日は10:00からコンテスト。この合宿にはICPC予選に参加したチーム全員で参加していたのですが、「強い人と組んで、強い人とはどういう人かを感じる」との方針のもと、臨時チーム募集所を利用してチームを組みました。この日はamylase伯爵ともう一方（ハンドルネームを失念してしまった。メモしておけばよかった）と組み、vimmersとしてコンテストに参加。結果2完でした。
私はB問題を担当し、amylaseさんの助言を得てDPの方法を考えていたのですが、ACならず。3時間が過ぎた頃でしょうか、二つのケースを示され、その二つのケースが同時に通るようなDPでなければならないことが分かり、その時点で考えていたDPではその二つのケースが同時に通るようなことは無かったため、別の問題を考えることになりました。この時点でA問題がAC、C問題がWA。C問題について、高々21通りについて答を埋め込んでやればACすることが分ったので、3人で手分けして答を導き埋め込み、submitデバッグの末AC（間違った答埋め込んでいたの私だけじゃなかったっけな。反省。）。score boardを確認し、あみだくじのD問題を解こうという話になり、計算量的に間に合う解法の見通しが立つも、実装できずコンテスト終了しました。
3日目、リクルート社に移動し11:00から模擬地区予選。この日もやはり臨時チーム募集所でチームを組み、デング熱としてコンテスト参加。この日は@yuustiさんと@hirokazu1020さんとチームを組みました。私と@hirokazu1020さんでA問題を読んだ後、とりあえず私がA問題を実装。誤読があり、バグらせましたがsampleで落ちたので@yuustiさんの助言を受け、修正し提出すると無事AC。私がAを書いている間@yuustiさんがC以降を、@hirokazu1020さんがB問題を読んでいました。AをACした後、Bの題意がいまいちつかめないということでBを三人で読むことに。@yuustiさんがB問題を説明し、解法の概要まで示してくれたので私が実装することに。BをACしたあと、@yuustiさんがDの解法の方針を説明。後、@yuustiさんの実装でAC（解法の説明があったのは、B実装前だったかな。）。Dの実装中、私はGを、@hirokazu1020さんはHを読解。Gは、毎日一つづつクッキーを食べる前提でDPをし、順列の計算で解を求めるという解法（想定解2）ができ、組み合わせの計算で出てくる階乗の計算をどうするかという問題を残してしました。後に、高々2000回ループを回せばよいことに気付き、計算量的には問題の無い範囲に落とせました。Gの実装は私が除法でmodを取っていく計算をよくわかっていないことと、DP慣れしていないこととで、@yuustiさんが担当。無事ACしました。また、G問題と並行して、H問題を@hirokazu1020さんが実装。GをACした後、Hを3人でデバッグし、AC。結果5完になりました。
4日目、合宿最終日。この日は同部屋だった@ENIXERvsREXINEさんと@assyさんの3人でチームを組み、assyとしてコンテスト参加。「自己申告3完の人が集まったチームなので2完したら褒めてね」と呟いていたような気がする。A問題を私が、B問題を@assyさんが実装し無事AC。C問題が難しいのではないか（のち、誤読と判明）、E問題は実装が重めだが、構文解析の部分を抜ければ自明な解法であるという判断のもと、@ENIXERvsREXINEさんがE問題の実装をすることに。この間、私はD問題を考えていたのですが、結局解法を導けませんでした。B問題ACのあとC問題を改めて読んだところ、誤読があったことが分かり、C問題はさほど難しくない問題であると分った。@assyさんに手計算をしてもらって、Cを実装しAC。C問題に関して、入力以外はちゃんとlong longで計算しているのに、入力だけintで受け取っていてWA叩いたのは反省点。E問題はああでもない、こうでもないといいながら実装がんばりました（@ENIXERvsREXINEさんががんばってました）が、ACできず結果は3完でした。でもまあ、自己申告で国内予選3完の人が集まったチームとしては上出来だったのではないでしょうか。
合宿終了後、高速バスで帰宅することに。高速バスまで時間があったので、荷物をコインロッカーに預けたあと神保町に行ってみました。数学書とかも古本だと値段落ちてていいですね。何冊か安くで変えました。
5日目、福岡到着。博多で昼食、用事を済ませたあと帰宅。午後2時ごろに自宅にたどり着きました。疲れが溜っていてそのまま12時間超えの睡眠へ沈みました。これにて合宿終了です。
合宿を通して。
実は今回のJAG合宿、交通費＋参加費の3万程度払ってまで参加する価値があるかどうか半信半疑のままの参加でした。結論から言って、3万円出した価値はあったのではないかと思います。今まではtwitterやコンテストのスコアボードでしか見たことの無い人たちと会えて、競技に対する意識が高まったこともそうですし、何よりも演習量いかんではこの人たちに追いつけるのではないかと思えたことは大きな収穫だったのではないかと思います。競技プログラミングのような事に関しては輻輳説のようなものを信じていますが、努力して埋められない差ではないということは感じることが出来ました。
合宿参加者の皆様、お疲れ様でした。合宿参加者、JAG、リクルートの皆様、ありがとうございました。
九州大学プログラミングコンテスト参加しました
昨日、九州大学プログラミングコンテストにオンサイトで参加してきました。
オンサイトでのコンテスト参加は始めての経験でいい刺激になりました。一応、同じ学校で競技プログラミングをやっている人とは部活で知り合っていたりするのですが、他校の競技プログラミングをやっている方と実際に会う機会がなかったのでこういう貴重な機会はいいですね。まさかcolunさんまでいらっしゃるとは思わなかった。
さて、コンテストなのですが、ICPC形式でチームを組み「(≧∀≦*)」(2名)としてコンテストに参加しました。
結果は４完。私はBとDを解きました。ダイクストラ法の実装に無駄に時間をかけたり、バグらせたりしたのは反省点。実装量が全く足りていないようです。ICPC国内予選まで実装量を稼いで実装慣れする必要を強く感じました。
また、E問題に関しても
・胡桃さんが移動する速度のうち、猿の移動する速度に添う成分が猿の移動する速度と同じであれば猿を捕まえることができること。
・猿の移動する方向が胡桃さんからみた猿の方向と一致するときにコーナーケースが存在すること。
の二点について分っていたのにACできなかったのは反省すべき点でした。
あと3ヶ月無いくらいでICPC国内予選なので、そろそろ気合入れて練習します。
デザインパターン勉強しました。
上の本を購入してデザインパターンを勉強してみました。
デザインパターンを一通り見た印象は「オブジェクト指向の活用例をまとめたもの」で、デザインパターンはそれ自体を参考にしてプログラムを設計するという使い方でなく、自分の考えているやり方を他人に説明するための語彙として持っておくものという印象を受けました。
本の中で繰り返し言われていたことを纏めると
・外部から見えるべき機能とそうでない機能を区別すべき。
・外部から呼べる機能をAPIとして抽象クラスにまとめ、具体的な機能についてはその派生クラスで実装すべき。
ということでしょうか。
23のデザインパターンが紹介されていたのですが、その殆どが上のような考え方をもととした設計のように感じられました。
オブジェクト指向言語を勉強してみたはいいものの、オブジェクト指向とは何で、言語の機能をどう活かせばいいのかわからない。そういう層が読むと面白い読物だと思います。
さて、この本についてなのですが、私はあまりいい本だとは思えませんでした。本の中で説明が前後している箇所があります。分からないところがあっても、それを飛ばして読める人ならばいいのでしょうが、分からない箇所があったらつど立ち止まって考えるタイプの人間には向いていません。また、せっかく抽象的な話をして理解しかけていたところに、例え話を入れて分かりにくくしている箇所もあります。人によって向き不向きはあるのでしょうが、私には向いていないようでした。
一通りデザインパターンは把握できた、ことになるんでしょうかね。
GoF本......読むべきでしょうか。
