Hatena::Grouptopcoder

ir5は引退した

|

2014-05-05

JAG スタッフと topcoder writer を引退します

22:17

タイトルのとおりです.せっかく引退するのでエンジニア界の退職エントリっぽく引退エントリを書くことにします.

これまでの活動

JAGでは10ヶ月ほど,topcoder では3年ほどプログラミングコンテストの作問者として活動していました.

JAG では2013夏合宿,模擬地区予選,春コンテストの運営に携わりました.やったことは主に問題作成担当ですが,夏合宿の最終日に部屋点検なども行いました.春コンテストの Tokyo Olympics Center は,合宿スタッフが大変だったことを表す問題として作りました.

topcoderでは SRM 498 くらいから今日に至るまで色々と問題を書いていました.気づけば60問弱くらい書いていたようです.最後の方になってからはフルセットで作る時間がないので Hard だけ書いたりしていました.

作問では良い題材を見つけるのが大変です.高難易度の問題を追求するのが難しいのはご想像がつくかと思いますが,低難易度のものでも面白いものを考えようとすると楽ではありません.適当に思いついた問題は,ほとんどの場合,多項式時間で解けるが典型的でつまらないか,指数時間かかってしまうかのどちらかです.で,ちょうどほどよい(多項式で解けるし面白い思考を要する)問題がそれら両者の中間にあるという構造になっているような気がします.良い問題を考えたい際,いつも次のように考えていました.まず,適当に問題を考えます.これはなにかの名前ドリヴンだったり,数学的な構造ドリヴンだったり,ストーリードリヴンだったり,色々です.僕は,シャワーを浴びている時とか外を歩いているときにぼんやりと考えるのが好きでした.このとき,いきなり考えた問題は,まず大抵の場合は典型でつまらないか,工夫しても効率よく解けないかのどちらかになっています.それを,制約を緩くしたりきつくしたりをうまく調整することで,良い問題につくり上げるよう試行錯誤をしていました.制約をどう変えれば面白くなるかは,作問者の自力に強く依存しています.制約を変えて解けるかどうか分からない問題が生まれた結果,その問題を解けると信じて考えを進めるか,見切りを付けて捨てるかを判断する必要があります.これには苦労が伴いますし,うまくいかなかった場合に時間を浪費してしまうこともよくありました.

topcoder に出した最後の問題は SRM 619 の SimilarSequencesAnother でした.制約が小さいので簡単そうですが,方針を見失いやすかったり,正しい方針を見つけても実装が結構ハードなので難しいと思います.解法自体は割と典型的なのですが….

引退する理由は,単に社会人になって時間を割くのが難しいと感じたためです.(しかし他にも理由はあります.)

今後の活動

JAG,topcoder では活動を休止しますが,今後も人によってはまたどこかでお会いするかもしれません.詳しいことはまたいずれ…

あ,あと Fox Ciel さんは今後も問題文に自由に使ってくれていいです.(当たり前ですけどあんまりひどい扱いはしないでください)

あとどうでもいいですけど個人的には Fox Ciel さんは20才くらいで胸がでかいイメージで Fox Jiro くんは小6くらいのイメージです.(超どうでもいい…)

2013-12-25

2013年振り返り

00:39

2013年ももうすぐ終わりなので今年を振り返ってみたいと思います.

作ったもの

ICPC/JAG非公式難易度表

これ(とichyo君が作ってくれたAOJ-ICPC).JOI非公式難易度表とかIIDXのDP難易度表に触発されて正月に3日位かけて頑張って叩き台を作った.

プログラミングコンテストでは毎年多くの問題が生産される.ICPC公式で16~17問,JAGで40~60問程度.その中には良い問題もあればそれほどでもない問題もある.現状だと良問を残していくような仕組みがあまりないのでなんとかしたいなぁと思ったのが始まり.( 個人がブログの記事でまとめたりとかはよくあるけど….) 最近放置気味である.

色んな人が投票してくれたおかげでだいぶ整理されてきた感じがします.皆様ありがとうございます.

Google Docs でやると意見の交換ができなかったり表計算が爆重だったりして不便なので専用のシステムがあれば便利だろうなーと思ってるのだけど時間がなくてそこまでできてない.

AtCoder Statistics

これpythonの習作.コンテストの振り返り用ツールみたいな感じにして,コンテスタントと運営者のモチベアップにつながるような風にできたらいいなーと思ってつくった.が,1ヶ月くらい放置していて管理するモチベが低下している.(まぁotinn.comとかあるけど頻繁には見ないしそんなもんだよねーみたいなかんじ?)

運営

  • KUPC'13
  • SRMいろいろ
  • JAG'13夏,模擬地区予選

コンテスタント

  • 1月の最初の方に ICPC World Finals に行けないことが発表されたので引退.
  • 引退してるけど TCO'13 オンサイト行った
    • 座ってるだけ楽しい……

2013-06-29

KUPC2013

00:03

久々の記事です.宣伝をします.

今年も KUPC こと京都大学プログラミングコンテストを開きます.

http://www.kupc.jp/

KUPC2013は7/6(土)に開催します.

例年通り,AtCoder上でコンテストを開催します.コンテストページはこちらです.別に前もって参加ボタン押さないといけないとかはなかったはずですが,大まかな人数を把握したいのでご時間のある方は前もって登録してください.(謎)


例年通りオンサイト会場を設けます.京大内と渋谷に会場が設けられます.

京都会場 : http://atnd.org/events/40783

東京会場 : http://atnd.org/events/40780


問題の傾向はいつもどおりなのかな… よくわかりません.今年から新しく hirosegolf さんと asi1024 君がジャッジになってくれたので,そこは見どころ? かもしれないです.

あと,例年からの変更点として,今年は問題ごとに異なる配点が割り当てられているかもしれません.

皆様のご参加をお待ちしております.

2013-01-19

ARC011 D

03:36

ARC011のD問題の原案を担当していました.問題文はこちら

せっかくなので解説を置いておきます.

問題の整理

入力の直線を L[1], ..., L[N], 点を P[1], .., P[M] とします.

dist_l(x, y) := 点(x, y)から直線L[1],...,L[N]への最短距離

dist_p(x, y) := 点(x, y)から点P[1],...,P[M]への最短距離

とおきます.このとき,

です.最適化したい式は

すなわち

です.

領域の分割

最適化したい式が max [min... + min ...] とかなっていてウザいですね.

ところでこの中のminは (x, y) がとりうる領域を限定すれば外すことができます.

とおきます.R[i]は最も近くにある直線がP[i]であるような領域,S[j]は最も近くにある点がP[i]であるような領域です.

S[j] はボロノイ図のP[j]が属する領域で,これはP[j]と他の点の間についてそれぞれ垂直2等分線をとって,P[j]を含む半平面について共通部分を取ったものになります.

R[i] も同じような感じで,L[i]と他の直線についてそれぞれ交点で角2等分線を取って,L[i]側に近い方の領域の共通部分を取ったものになります.

こうすると,

R[i]上では dist_l(x, y) = dist(L[i], (x, y))

S[j]上では dist_p(x, y) = dist(P[j], (x, y))

となりますから,領域を (x, y) ∈ R[i]∩S[j] とかに限定すると最適化したい式は

とかになってちょっとスッキリします.

式の整理

dist_l はどういう関数なのか見てみます.点と直線の距離を思い出すと,これは

という式で表されました.つまりx, yの線形関数の絶対値です.

一方で dist_p は単にx, yの2次式です.


というわけでdist_l の項に絶対値が入っていてまだちょっとウザいので軽く整理します.

領域R[i] を,L[i]の右側か左側かで分割して,R[i][right] と R[i][left] とします.

こうすると R[i][right], R[i][left] では点と直線の距離の絶対値記号は外れてくれるので,最適化したい式は結局x, yの2次式(で,x^2, y^2の係数は1, xyの係数は0であるようなもの)になり,円の式であるということになります.


領域R[i][*]∩S[j] は多角形のような領域でしたが,このとき円の式が最大値を取るのは多角形の角の部分しかありえません.

この考察を使うことにより,調べるべき(x, y)の点の候補が非加算無限個から多項式個くらいに減ります.

ところで,この多角形の辺は

  • L[i],L[j]の角2等分線
  • P[i],P[j]の垂直2等分線
  • [-R,R]^2のボーダー

のいずれかで構成されているので,調べるべき候補は結局これらの辺の交点であることが分かります.

以上のことをまとめると計算量 O( (N^2+M^2)^2*(N+M) ) くらいでできることになります.

2012-05-24

あなたとJava

04:29

入学してから4年くらいずっとC++使っててそろそろ飽きてきたのでJava+Eclipseでも使ってみようという気分になって色々調べた.

とりえあずコンテスト厨なのでコンテスト的な用途を想定しています.

main関数

static 修飾子付けるのだるいので main の中で自分自身を new して呼び出している人が多い.

public class Solver {
  public static void main(String[] args) {
    new Solver().run();
  }

  void run() {
    // ...
  }
}

インクルード的なの

C++と違って何十行も書かなくてよくて便利.

import java.io.*;
import java.util.*;

入出力

読み込みは BufferedReader (+ FileReader) + StringTokenizer がゴールドスタンダードなんだろうか.Scannerを使う人もいるけどScannerはBufferedReaderに比べると遅い? とか(ちゃんと確認してない)

Eclipse上だと標準入力のリダイレクトがどうもできないっぽくて,Javaからインプットファイルを直接読み込むような機構にしている人が多い.

出力は PrintWriter 使うと便利なのかなぁ.

  void run() {
    try {
      in = new BufferedReader(new FileReader("<入力ファイル>.in"));
      out = new PrintWriter(System.out);
      solve();
      out.close();
    } catch (Exception e) {
      e.printStackTrace();
      System.exit(1);
    }
  }

  BufferedReader in;
  StringTokenizer st;
  PrintWriter out;

  String nextToken() throws IOException {
    while (st == null || !st.hasMoreTokens())
      st = new StringTokenizer(in.readLine());
    return st.nextToken();
  }

  int nextInt() throws IOException {
    return Integer.parseInt(nextToken());
  }

  long nextLong() throws IOException {
    return Long.parseLong(nextToken());
  }

  double nextDouble() throws IOException {
    return Double.parseDouble(nextToken());
  }

  void solve() throws IOException {
    // ...
  }

ここまでテンプレで実際に解くときは solve に書いていく感じになると思う.テンプレ微妙に長い.


基本

java.langは人権っぽい,目を通しておいたほうがよさそう.


配列は

char[] charArray = new char[50];
String[] stringArray = {"Sunday", "Monday", "Tuesday"};

みたいに書く.普通.clone,arrayCopyはシャローコピーとか言ってて不穏なので配列コピーしたいときはループ回してばしばし入れるのが無難か.


STLとの対応とか

ドキュメント(Java SE 6)


  • string : String ただし immutable なので mutable にしたいときは toCharArray() で char[] に変換するのが無難? あと比較するときは == じゃなくて equals 使えとかあった気がする
  • vector : ArrayList ?
  • queue : Queue 普通のキューは LinkedList で,ヒープにしたいときは PriorityQueue 使うといいんだろうか.ちなみに Java の PriorityQueue はC++と違って pop したときに大きい値からじゃなくて小さい値から出てきてくれるので良心的. see also : Comparator
  • map : HashMapTreeMap 前者は要素をソートしないが後者は要素をソートする.
  • set : HashSetTreeSet
  • bitset : BitSet
  • algorithm : Collections
  • sstream : StringTokenizer に突っ込むと楽かもしれない

他にも正規表現とかできるらしいです.

数学系関数はMathに基本的なのが揃っている.


その他

  • プリミティブは関数に値渡ししかできないのでswap関数定義するのむり
  • operator overload は甘え
  • マクロは甘え
|