JOI春合宿2015チューター記

 

JOI春合宿2015にチューターとして参加したので参加記を書きます。

 

周期表収集機

ジャンル: SF, ストラテジー, 収集, 化学

オススメ度

ゲーム内容

ある天才科学者が開発した、空気を原料として任意の元素を生成する機械。

あなたはこの歴史的大発明の立会人です。あなたは機械が生成した元素を収集して金を稼ぎ、その金でさらに機械をグレードアップさせていきます。機械には3つのステータスがあり、あなたはそのバランスも加味して機械をアップグレードさせなくてはなりません。

果たしてあなたは全ての元素を集めることが出来るでしょうか?

感想

なによりもまずゲームバランスが最高です。

最近流行りのゲームに比べて退屈する時間が短く、かといってゲームの一区切りの時間が長いというわけでもない。決して人を飽きさせない最高のゲームです。

また、生成した元素についての知識も得ることができるので、いわゆるためになるゲームでもあります。

化学が苦手なあなたも、知識を深めたいあなたも、このゲームでもっと化学を好きになろう!

 

 

薔薇がバラバラ

ジャンル: エイム力、反射神経、雰囲気、ダジャレ

オススメ度★★★☆☆

ゲーム内容

画面上にたくさんの薔薇が現れます。あなたはそれぞれの薔薇に狙いを定め薔薇をバラバラにします。決められた個数の薔薇を全てバラバラにするまでの時間を競うゲームです。

感想

ゲーム名はつまらないダジャレになっていますが、侮ってはいけません。アイコンからもわかるように、ゲーム内の薔薇やそれがバラバラになる時のエフェクト、背景までもがゲームの雰囲気を作り上げており、プレイ中に世界観に浸ることの出来る、素晴らしいデザインになっています。

先述の通りエイム力がものを言ってくるゲームなのですが、あいにくiPhoneにタップするという動作は、エイム自体に向いていない点も有り、そこについては改善の余地があるのではないかと思ったので、星3つにさせていただきました。

 薔薇が好きな方はぜひプレイしてみてくださいね!

薔薇がバラバラ

薔薇がバラバラ

  • RUCKYGAMES CO., LTD.
  • ゲーム
  • 無料

 

add time -時間加速- lite

ジャンル: 脳トレ, 計算

オススメ度

ゲーム内容

アナログ時計が2つ表示されます。左に表示されている時刻から右に表示されている時刻まで何時間何分たったかを4択で答えるゲームです。

add time -時間加速- lite

add time -時間加速- lite

  • RUCKYGAMES CO., LTD.
  • 教育
  • 無料

かおかお

ジャンル: 脳トレ, カウンティング

オススメ度

ゲーム内容

右向きと左向きの二種類の顔文字がたくさん表示されます。

どちらが多いか当てるゲームです。

連続正解型のゲームで、ステージが進むに連れ顔文字も多くなっていき、間違えたらそこで終了。何連続正解できたかを競います。

 感想

顔文字の右向きと左向き。空白の位置以外の違いがないので非常に難しいです。しかしパッと見た感じで適当に答えてもわりと正解できるので、以外にもハマってしまいます。

長時間プレイすると目がチカチカしてくるのでその点は注意。

Twitterで顔文字合戦をこれからしようという方には顔文字力をあげるためにおすすめです。

かおかお

かおかお

  • RUCKYGAMES CO., LTD.
  • ゲーム
  • 無料

 

リーゼント vs トロンボーン

ジャンル: 超能力バトル、反射神経、スナイプ

オススメ度

ゲーム内容

あなた(主人公)は超能力者です。体の一部の長さを自在に変化させる能力を持ちます。敵も超能力者で、直接触れずに物体を操ることができます。

敵がトロンボーンを操作して雫を狙います。あなたは雫を守るために超能力を使って応戦します。どれだけ長く雫を守れるかを競うゲームです。

 感想

超能力バトル系の中では最もシンプルな部類だとおもいます。しかし、敵が雫を狙うタイミングがバラバラで、攻撃に瞬時に反応できないとすぐにやられてしまいます。

絵もあいくるしいタッチで描かれていて飽きない作品です。超能力バトル系が好きな方はぜひ一度プレイしてみてください。

リーゼント vs トロンボーン

リーゼント vs トロンボーン

  • RUCKYGAMES CO., LTD.
  • ゲーム
  • 無料

 

大収集!!カードコレクト

ジャンル: 収集、数学

オススメ度★★

ゲーム内容

架空のカードを集めるゲームです。カードにはたくさんの種類があり、現実世界のように数枚入りのパックを買うことでゲームは進みます。

進行するに連れ買うことが出来るパックの種類が増えます。あなたはどれだけカードを集めることが出来るでしょうか?

感想

現実世界でもカードコレクトは人気ですね。私も使用済みのオレンジカードを意味なく集めた記憶が懐かしいです。このゲームはその楽しみをもう一度体験させてくれます。パックが増えたり、同じカードがでてきて「またかよぉ」となったりするあの感覚をリアルに感じることできます。

カードコレクトが大好きな皆さんはぜひこのアプリを入れてみてください。

 

大収集!! カードコレクト

大収集!! カードコレクト

  • RUCKYGAMES CO., LTD.
  • ゲーム
  • 無料

 

週刊アスキー表紙コレクション

ジャンル: 収集、週刊アスキー

オススメ度★★

ゲーム内容

「大収集!!カードコレクト」の集める対象がカードから週刊アスキーの表紙に変わったゲームです。週刊アスキーがRUCKYGAMESとコラボしてできたゲームです。

感想

集めるものがカードから週刊アスキーの表紙に変わっても、コレクションの楽しみは健在です。実在した週刊アスキーの表紙になっていますので、本当にコレクトする気分になれてより楽しめるとおもいます。

 

週刊アスキー 表紙コレクション

週刊アスキー 表紙コレクション

  • RUCKYGAMES CO., LTD.
  • ゲーム
  • 無料

 

Cross Shot lite

ジャンル: 弾幕、爽快

オススメ度★★

ゲーム内容

無数の敵艦が画面内を動き回っています。あなたは一回だけ十字に拡散する弾を打つことができます。この弾が敵艦にあたるとさらにそこから十字に弾が拡散します。あなたは一度だけの発射で全敵艦を撃ちぬくことが出来るでしょうか?

感想

The弾幕という感じのゲームです。1発しか売っていないのに、ねずみ算的に弾が増えていって弾幕を形成する様は圧巻です。そのため全敵艦を撃ちぬけないということはめったにないのですが、後半のステージになると失敗することも有ります。

弾幕好きなら買わない手はない!

Cross Shot lite

Cross Shot lite

  • RUCKYGAMES CO., LTD.
  • ゲーム
  • 無料

 

三国志三分

ジャンル: 三国志、知識、脳トレ

オススメ度☆☆☆

ゲーム内容

三国志の有名な登場人物の名前が次々に現れます。それがどの国(魏呉蜀)の出身か次々に答えていくゲームです。

感想

三国志好きにはたまりませんね。私は感じが苦手なのであまり高得点を叩き出せ無いのですが、やっているうちに三国志に詳しくなっていく感じが好きです。

日本人は中国人よりも三国志に詳しいという噂を聞いたことが有ります。三国志フリークのみなさんこのアプリで腕試しをどうぞ! 

三國志三分

三國志三分

  • RUCKYGAMES CO., LTD.
  • ゲーム
  • 無料

 

BreakGet

ジャンル: 瞬発力、カウンティング、脳トレ

オススメ度

ゲーム内容

GetとBreakを決められた順番にできるだけ早く押すゲーム。

感想

一行で内容を説明できるほどシンプルなゲームです。往々にしてこういうゲームはハマってしまうものです。全部押し切るまでの時間を図るのですが、押し間違えても押すべきものは進んでいくので、しっかり見ていないとミスしてしまいます。

ちょっとした時間つぶしに最適!みんなぜひやってみてください!

BreakGet

BreakGet

  • RUCKYGAMES CO., LTD.
  • ゲーム
  • 無料

 

NOWLOADING

ジャンル: 戦略、サバイバル、動体視力

オススメ度★★★

ゲーム内容

ローディングバーが時間経過とともに増えていきます。ローディングバーをタッチするとそのうち幾つかを砕くことができます。砕いたローディングバーは画面上に散らばりますが一定時間後にまたバーに戻ろうとします。バーにくっついていない砕けたローディングバーをタッチすると、それは消えて、二度とバーに戻ろうとはしません。ローディングバーが100%になるまでの時間をできるだけ遅くするゲームです。

感想

最初の方はローディングバーを連打しておくだけで良いのですが、それらが復元しようとし始めた時にしっかり処理しないと、連打が追いつけなくなって収集がつかなくなります。ローディングバーのタッチと欠片の処理のバランスを上手く考えなければならない、意外と頭をつかうゲームです。

 

NOW LOADING

NOW LOADING

  • RUCKYGAMES CO., LTD.
  • ゲーム
  • 無料

 

ドットsearch

ジャンル: 指トレ、精度

オススメ度★★☆

ゲーム内容

指定された座標をタッチするゲーム。

タッチした位置と指定された位置の座標の距離の差の小ささを競うゲームです。

感想

これまたシンプルなゲームです。たとえば(150, 200)を指定されれば、だいたい画面の中央あたりをタッチすればよいというゲームです。ちゃんと四隅の座標は教えてくれるので完全に勘というわけではありません。しっかり実力に見合った結果が得られます。

これからウェブデザインなどで座標をたくさん使うかもしれないかたは、ぜひ座標力向上のためにプレイしてみてください。

 

. search

. search

  • RUCKYGAMES CO., LTD.
  • ゲーム
  • 無料

 

イドケイド

ジャンル: 日本周遊、旅行

オススメ度★★★

ゲーム内容

「チェック」という行動によってあなたが実際にいる位置情報を取得します。そのとき居る都道府県は「行ったことが在る都道府県」になります。47都道府県すべてを「行ったことが在る都道府県」にするのがこのゲームの目的です。

感想

カードコレクトとは異なり実際にあなたが行った都道府県をコレクトします。時間をかけるだけでなくあなたの足も動かさなければなりません。しかし、いろいろな場所をめぐるというのはQOLの向上にもつながります。決して面倒くさいだけのゲームではありません。

旅行好きのあなたや、乗り鉄のあなたはぜひスマホに入れることをおすすめします。

 

イドケイド

イドケイド

  • RUCKYGAMES CO., LTD.
  • ゲーム
  • 無料

 

パワースポット一網打尽

ジャンル: 社会学、人類学、オカルト、ストラテジー、経営

オススメ度★★★

ゲーム内容

あなたは人気パワースポットです。あなたに訪れる人々とパワーをやりとりしながら、パワースポットのレベルを上げていきます。レベルが上がるとさらに人気が上がり多くの人が訪れるようになります。めざせ最高のパワースポット。

感想

いわゆる経営系ゲームですね。貞子が出てきそうなパワースポットに群がる人々を無駄なく利用することが効率の決め手です。また観光地がどのように発展していくのかという社会学的に課題にも暗に言及している、アカデミックなゲームです。

プレイする価値有りです。

 

パワースポット一網打尽

パワースポット一網打尽

  • RUCKYGAMES CO., LTD.
  • ゲーム
  • 無料

 

THREE MATCH PUZZLE

ジャンル: Zookeeper、マッチ棒

オススメ度★☆☆

ゲーム内容

Zookeeperです。

感想

ただのZookeeperです。もちろん面白いです。しかし新規性がががが・・・

無料なので入れて孫はないです。

 

THREE MATCH PUZZLE

THREE MATCH PUZZLE

  • RUCKYGAMES CO., LTD.
  • ゲーム
  • 無料

 

無限刺身

ジャンル: 労働、収集

オススメ度★★

ゲーム内容

32種類ものお造りのパックにタンポポを載せていくゲームです。あなたはどれだけ多くのパックにタンポポを載せることが出来るでしょう。

感想

もう最高です。タンポポをのせるだけのバイトはつまらない、などという文言が一般に知られていますが、それが嘘だと一瞬でわからせてくれるゲームです。

お造りは単調に見えて多様なのです。みなさんぜひこの世界観を感じましょう。

 

無限刺身

無限刺身

  • RUCKYGAMES CO., LTD.
  • ゲーム
  • 無料

 

iヒナ マツリ

ジャンル: 脳トレ、判断力

オススメ度★★☆☆☆

ゲーム内容

無数のヒヨコが画面上に現れます。オスかメスか判断して、オスなら画面右に、メスなら画面左に仕分けしてください。制限時間内に何匹のヒヨコを正確に仕分けることが出来るか競うゲームです。

感想

現実世界とは異なり、ヒヨコの性別判定は頭にリボンをつけているかどうかで判定できます。しかし連続してたくさんのヒヨコを判別していると、ときどき間違った判断をしてしまうこともあります。ぜひ脳トレに。

 

iヒナ マツリ

iヒナ マツリ

  • RUCKYGAMES CO., LTD.
  • ゲーム
  • 無料

 

あぬめ

ジャンル: 脳トレ、動体視力

オススメ度★★★★

ゲーム内容

画面上にいくつかのひらがなっぽい文字が表示されます。一つを除いて「あ」「ぬ」「め」の間をモーフィングしながら変化しています。変化していない一つを見つけるまでの時間を競うゲームです。

感想

ゲシュタルト崩壊。この一言に限ります。「あ」「ぬ」「め」、案外似ているものですね。

 

あぬめ

あぬめ

  • RUCKYGAMES CO., LTD.
  • ゲーム
  • 無料

 

16 puzzle -white-

ジャンル: パズル、記憶

オススメ度★★★★

ゲーム内容

「16パズル」と呼ばれるスライドパズルです。しかしパネルに文字が書かれていません。開始前に一度だけパネルの数字を見ることができますが、それ以降は見れません。がんばって揃えてください。

感想

難易度は3種類あり、EasyではHintボタンを押すことによりパネルの文字を見ることができます。Normalではパネルが正しい位置に居る時だけ、文字が表示されます。Hardでは容赦なく文字を見せてくれません。Easy,Normalは簡単ですがHardは難しいです。是非皆さん挑戦してみてください。

 

16 puzzle -white-

16 puzzle -white-

  • RUCKYGAMES CO., LTD.
  • ゲーム
  • 無料

 


11人いればサッカーできる

クソゲー

 

11人いればサッカーできる

11人いればサッカーできる

  • RUCKYGAMES CO., LTD.
  • ゲーム
  • 無料

 

エスカレベーター

ジャンル: 脳トレ、文字認識

オススメ度★★★★

ゲーム内容

エスカレーターもしくはエレベーターの画像が表示されるので、それがエスカレーターかエレベーターか判断する二択問題です。逆にどちらがエスカレーターの絵か判断するという問題もあります。指定された問題数をできるだけ早く解くゲームです。

感想

二択問題と言っても「エスカレーター」「エレベーター」の二択ではありません。「エベレーター」「エレベーター」の二択なども有ります。しっかり文字を見ないと正解できません。このゲームも目がチカチカしてくるので長時間プレイは向いていないかも。だけどちょっとした暇つぶしには最適です。

 

エスカレベーター

エスカレベーター

  • RUCKYGAMES CO., LTD.
  • ゲーム
  • 無料

 

もじばたけ

ジャンル: 戦略、言語学栽培、収集

オススメ度★★★★

ゲーム内容

あなたは文字を栽培する畑を管理しています。収穫した文字をならべて文字列を作るとポイントが得られます。そのポイントを使って畑を拡張したり、文字の出現頻度を調節する機構を利用したりします。

感想

もじぴったんなどが流行ったように、語彙力系のゲームには一定の支持率が在るようです。このゲームもそうで、6文字以下の単語しか収録していないものの、以外なワードまで網羅しており、ゲームに不満を抱くことはまず無いでしょう。6文字の単語を作った時の快感といったら最高です。皆さん是非プレイしてみてください。

 

もじばたけ

もじばたけ

  • RUCKYGAMES CO., LTD.
  • ゲーム
  • 無料

 

ジャンル: 反射神経、タッチ力

オススメ度★★★★★★

ゲーム内容

画面に!(ビックリマーク)が表示されてから画面をタッチするまでの時間をできるだけ小さくするゲームです。表示される前にタッチするとMISSになってしまいます。

暇つぶしにソリティアが遊べます。

感想

0.22秒が私の壁です。これよりはやくタッチするには勘でタイミングを当てるしかありません。0.01秒でタッチする実績があるのでエスパー力に自信が在る方はぜひ挑戦してみてください。

 

!  

!  

  • RUCKYGAMES CO., LTD.
  • ゲーム
  • 無料

 

ニンゲンのチョウサ 

ジャンル: 苗字、収集、統計学

オススメ度★★★★★

ゲーム内容

地球の調査にやってきた宇宙人(あなた)が日本の苗字を収集するというゲームです。集めた苗字でUFOをグレードアップさせることができます。めずらしい苗字を収集するためにはUFOをグレードアップさせなければなりません。あなたはどれだけ苗字を収集できるでしょうか。

感想

最初の方は佐藤ばっかりですが、やがて田中、近藤、五所川原と珍しい苗字が出るようになっていきます。収集した苗字が日本で何番目に多いのか、などの情報も得られるので、友達同士で苗字を収集したりなんかすると盛り上がることまちがいなしです。ぜひプレイしてみてください。

 

ニンゲンのチョウサ

ニンゲンのチョウサ

  • RUCKYGAMES CO., LTD.
  • ゲーム
  • 無料

 

 

おわりに

春合宿に参加した皆さんお疲れ様でした。代表に選ばれた方はおめでとうございます。IOI頑張ってください。

DPの話

この記事はDynamicProgrammingAdventCalendarには関係ありますん。

 

最近DPできないという人が多いので、そういう人々に様々な言葉を投げつけたいと思います。

 

DP(ドッピオ)というのは競技プログラミングで頻繁に使われるテクニックです。日本語では動的計画法(ダイナミックプログラミンッ)です。

DPができない人はN(自然数)種類に大別されます。

第1種DPできないマン(ウーマン):初めてDPをみた

初めてDPを見た人というのは、おそらく競技プログラミングを始めたばかりの方だと思います。これ以前に解いた問題は計算量を考えたりする必要のない問題ばかりでしたでしょう。DPに出会った人々は初めて本格的にTLEに悩まされるでしょう。ソートなんかとはものが違う。累乗を擬似多項式まで落としこむという概念自体が初めてなので、人々はDPで「DPつらい、ちかよらんとこ」となるのです。そもそも入力を保存する以外の用途で配列を確保したりするという発想もまだ無いかもしれません。とにかくまだDPが発想に無いのです。

第2種DPできないマン(ウーマン):解説が読めない

さて、初めてDPに出会った人は悩みます。悩んで悩んでわかりません。わかる人ならできないマン(ウーマン)ではありません。わからないのです。そこで、きっとこの問題は私には無い発想が必要なんだと気づきます。それならばうんうん悩むより解説を呼んで学習するほうが効率が良い、そういうわけで解説を読むわけです。今日では多くの競技プログラマーがブログ等で解いた問題の解説を公開してますから、一つくらいわかりやすい解説に出会うでしょう。

しかしどの解説も読めないという人がいます。それが第2種DPできないマン(ウーマン)です。

この人は簡単です。言葉の勉強をしましょう。日本語じゃなくても英語でも大丈夫です。漸化式とか再帰とかの文字が読めないときは、競技プログラミングよりもっと基本的な何かが抜けているのでググるなどして理解しましょう。

第3種DPできないマン(ウーマン):解説が理解できない

晴れて解説を読めるようになったけれど、なぜそのアルゴリズムがうまくいくのかわからないという人がいます。

その人は数学的センスがありません。数学的センスはごく一部のプロのみが生まれながらに持ち合わせていますが、普通は持っていません。普通の人が数学的センスを磨く方法は一つしかありません。ずばり演習することです。まだDPは解けないので高校数学の確率と漸化式の範囲の問題でもすればよいでしょう。互いに排反であることを意識したり、できるだけ簡単に計算できるように場合分けを考えたりするというのはDPに通じる発想力ですので、やれば絶対にDP力がつくでしょう。それでもダメな人はアイエエエエエ

第4種DPできないマン(ウーマン):実装ができない

経験の問題だ!精進しよう。「精進」というのはひたすら問題を解く苦行のことです。たくさん解けば、いわゆるパティーン(パターン)がわかってきます。2,3重のfor文を書く。変数はちゃんと初期化しないとまずい。初期値は0だったりINFだったり。dp[0][0]だけはじめに適切に設定しないといけない。わざと1-indexにして番兵をつくるとわずらわしい条件分岐がなくなって良い。などなどいろいろなノウハウを精進でゲットしましょう。

第5種DPできないマン(ウーマン):解説記事の筆者の気持ちがわからない

解説も理解できるようになったし、理解した解説をコードに落としこむ事もできるようになったけど、解説なしでは解法がさっぱり思いつかない。どうしてその漸化式が思いつくのかわからない。そういうパティーンの人は競プロ的センスがありません

おそらくこのパティーンの人が一番多いでしょう。競プロ的センスというとやばそうに聞こえますが、今の文脈では「頭のなかで似た既知の問題を探してこれるようなセンス」のことを指すと考えてください。競技プログラミングというのは問題を解く問題を解く競技です。あらゆる特殊な問題を頭のなかで一般化して、できるだけ抽象的な形で引き出せるようにして格納することができるかどうかが大事になってきます。例えば私の個人的な見解として、JOI予選4番は2010年のA FIrst Grader以降、ぜんぶ同じ問題です。i番目までで状態がx,y,z...なときの求めたい値をdp[i][x][y][z]..で管理して、すべての変数について小さい順にループを回すだけ、という点で全部同じ問題です。そういう問題を分類する視野をもてるかどうかが一種の競プロ的センスだと思います。競プロ的センスについても数学的センス同様に演習でつくものですが、ただ精進するだけではだめです。しっかり頭で問題を吟味しましょう。

第6種DPできないマン(ウーマン):蟻本を持っていない

蟻本を読もう!

 

以上です

 

 

第一期蟻本元ネタ

最近毎日やっている【今日の蟻本】ですが、自分でやっていてネタかぶりが怖くなったので、何日分か元ネタ込みでまとめてみました 【今日の蟻本】を自分でもやってみたいなと思っている方がいらっしゃいましたらぜひ参考にしてください

 

PCK参加記

PCK参加しました。参加記を書きます。

 

Day1 (9/13)
  • 朝ごはんにサブウェイ
  • 学校につく
  • 体育祭の準備のお手伝いをする
  • 絵の具の水換えをしていたらズボンが盛大にぬれる
  • 冷えてる
  • インドの踊りの練習を見る
  • ホームセンターで細めの筆と紙皿を買う
  • 学校の予算で落ちるのでレシートをしっかり貰う
  • 買ったものを作業をしている人に渡して作業場をあとにする
  • ちょうど昼なので飲み物を自動販売機で買う
  • 炭酸なので美味しい
  • 部室に行く
  • みんながPCKの準備をしている
  • チーム「和馬」のさたしゅん、ぽてちはUbuntuを起動
  • チーム「三上」のいわい、おくらは印刷設備の確認
  • わたしは最近ハマっている伊坂幸太郎の「SOSの猿」を読む
  • 細々とした伏線がきれいに収まるコメディな作品が無条件で好きなので伊坂幸太郎作品は私の性に合っている
  • もうすぐPCKが始まるらしいので自分のノートパソコンをとじる
  • ツイッターもできなくなる
  • PCK開始
  • 体育祭準備から帰ってきたしあつまっと氏と作業分担
  • 彼が問題文を読む間、私は「SOSの猿」を読む
  • しあつまっと氏は「なんだやるだけじゃん」と行って問題を読むのをやめた
  • 私は問題を解く
  • 10問目 なるほど モーわからん
  • 組む サンプルは通る
  • 後輩チーム2つが20より大きい点数を取るまで待つ
  • Submit
  • なんか落ちる
  • 問題文を誤読していた 先頭が決まっているなんて初耳
  • 結局4WAしてAC
  • 9問目 絵がテキトーっぽい
  • N≦1,000と書いてあるのでN^2のDPを組む
  • すでに両後輩チームが38より高い点数をとっているので普通にSubmit
  • AC
  • 8問目 星座と書かれていて戦慄
  • 星座関係無かった
  • 組む
  • ちょうどランキングが凍結されてしまっていたので提出してもいいのかわからない
  • 遠くから「よっしゃ」と聞こえたので一か八かSubmit
  • AC
  • あとからきいたらしっかり後輩達は共に8完以上していたので安心
  • 帰りにさたしゅんとともにサブウェイを食べる
  • 新発売のきのこチーズサンドおいしかった
  • もう少し秋めいて肌寒さを感じるような季節だとなお美味しく食べれそうな一品に仕上がっていた
  • 帰宅
  • この参加記を書く

ボーダーは6完か7完らしいのですが、わたしのチームは最初の6問解けていませんし、4WAも出してしまっていますし、予選落ちです。最後のPCKでした。皆さん有難うございました。

夏季セミナー参加記

JOI夏季セミナー2014に行ってきました。

参加記を書きます。

 

Day1 (8/25)
  • 新幹線速い
  • じょいしのさんとサブウェイを食べに行く
  • おいしい
  • オリンピックセンターに着く
  • 自己紹介
  • 知らない人がたくさん
  • 交流の予感かな?
  • 本を選ぶ
  • Looking for  a Challenge班に春合宿勢が5人あつまる。交流失敗
  • 今回の宿泊棟は談話室が無いらしい。交流失敗
  • 最近オリンピックセンターの仕様が変わったらしく人権が得にくい。交流失敗
  • Looking for a Challengeの問題(53問)を5人に分ける
  • 私は最後の11問を担当
  • Triangleという問題が簡単だったので解く
  • 問1:有理数がN個与えられるのでどの3つをとってもそれらを辺の長さとする三角形が作れるか判定せよ
  • 問2:整数がN個与えられるのでうまく3つを選べばそれらを辺の長さとする三角形が作れるか判定せよ。作れるならその3つを示せ。
  • 数学っぽい。面白い問題だった。
  • 他の問題もせこせこと和訳をしていく
  • セミナーの時間が終わって夜
  • かかさず見ているHERO(月9)があったのでロビー(唯一交流可能な空間)に行かずに部屋にこもる。交流失敗
  • HEROおわったあとにロビーに言ったら人々が麻雀をしていた。kagamiz氏さんとかOBが遊びに来てた。
  • ロビーが11時に閉まるという残念使用。交流失敗
  • 部屋で11問和訳し終える
  • 寝る
Day 2 (8/26)
  • 和訳が終わっているので問題を解いていく
  • 問題3: Nimっぽい問題
  • やっぱりNimだった
  • Nimへの落としこみでエンバグする
  • あきらめる
  • 問題4: 辺に重みがある連結なグラフが与えられるので、各辺についてそれを使う最小全域木があるか判定せよ
  • Easy
  • 問題5:頂点に重みがあるグラフが与えられるので、全ての互いに隣接している3つ組に対して、その3つのうちの重みの最大値をもとめて、それらの総和を求めよ。
  • 自分で考えて提出すると部分点 (O(M√MlogM))
  • 解説を読むとバリバリのグラフ理論でlogを外していた。
  • 面白い、発表に使おう。と決心
  • 講義の時間
  • 決定木というデジャヴ
  • 少しプログラミングの知識がある中高生にアルゴリズムの講義をするときは数え上げお姉さんを使うという王道でもあるのだろうか
  • 2回目だけどフロンティア法の実装がよくわからない。mate配列による空間計算量はどうするのか
  • ともかく面白かった
  • 一般展開図の個数が行列木定理でも止められるというのはあざやか
  • セミナーに戻る
  • 問題6:整数列が与えられるのである長さkの連続した区間の値が全ておなじになるように値を変更するときに、変更量(差の絶対値)の総和が最小になるような方法を実演せよ
  • メジアンの問題ですね 教育的良問
  • 問題7:整数列S,Tが与えれる。Tの中の連続した長さ|S|の区間のなかで|S|とトポロジカル的に一致するものを全部教えろ
  • うーん KMPで解けることは聴いたことがあるけど実装したことがない
  • 解説を読むとどうやってKMPに帰着するか書いてある あざやか
  • しかし今晩CFがあるので組まない
  • セミナーが終わりさっさと風呂に入りCFに出る
  • BGMはキンモクセイのベストアルバム
  • 3問早解きして4問目と5問目を考えてたら終わり 50位
  • レートがあがった
  • 寝る
Day 3 (8/27)
  • 先述の問題7を通す。
  • 問題8:頂点数3Nのグラフが与えられる。サイズ2Nのクリークが存在することが保証されている。サイズNのクリークを一つ挙げよ。
  • うーん うーん NP完全じゃないのこれ
  • 解説を読むと自分の頭の硬さがわかる すごく単純な解答だった
  • 問題9:一般グラフが与えられる。頂点を2グループにわけて、両グループをつなぐ辺を消す。次数が偶数になるような頂点が最も多くなる分け方を一つ挙げよ。
  • うーん うーん むずい 頂点数≦200だし典型ではなさそうだな
  • 解説をよむ。 帰納法! そういえばIOIでもあったなー
  • 問題10:n個のサイコロを振って総和がkになる確率を有効数字2桁で求めよ。
  • シンプルな問題すぎる
  • 有効数字2桁は中心極限定理ゲーだと私は経験で知っている
  • 組む WA
  • 有効数字2桁の真意は大きいnを調べなくていいということだった
  • 普通のDP
  • 問題11:Aさんは0以上1未満の実数をランダムに9個選びます。Aさんはランダムな順番で1つずつ実数を教えてくれます。あなたは教えてくれるたびにそれがAさんの選んだ数字の中で何番目に大きいかあてなさい。正解率が3.3%を超える戦略を実装しなさい。
  • はぁ?
  • 解かない
  • スライドを作り始める。先ほどの三角を列挙する話をかく。
  • LibreOfficeは忘れた頃にクラッシュする。30枚くらいが消える。つらい
  • 本日分のセミナーは終了
  • 今日はオリンピックセンターで選択をする。選択の待ち時間に法学を学びに来ているベトナム人と、自由に関するカンファレンスに来ているシンガポール人のひととお話したりする。スライドを作っていたらグラフ理論を先行している人に声をかけられたりする。
  • スライド完成!
  • 夏季セミerと交流しないでどうする。交流失敗
  • 一つだけ洗濯物が汚れが落ちきっていなかったので明日も洗濯しようと思う
  • 夜はhogloidさんの部屋に行って「薔薇と髑髏」というゲームをする。キルミーベイベーは面白い。
  • ねむくなったので寝る。
Day 4 (8/28)
  • 起きたら8:30 朝飯1完
  • スライドはできているし暇
  • 午前ずっと寝てしまった
  • 午後は他の人担当の問題をみる。KangaroosとLeonardo numberの解説を読む。
  • この二つの問題はもっとも解説が長い問題だったが、実は作問者回と筆者回が違うので両方載せていた。だから2倍ページが割かれるというからくりだった。
  • Leonardo numberは筆者いわく「私がこの問題に出会った時は数学に関する知識がなかったので解けなかった。作問者から解説を聞いて面白いなと思い自分なりに考察してみたら、想定解より速く実装も簡単な解法を思いついたので紹介するね。」
  • プロ
  • Kangaroosは筆者いわく「この問題はすごく単純な問題だからきっと典型な手法の組み合わせで解けると思ったんだ。そして僕はそういうふうな解き方を思いついた。だけど実は作問者はちょっと複雑だけどもっと速い解法を用意していたんだ。おもしろいから両方紹介するね。」
  • プロ
  • Kangaroosは作問者想定解より筆者想定解のほうが面白かった。
  • いくつかの区間に関するクエリ処理の問題がなんと巡回セールs ゲフンゲフン ネタバレはよしておこう
  • 面白いやで
  • 寝る
Day5 (8/29)
  • まこりん誕生日おめでとう!
  • みんな発表
  • ちょっと国際交流棟のあの部屋のスクリーンは見にくかったので来年は使いたくないなと思った
  • 我々の班はもうちょっとリハをするべきだと思った(ちょっと見にくいスライドがあった
  • まぁ時間通り終わってよかった
まとめ

楽しかった。運営はちょっとウーンだったけどLooking for a Challengeを見れたのでよかった。

競技プログラミングのための音楽

こんにちはきゃたぱるです。キャットアッパーです。

競技プログラミングをする時にオススメの作業用BGMを紹介します。

クラシック編

作業用BGMを聞きながら参加できる競技プログラミングは問題文が日本語でないものが多いです。すると歌詞付きの曲や、ポピュラー音楽だとReadingの妨害になることがあります。クラシックの曲は使われる楽器の音や流れのマナーがいい感じに穏やかなのでコンテスト序盤に役立ちます。長い曲が多いので、一曲だけでコンテスト全部をまかなえることもあるでしょう。注意点として、人によっては飽きるということです。

ボレロ


ボレロ/モーリス・ラヴェル【ミューズ交響吹奏楽団】 - YouTube

ボレロはおよそ同じ戦慄が100回以上繰り返されてゆるやかにクレッシェンドしていく曲です。問題の読み始めにほそぼそと曲が始まり、コンパイル成功時にはオーボエが鳴り始め、SubmitしてACの表示が出ると同時にシンバルが鳴る。このような流れをイメージすると調子が乗ってきてスムーズに問題が解けます。

新世界より 第三・四楽章


「新世界から」第3楽章 - YouTube

普通に曲を嗜むときは、第一楽章から聴くほうが良いのですが、BGMとしては第三楽章くらいから始めて聴いたほうが良いと思います。第四楽章の有名なフレーズに8分程度で到達するので問題文を読んで理解するのにちょうど良い時間でしょう。第四楽章の中盤のくるくるまわるところは頭にじんじんきて全完のちからを与えてくれます。

「惑星」より「火星」「木星


組曲「惑星」より「火星」 ホルスト - YouTube

「惑星」の中で有名な2つです。「木星」を知らない人はいないでしょうから、こちらの方がより確実に調子を整えてくれるでしょう。「火星」も終盤あたりが良い感じ(小並感)なのでお勧めです。

交響曲第9番


ベートーヴェン 歓喜の歌 交響曲第九番 Beethoven Symphony No 9-video ...

年末のコンテストとかに良いでしょう。すこし短めなのでコンテスト中盤辺りにかけるのがお勧めです。展開が速いので思考のペースを曲に合わせるのがやや難しいです。全完した後や、もうやることがなくなった時に喜びの表現としてこの曲を聞くのもよいでしょう。

インストゥルメンタル

クラシックもインストゥルメンタルですが、もっとポピュラー音楽よりのインストゥルメンタルにも違った良さがあります。ズンチャズンチャと踊るために作られた曲だったり、ヒーリングのために作られた曲だったり、いろいろな用法用量がありますので、自分にあった曲を探すのもよいでしょう。今回は曲名ではなくて作曲者、もしくは演奏者を紹介していきます。

Jazztronik


Jazztronik - set free - YouTube

ミキサー以外のメンバーがぐるぐるしている様々な雰囲気の曲を作るJazztronikです。ピアノ色が強い曲から、最近ではポップな曲も多いです。多くあるアルバムの中から自分の好みのテイストの曲を探してみてください。インストだけではないので、いろいろ試すとよいでしょう。

姫神


神々の詩 姫神 大地の風景 - YouTube

ヒーリング・ミュージックでは有名な姫神です。コンテスト開始前とかに聴くと落ち着けてよいでしょう。

DEPAPEPE


DEPAPEPE ONE - YouTube

ギターで歌うDEPAPEPEです。軽快で明るい音を爪弾くので、コンテスト中のテンションの調整の妨害に鳴ることはありません。いくつかクラシックの曲もDEPAPEPE調にアレンジしてカバーしているので、そういうのが好きな人にもお勧めです。

ナニワエキスプレス


SESSION'83 NANIWA EXPRESS 「RED ZONE」 '83 ...

上方フュージョンナニワエキスプレスです。テンポがよくうるさくない、良い感じ(小並感)の曲調です。

池田亮司


池田亮司 + / - [ the infinite between 0 and 1] キュレーターインタビ ...

電子音楽の人です。0と1がビンビンする感じが頭にじんじん来て全完まちがいなしでしょう。作業用BGMにすごく適している曲が沢山です。

J-POP編

あまりお勧めとかないです。皆さんの好みの楽曲を聞くのが一番だと思います。終盤辺りにかけるとアクセルがかかって良いのではないでしょうか。アニソンがJ-POPかどうかは怪しいですが、アニソンとかも好きな人には良いとおもいます。ぴょんぴょん。

 

その他

新谷良子


新谷良子-WonderfulWorld(歌詞字幕付き) - YouTube

いいよね~

 

まとめ

最後のやつはただの私の好みです。ごめんなさい。

BGMに向いてる曲、向いてない曲、いろいろありますが、その曲が好きで、コンテストに一緒に臨む心意気さえあればなんでも作業用BGMになりえます。上の方であげた、クラシックもインストも新谷良子も、人によってはBGMにならなかったりするでしょう。みなさんも自分にあったBGMを探してNice Music, Nice Contest.でがんばってください!プロ!