Staff

山口 洋 †

2010 年にスタッフになって以来、2014年の夏合宿まで長らく OB/OG の会の中核スタッフとして活動してまいりましたが、引退しました。思えば、ほぼすべてのコンテストで作問スタッフ・オンサイトスタッフとなり、半分程度についてはプロジェクトマネージャ的な仕事に加え渉外等もしてきました。しかしながら、老いには勝てずここ1,2年は最近の流行を追うこともできませんでした。そろそろ潮時かと思っていたところようやくスタッフに恵まれ業務を引き継ぐことができた次第です。

これからもOB/OGの会をよろしくお願いします。論文を育成するゲームをしつつ余生を楽しみたいと思います。

2014.10.1

---

かつてのチーム †

TwinTails -> 永遠の初心者 wakaba

地区大会は例外枠で... (2009)

所属 †

東京大学情報理工学系研究科博士 2 年 (at 2014)

ツール †

• pukiwiki から問題文を生成するツール https://github.com/hiroshi-cl/prostagen

ソースコード †

NYSL Version 0.9982 でどうぞ。

ライブラリ †

• サイコロ (ソースコード)

2013 模擬地区予選 †

• A: Broken Signal Audio
  • 解法1: 候補を試してみる (ソースコード)
  • 解法2: 区間を縮小していく (ソースコード)
• D: Everlasting -One-
  • (ソースコード)

2013 夏合宿4日目 †

• B: Trodden Cable
  • (ソースコード)
• F: Graph Automata Player
  • (ソースコード)
  • 毎年というわけではありませんが、線形代数の問題 (累乗・掃き出し法) は出るのでなんのひねりもない問題を出しました
  • フルランクでない掃き出し法の問題も 2009 年などに出題例があります

2013 模擬国内予選 †

• D: 沈みゆく島
  • 須藤さんのコメントを見てくださいな
  • (ソースコード)
• E: 小野小町の編集合戦
  • これと A 以外は模擬国内予選のために新しく作ったので2番めに古い問題 (2010)
    • Aは2005年(記念すべき初回?)の模擬国内予選のためだったもの...
  • (ソースコード)
    • 長いがエラー処理を除いたりコピペしたりすればそんなに面倒じゃないです
  • 構文解析系問題出ましたね
  • 気付かなくてもα-βで8くらいまではいけるそうです。(金子さん情報)
• G: 鏡の迷路
  • 原案でした 最初

    凹多角形の共通部分を最初に計算しろ

    とかいう無茶を言ってすいませんでした (要りません)
  • 最初から須藤さんの方針が見えていれば準備が紛糾することも...
    • 解説はこっちになっています

2012 春コンテスト †

• 諸事情によりお休み中でした
• Tree Reconstruction
  • 線形代数枠として模擬地区予選用に手伝ったのがリサイクルされました

  元ネタ

  • サブルーチンがあるので各行の実行回数を測定したい
  • しかし、すべての行でカウントすると遅くなるので、フロー保存則でカウンタの数を最小化したい
  • どうすればよいか

  解法について

  • 線形代数枠として、フロー保存則から連立方程式を立てて rank を求めてもらう
  • ...つもりだったけど、よく考えると実は rank は連結成分の数だけで一意に決まってしまうので UnionFind を使うだけ。おしまい

  強連結でない一般の場合

  1. 戻ってくる辺がないならその辺の流量は0でなければならない
  2. すなわち, 強連結成分間をつなぐ辺の流量は0で確定するので値を持っておく必要がない
  3. ゆえに, 強連結成分分解して成分の数を数えるだけ

  • ちなみに, 連立方程式を立てて rank を求める方法はうまくいかない

2012 模擬地区大会 †

• G の原案と入力・解答 (と没問題) 担当でした
  • (ソースコード)
  • ヒエログリフをモデルに変な構文解析問題を作ってみました
    • 参考 > http://ja.wikipedia.org/wiki/%E3%83%92%E3%82%A8%E3%83%AD%E3%82%B0%E3%83%AA%E3%83%95#.E6.96.87.E5.AD.97.E3.81.AE.E7.89.B9.E5.BE.B4
  • 一風変わった構文解析問題は地区大会では割と定番です
  • なんだかんだでパターンマッチして再帰降下するだけです
  • 入力たち Visualizer;
    
    
    
    
    
    
    
    
    
    
• C, E, J のお手伝いもしました
  • J;

2012 夏合宿4日目 †

• A, E, H の担当でした
  • A は国内 E にしては簡単すぎとか言われたのですが、そこまで簡単ではなかったようです
  • E はサイコロの呪文的な
  • H には蛇口から濁り水が出た野田さんの恨みが詰まっています

2012 模擬国内予選 †

• E: The Enemy of My Enemy is My Friend (ソースコード)
  • 解説に書いてありますが, ノード数の上限がいくつに減るかが理論的にわかる方法により適切に計算量を見積もった上で通せるようになっています (ヒューリスティクス的な枝刈りは必須でない)
  • 色々な枝刈りを楽しんでね
  • 半分全列挙もAOJで通るはず
• E の Sample Input たち
  1. Esolang で縦読み (元は現存する国名だったのですが政治的配慮で差し替えました)
  2. 戦国の七雄 (登場人物の数がちょうどよかったので)
  3. マウリヤ朝とその周辺 (The Enemy of... の出典にちなみました)
  • 実は大きい方から貪欲でも通ってしまうようにサンプルの数字を細工しました
  • E 問題を解くような人はまさか貪欲で通るなんて思いませんよね?
    • とは言っても近似になっていることがよくあるので、枝刈りに活用できたりもしますね

余談 †

• 実はOB/OGの会には山口がもう1人いたりして, しかも所属が東大なのでフルネームでお願いします。。

github †

• https://github.com/hiroshi-cl

過去のページ †

• 2011
• 2010