競技

この文章は Prolab' Advent Calendar 2015 の 25 日目の記事です．

年末って忙しいですね
別にクリスマスだからと言うわけではないのですが
勢いでこの文章書きます やっほい

きみはだれ

さすがに 3 年生以下は知らない人多いかな，
プロラボ部の前の前の前の部長です（制御科 48 期生）

なにしたひと

現役時代は SuperCon, パソコン甲子園, JOI, ICPC, 高専プロコンとかにそこそこ出てました
大学生になった今でもプロコン観戦しに行ったり出場しに行ったりしてます

これは何の記事

昔は「久留米」というと赤子も黙る強豪校だったんですが
最近「久留米」の名前あんまり見ないよネエ
という話をします
競技の話なので自由課題やその他ソフトウェア開発の大会については言及しないです，ごめんなさい

昔は強かった久留米

昔といってもプロラボ部の歴史は 10 年強なのですが，僕が知るかつての伝説を述べますと

  • 9 年連続 ICPC アジア地区予選出場（高専では異例）
  • 高専プロコン競技優勝回数最多記録保持
    • 2015 年現在も久留米と府立がそれぞれ 4 度優勝で首位タイ
  • O 高専の某 M 教授やその他 S 高専，T 高専の先生方が久留米を敵視し学生指導に励む

みたいな感じでした．

盛者必衰

ICPC アジア地区予選連続出場記録も途絶えましたし，ウーンなんでだろう

僕は n 年前に卒業したので外野から見ている立場ですが，思うに周りのレベルの向上についていけてない気がしています． 日本の競プロ界は年を経る毎に確実にレベルが上がっていて，例えば昔だと DP が怪しくても JOI の春合宿に行けたものですが，最近は DP を使いこなさないと予選通過も厳しそう
春合宿レベルだとセグ木や UnionFind 等のデータ構造は必須でしょうか
流石に最大流は要らないのかな

豪速球を投げる中学生

今年の長野プロコンでお会いした KRK 先生はこのように仰ってました

「豪速球を投げる中学生は居るけれど，その先に続かない」

つまり 1,2 年生で JOI 本戦に行ったりする人はポツポツいるけれど彼らはそこで伸び悩みそのまま 4,5 年生になってしまう，という意味らしいです
現役生にとってはキツイ言葉だと思いますが，僕自信の体験としてもそれは分かるなー，という気がします

最初は楽しいが，少し出来るようになって大会に参加するようになると，地区大会などの規模の大会がなく，いきなり少なくとも全国レベルでの大会になるので， 目の前に立ちはだかる敵の強大さに打ちひしがれ，そのまま飽きて辞めちゃう，みたいなサイクルがあった気がしています

特に昔の TopCoder とかだと無味な（と言うとアレですが）数学系の問題も多かったので，高いレベルの問題を解くこと自体が無意味に思えてくるというか， 「高専」であることの気負いを勝手に感じて自分は新学校の人に比べ数学をする才能がないと思い込むとか そんな感じでした

「才能」から「努力」へと遷移した競プロ

このように昔は才能がモノを言う世界だと，自分自身に対して言い訳のように思っていたわけです．実際，中学受験でいわゆる「パズル的な算数」に取り組んできた人たちは，そういう問題はある程度得意だと思います

しかし，昔より数学力で殴る問題は減ってきて，最近はアルゴリズムとデータ構造をきちんと会得し，ライブラリを整えれば解ける問題も増えてきてると感じています（強プロをやっている人の構成員がそういう集団に遷移して来たので，作問がそっちよりになったという説があります）

加えて今は僕がやっていた当時より優良な教材がたくさんあると思います
蟻本やチーター本などの教本もあるし，英語が苦手な高専生のために AtCoder や AOJ もあります

久留米高専は 4 年生になると大量の手書きレポートを課されてしまい戦闘力が半減するという話もありますが，そんなの関係ないです

1,2 年生 レベルはどんどん上がってきているので，昔の先輩を抜くだけではだめです
今の先輩を抜く勢いでがんばろう

3,4,5年生 競プロコミュニティは拡大していて最近は CODE FESTIVAL とかもあるんで，昔よりみんなでわいわい楽しいですよ
もう一度ゆっくりやってみるのはどうだろう　何かの役にもたつはず

まあでも

「精進」とか言って脅迫的に練習するのは続かないし楽しくないですよね．
楽しんでプログラム書くのが一番です，肩の力を抜こう
問題解けなくても，他の人の解法を見て新たな気づきを得られるだけでも楽しいものです
レッツエンジョイ！

無限面のサイコロは球なのか？

気になりますよね．

この記事は ICT Advent Calendar 2015 の 25 日目の記事です．

まえがき

前掲した Google Docs のページ，半分以上誰なのか分からないので自分が老害である事実をより一層噛み締めているなとりうむです． 久留米高専プロラボ部の OB で，前の前の前の部長をしてました． 今週沖縄行ってました．コーレーグース美味しい．

無限面のサイコロ？

偉大なるまるさ先輩のブログのタイトルです． 無限面のサイコロってなんでしょうね．とりあえずサイコロと聞いて思い浮かべる図形を wikipedia から拝借して来ました．

f:id:natrium11321:20151206212820g:plain:w150 f:id:natrium11321:20151206212349g:plain:w150 f:id:natrium11321:20151206212542g:plain:w150 f:id:natrium11321:20151206212814g:plain:w150 f:id:natrium11321:20151206212817g:plain:w150

左から順に正四面体，正六面体，正八面体，正十二面体，正二十面体です．確かに面*1の数が増えてくるとだんだん球に近いような形になってるっぽいオーラが出ています．この調子で面の数を無限まで増やしていけばきっと球に・・・？

無限は怖い

話はそう簡単ではありません．基本的に数学で無限というのはとても怖い単語で，その手の人が聞いたら「加算？非加算？あ，連続体仮説認めない人？」とか「超準解析」とか「選択公理反対！」とか「ℵ」とか，このような反応が帰ってきます．怖いですね．ちなみに僕もここ最近有限の数しか扱ってないので，安易に無限を扱うのが怖いです．この文章にマスカリ飛んできそう．;;(∩´﹏`∩);;

しかしここで足を止めてしまってはいけません．例え怖い人達にマサカリを投げられようとも，サイコロに因縁のある僕らは「無限面のサイコロ」の正体を暴かなければならないのです．ICT Advent Calendar とはそういうものだったはず．

サイコロを定義しよう

サイコロという概念をきちんと定義しないとこの議論は出来ません．ある図形がサイコロであると呼ぶのにふさわしい性質は何でしょうか．まず，サイコロである以上，その図形を振ることが出来なければ意味がありません．サイコロは数えるものでも並べるものでもないですね．次に，振った結果として「目」が出る必要があります．つまり，どの面が出たのかがきちんと分かる必要があります．

以上の要求を踏まえて，この文章では以下を満たすものをサイコロ (dice) と呼ぶことにします．

定義（サイコロ）

\mathbb{R}^n の部分集合 S \subseteq \mathbb{R}^n は以下の条件を満たすとき，サイコロであるという．

  1. S は n 次元凸多面体である．但し n 次元凸多面体とは， n=0 の時は単元集合であり， n \geq 1 の時はその境界が加算個の n-1 次元凸多面体の和で書けるような n 次元閉凸集合を表す．
  2. S は空でない*2．
  3. S は有界である．

難しそうな単語がいっぱい出てきました．これを口語訳するとこうなります．

定義（サイコロ）

n 次元空間の図形 S は以下の条件を満たすとき，サイコロであるという．

  1. S は凹みのない n 次元の図形で，面が数えられるくらいしかなくて，しかもその全ての面とか辺とかは全て真っ直ぐであり，曲がっていない．
  2. S の実体は存在する．
  3. S は無限に大きくない．

この定義のキモチを考えてみましょう．条件が 3 つありますが，本質的な条件は 1 のみです．条件 1 の前半は「凹みがない」ことを言っています．確かに凹んでいる図形は，凹んでいる部分の面が地面に接することがないため，サイコロとして使えそうにありません．一方後半はすべての面が安定してきちんと地面に接することが出来ることを保証しています．確かにこの条件はサイコロとして必要っぽいです．条件 2 と 3 は，虚空を指してここにサイコロがあると言いはったり，逆にこの宇宙全体*3が実はサイコロだと主張したり，そんな感じの変な図形を除外している感じです．

逆に，上記の定義に当てはまる図形は赤子が泣こうが全てサイコロです．

どんなものがサイコロなんだろう

例 1. 点（0 次元）
f:id:natrium11321:20151224222237p:plain

点は 0 次元空間の（唯一の）サイコロです．数式で書くと \{0\} です．ちなみにこのサイコロ，常に 1 の目しか出しません．たまげたなあ．

例 2. 線分（1 次元）
f:id:natrium11321:20151224222239p:plain

1 次元空間のサイコロは（長さと位置の違いを除いて）線分しかありません．数式で書くと [0, 1] みたいな感じです．このサイコロは 1 の目か 2 の目を出してくれます．優秀．

例 3. 正方形（2 次元）
f:id:natrium11321:20151224222238p:plain

空間の次元が 2 まで上がると一気に色々なサイコロを考えることが出来るようになりますが，その中で最も初等的なのがこれです． [0, 1]^2 みたいにかけます．1 の目から 4 の目まで当確率で出してくれるし，向かい合う目の合計は全て 5 だし，優秀そうなサイコロです．

例 4. 立方体（3 次元）
f:id:natrium11321:20151224224016p:plain

僕らが最もよく知っている 6 面サイコロです．謎の安心感があります．

例 5. 正八胞体（4 次元）
f:id:natrium11321:20151224224017p:plain

1 から 8 までの面（といっても各面は通常の意味での立方体ですが）があります．

球は無限面のサイコロなのか？

本題に戻りましょう．（3 次元の）球は無限面のサイコロと言えるのでしょうか．答えは残念ながら No です*4．何故なら球の面（境界）は球面ですが，球面はまっすぐな平面を幾つか切り貼りして作ることが出来ない（凸多面体ではない）からです．そもそも球，振っても何の目が出たか分かんないし…………

じゃあ無限面のサイコロってあるの？

あります．

例 6. 無限面のサイコロ 1（2 次元）
f:id:natrium11321:20151224234213p:plain

なんかやばそうな平面図形が出てきましたが，これは何をしているかというと，単位円の上半分に頂点を沢山置いて，それらを辺で結んでいるだけです． y 軸に近いほどいっぱい頂点を置いています．多分 y 軸と成す角度が 2^{-n}\pi ( n \in \mathbb{N}) くらいの所が頂点になっています．確かにこいつは辺（2 次元図形の面）が無限にあります．しかも，「数えられる量」の辺を組み合わせることで作られています（無限個あるけど，全部長さは 0 じゃないし，1, 2, … って数えられる）．面によって出やすさが異なりますが，サイコロの定義を満たしているので，これは正真正銘のサイコロです！ちゃんと何の目が出たか分かります（地面に接した面を「出た目」とする）．冬休み暇な人はそれぞれの目の出る確率を計算してみてください．

例 7. 無限面のサイコロ 2（無限次元）

次元を無限まで上げて， [0, 1] \times [0, 1] \times \cdots ってすればいいと思うんですが，無限は怖いので言及を避けます*5 ;;(∩´﹏`∩);;

結論

普通の 6 面サイコロを普通に使おう．

*1:さっきから「めん」で変換すると真っ先に「麺」が出てくる…

*2:この定義だと 1. から S の非空性が言えるので実は不要．空集合の次元は -1 でありこれは n と異なる．

*3:宇宙全体が非有界なのかという議論はここでは置いておきます．

*4:もちろん，上のサイコロの定義に従うと，という話なので，定義を変えればサイコロって言い張ることも出来ます！

*5:加算無限次元の線型空間というものを考えることは出来るはずで，凸性は well-defined だと思うんですが境界演算子とかがどうなるかよく分からない．書いた定義をそのまま拡張すると「無限次元凸多面体」の定義が循環して全ての閉凸集合が凸多面体になっちゃう気がするぞい．幾何怖い;;(∩´﹏`∩);;

Pokemon Advent Calendar 2014 8日目

この記事は Pokemon Advent Calendar 2014 の 8 日目の記事として書かれたものです． 本当は書く予定が無かったのですが，Calendar の主催者である kagamiz 君が困っていたので，僕も寄稿することにしました．

何を書くか迷ったんですが，

みなさんのポケモンとの出会い, ポケモン史を書き連ねる Advent Calendar です. ポケモンへ対する愛をさらけ出して下さい :)

とあったので，僕がかつて愛をこめて育ててきたとあるパーティの紹介をしたいと思います．

ポケモン歴

とりあえず何バージョンをプレイしたことがあるのかを書かないと話をしにくいので，，

プレイ経験あり（ガッツリ）：サファイア，リーフグリーン，ダイヤモンド，プラチナ，ソウルシルバー，ブラック，青の救助隊，空の探検隊

プレイ経験あり（少し）：銀，エメラルド，ファイアレッド，ポケモンピンボールアドバンス

一番メインで育成を行ったのはリーフグリーンとダイヤモンドです．中学二年生くらいだった気がします．最近はあまりポケモンをプレイ出来ておらず，特に XY 以降に新登場したポケモンは分からないのでご容赦下さい．ちなみに本題から逸れますが，上記の中で一番好きなタイトルは 空の探検隊 です．ポケモンは不思議のダンジョンシリーズが，ストーリー・音楽共にとても素晴らしいので，プレイされたことのない方はぜひ一度お手に取ってみることをお勧めします．

パーティの紹介

エントリーNo.1 わりばし（マルマイン）

  • 性格：おっとり
  • 特性：ぼうおん
  • 技：かみなり，でんじは，あまごい，だいばくはつ
  • 努力値：CS
  • もちもの：しめったいわ

雨パの雨撒き係です．先発に出して，その素早さを活かして速攻で雨を降らせます．もちろんもちものはしめったいわです．自分はその後でんじはを撒くか，命中100%のかみなりを放った後，だいばくはつして，たれにバトンを繋げます．生き延びて3ターンという，あまりにも儚い運命を辿るわりばしですが，彼（彼女？）の置き土産で戦況が大きく変わることも珍しくはありません．

エントリーNo.2 たれ（ルンパッパ♂）

わりばしの命を受けて登場するのがたれです．ルンパッパの素早さの種族値は 70 と決して高い方ではありませんが，すいすいの効果により，雨の中では素早さ 140 と等価になります．130 族もびっくりの素早さです．れいビを打てるのでドラゴンも狩れます．ギガドレインで回復も出来ます．なかなか器用なやつです．あと体感地味に打たれ強くて頼れる奴です．

エントリーNo.3 しろごはん（フーディン♂）

実はそんなに雨パというわけでもなくて，後は特に雨関係ないやつが続きます．しろごはんはCSブッパのフルアタフーディンです．よくあるやつです．でもしろごはんのきあいだまは結構当たった記憶があります．愛の力ですね．エナジーボールはサブウェポンとして地味に便利です．というかこいつだけ 600 族だから普通に強いよね．

エントリーNo.4 おさら（ツボツボ♂）

  • 性格：わんぱく
  • 特性：がんじょう
  • 技：かげぶんしん，どくどく，ねむる，まきつく
  • 努力値：HB
  • もちもの：かいがらのすず

どくどくを撒いた後巻き付いて逃げられなくし，相手をじわじわ毒殺します．その間自分はかげぶんしんを繰り返し，残像を大量に生成し，命中率を下げます．ピンチになったら眠ります．対人戦で使うとかなり嫌われます．友達をなくします．対戦してくれなくなります．でも，その割にはうまく決まらなくてあっさり負けたりもします．さらに，消耗の激しいストーリーでは全然使いものにならないです．でもツボツボかわいいからいいんです．愛です．

エントリーNo.5 おかず（ウィンディ♀）

物理特殊の両刀使いであるおかずは，対処することの出来る相手の幅が広く，あらゆる場面で活躍することができます．特に，虫の息になった相手を，しんそくで確実に仕留めることが出来ます．但し，雨が降っている間に出してはいけません．また，実はこのパーティの紅一点です（わりばしは性別不明なので除く）．

エントリーNo.6 カルビ（ラグラージ♂）

一番手塩にかけたのは カルビ です．実は僕も御三家の中ではミズゴロウが好きなので，ラグラージをよく育てていました．カルビはその中の一匹で，一番良く使っていたので印象に残っています．カルビはこのパーティのリーダー的存在です．雨の中でも，雨が止んでも，活躍します．しかしながら，あまり良く考えずに育成したので（例えば性格），その後継としてとんカツという別のラグラージも居たりしますが，それはまた別の機会に．