tozangezan's diary

勝手にソースコードをコピペして利用しないでください。

PKUについて紹介

PKU 企画

見出しの使い方がわかりません。

この記事がCompetitive Programming Advent Calendarの23日目の記事に当たります。

JOIについてはあんまり見つからないので、PKUについて紹介したいと思います。

PKUというのは(よくPOJという名前で聞く人が多いかもしれませんが)このサイトです↓
http://poj.org/

どうやらPKUというのは北京大学自体をさすので、このジャッジ(北京大学オンラインジャッジ)はPOJと言うのが正しいはずなのですが、それなりに多くの人が自分含めPKUと言ってるのでPKUと言うことにします。
(これに対してAOJとかZOJとかSPOJとかSGOJとか言うのはなんでなんでしょうかね…　じゃあBNUは…)

・PKUとは
AOJの北京大学版です。問題が多いです。世界各地のいろいろなコンテストの過去問がかき集められています。一応最近も問題は増えていますが、そのペースは一時期より少ないようです。(POJ Monthlyがなくなったのも一因？)。
ちなみにAcceptedが青字でCompile ErrorとかRunning&JudgingとかCompilingとかWaitingが緑字で、WAやらTLEやら(略)は赤字です。ごくまれに赤がどうだ青がどうだとか言うのをPKUで使っているときは、こんな用法かもしれません。(自分以外に使ってる人見たことありません)

・だいたいの使い方

  1. とりあえずRegisterしておきます
  2. 好きな問題を開きます
  3. 解けたらソースを送ります(使える言語はC,C++,GCC,G++,Java,Pascal,Fortranで、C++とG++なんて編集距離1Byteなのに実行速度やら誤差やらにいろいろ違いが出ていて、なかなか謎です。経験からしてqueueはG++のほうが速くて、他はC++のほうが速い（？）)
  4. ソースに対するレスポンスが帰ってきます。
  5. ACがもらえます

・残念な点

  • 英語がときどき違います。文法的に問題があったり、そもそも誤字脱字があったり…
  • 日本語の問題はほとんどありません。ごくまれにあります。
  • 中国語の問題も結構あります。正直言って読めないので、飛ばすなりなんなりしてもいいと思いますが、最近は和訳してくれる人が結構いるので助かってしまうことも。
  • おそらく-O2のオプションがついていません。なので実行が遅くなります。
  • そして、PKUで目立つところは、ときどきTime Limitがやたらと厳しい問題があることです。たとえばHuge input, scanf is recommended.と書いてあるのにscanfを使うとTLEしてgetsを使わないといけなかったり、入力するのを答えが出たら途中で中断してgetsで読み飛ばしたり、vectorだとTLEするので配列を使ったグラフのデータ構造に変えたり、よくわからない定数倍改善をしたりetc
  • ちなみに、問題文に矛盾したケースがある問題もごくまれにあります。
  • 本来の問題にはSample Input/Outputが2組あるのにPKUでは1組しかない問題があります。残念ですね…

・うれしい点

  • JavaのTime Limitはかなり余裕があります。だいたい(普通のLimit)*3+ちょっとだと思っておけばよいです。しかしたまに(入力ファイル数の多い問題はJavaのほうが不利になったり、Javaだと無理ゲーに近いものもあります)
  • ShortCodingが専門のものでない中では盛んなほうです。僕はしませんが。
  • 飽きるほど問題があります。しかし悪問も多いです。

・精進
はい。がんばります。

・本編
とりあえずランダムで問題番号を入力して、その問題の出典についてなんか特徴とかを知っていたら書きます。飽きるまでやります。まずは……

  1. Southeastern Europe

PKUには80題(うち20問ほどSolved)
ICPCのどこかの地域です。EuropeのICPCの地域は似たような名前が多すぎてよく覚えられませんが、こんな問題があります
http://poj.org/problem?id=3067Japan(Japanなのに日本語の問題文はありません)
http://poj.org/problem?id=1455Crazy Tea Party(いままで牛が登場すると思っていたので、USACOだと思っていました。パズルです)
説明できない！次！

  1. USACO

PKUには195題(うち172問ほどSolved)
JOIのアメリカバージョンだと思っておけば大体あっています。JOIと違ってオンラインのコンテストは他の国の人でも出られます。クロアチアかどっかのOIが最近一部の人の間で流行っていると思うのですが、USACOもその一種だと思います。
rng_58さんの記事でうしが出てくることは有名になっていると思いますが、多くの問題で登場するのはFarmer JohnとCow Bessieであり、たまにBessieじゃない牛(名前のついたBessie以外の牛はPKUにはいた印象があんまりなくて、最近(2009？2010？)のUSACOにBessieじゃない牛がいた気がします)が出ていたり、Johnじゃない農夫(Bobがいます。Farmer Johnの妨害をしていました)が出てきたりします。
USACOはなかなか良問が多い(と自分は思っている)ので、お勧めの過去問集としておきます。問題番号を入れる枠にUSACOと書いてEnterを押すとUSACOの問題がざーっと出てきます。
ちなみにGreen,OrangeやらGold,Silver,Bronzeやらで難易度が分かれているので、競技プログラミングになれたばかりの人はOrangeやらBronzeやらの問題を埋めてみるのもいいかもしれません。そういうときも問題番号の枠にBronzeとか入れるのが多いに役に立ちます。
ちなみに、USACOは牛に関する相当マイナーな英単語が出てきますが、正直そんなの読まなくてもいいと思います。
こんな問題があります。
http://poj.org/problem?id=3663Costume Party(ハロウィンです。なのに牛をつなげるらしいです)
http://poj.org/problem?id=2391Ombrophobic Bovines(初見でこのタイトルを和訳できる人はいますか？)

  1. POJ Monthly

全280問(うち76問Solved)
POJ Monthlyの名のとおりMonthlyにPOJでやっていたコンテストのようです(最近全く開催されているのを見かけません。)
Writerがなかなかすごい人たちです(たとえばTopCoderで知らない人はいないであろうACRush(Lou TianCheng)氏や、韓国で有名なkcm1700氏などがWriterをしています。
データ構造の問題が豊富にある印象。しかしTime Limitがこれでもかってほど厳しい問題がPOJ Monthlyには多いことが残念ですね…
http://poj.org/problem?id=2985このくらいのゆとりSegTreeは癒される
http://poj.org/problem?id=3213これも面白い

  1. World Finals

へんなの引いちゃったよ。ICPCの決勝ですよね、ぜんぜん問題数ないですが。
http://poj.org/problem?id=1888こんなつまんない実装しかといてない

  1. South America

こんなコンテストしらねーよ…
http://poj.org/problem?id=1297初心者向けDPだと思います。
一応こういうはじめてみるようなコンテストでも解いた問題があるのが奇跡。まあ1000ACはしてるからなぁ。

  1. Greater New York

PKUに77問。(うち半分ほどSolved)
なかなか簡単な問題が多い気がします、が、難しい問題もちゃんとあります。PKU始めた当初に結構片付いていたと予想。
http://poj.org/problem?id=3784これも解けたとき感動しました

おい！もうじき説明しがいのあるコンテスト出ろよ！

  1. CTU Open

CTU FEE Localというよく分からないコンテストもあるので、こっちも一緒に話しておきます。
PKUに55問。多分10問ほどSolved
CTU Openはそうでもないのですが、CTU FEE Localは問題が難しくないのにも関わらずAC数が2桁です！それはなぜでしょう？
答えはここにあります。
f:id:tozangezan:20111223231906p:image
!?!?!?!?　これは何語　!?!?!?!?
出力が意味不明なので解いてる人が少ないと思っています。何語だったっけ、チェコ語だっけ。
http://poj.org/problem?id=2115出力もさすがに英語になりました
(2回連続でCTU引いてしまった)

  1. Central Europe

PKUに94問。あんまりといてません
紛らわしい名前ですね。ずいぶん古い問題が多いらしい。
http://poj.org/problem?id=1102暇な人はこんなのでも解いていればいいのではないでしょうか

  1. IOI

PKUに35問。16問Solved
IOIです。イタリアです。イタリア行きます。代表になります。
ちなみにPKUのIOIの問題は一番新しいのでも2003年という過去仕様なので、難しくない問題だって沢山あります。
http://poj.org/problem?id=1163初心者向けDPです
IOI行きます。はい、IOI行きます。

  1. National Programming Invitational Contest Host by ZSTU

こんなに長い名前の知らない。

  1. Northeastern Europe

PKUに293問(たくさんのSubreagionの問題を含めて)
出典提供のなかではかなり上位に入りそうなコンテストです。ちなみに良く考えてみればわかりますが大部分はロシアで占められています。
Far-Eastern Subreagionにいたっては(すごく大きいsubreagionですが)日本のすぐ近くまで範囲です。
ちなみにFar East Nightbirdとは無関係です。
http://poj.org/problem?id=2201Cartesian Tree
あまりに大規模だけどICPCであるので特徴がよくわかりませんが、
FarEasternは入力ファイルがたくさんあります。

  1. Waterloo local

PKUに175問(たぶん40%はSolved)
これも沢山問題を提供していると思っていたのですが、案外少なかったです。このコンテストは入力は1つのファイルにたくさんある形式です。
簡単な問題が結構沢山あるので初心者はWaterloo Localと窓に打ってSolvedが多いものをやるのもいいかもしれません。
http://poj.org/problem?id=2663簡単なDPです
http://poj.org/problem?id=3645簡単な構文解析です
http://poj.org/problem?id=2335悪問です。
http://poj.org/problem?id=2405数学です。

  1. Tehran

PKUに121問(ほとんどといてません)
正直こんなにたくさんあったことが驚きなのですが…
http://poj.org/problem?id=1972まあパズルです

このコンテストが出たらやめるというものを決めているのにそれが出ないのです…

  1. Ulm Local

PKUに96問(半分以上はSolved)
どこの国だかよく覚えていないので調べてみたら大学名らしいです。Waterlooみたいな感じです。
簡単めの問題が多い印象。
http://poj.org/problem?id=3370解法が面白いです　斜体と太字だけでPOJ Monthlyだと思い込むクセ何とかしないと…

  1. Northwestern Europe

似たような名前の地域が次々と…
PKUに61問(12問くらいSolved)
これといって印象に残る問題が無いですが、難問を放置しているからかもしれない。

  1. Svenskt M〓sterskap i Programmering/Norgesmesterskapet

なんてかいてあるの…

  1. Ural State University Internal Contest

PKUに16問。知らないコンテストですが結構といてます(長いのは覚えられません)

  1. Noi

NOIといってもこれは多義らしいです。PKUにあるNOIは多分中国のコンテストなので、問題文は全部中国語です。
ちなみに亜種が多すぎて全く把握できない。
http://poj.org/problem?id=1186例のあれです
http://poj.org/problem?id=1185例のあれです

  1. Asia Regional Contest

アジアの地区大会？Aizuと書いてあることからして会津大学でやったっぽいです。
でもこの会津のときのしかないや
http://poj.org/problem?id=3941newわからないとどうしようもなくなるような

  1. Beijing

どうみても北京のコンテストです

投げやりになってきました。

  1. ACM North Western European Regional Contest

これさっきのとおんなじだろ！

  1. Rocky Mountain

これも結構見ますが、なぜRocky Mountainなんだろう？
PKUに37問。
http://poj.org/problem?id=3437探索です

  1. Mid-Atlantic

北極圏？意外と解いていました。
PKUに50問、1４問くらいSolved
1004と1005というかなり初期のものがこの出典です(知らなかったけど)

  1. East Central North America

何でもEastとかNorthとかつければいいってもんじゃないんだよ！いい加減解放させてくれよ！

  1. MIT Programming Contest

MITとは多分あそこのことだと思います。PKUにはあんまり上がっていません。

  1. Tokyo

普段はこんな出典では記述されません

  1. Japan

(ランダムで引いたわけでもないのに終わりにしたくなったのでJapanと入力しました、これで最後にします)
PKUに90問(30問弱Solved)
AOJに全くおんなじ問題が上がっています。AOJはTimeLimitがゆるいです。AOJには日本語の問題がおいてあることもあります。
さすがに日本のコンテストのジャッジは日本のサイトが良いのでしょうね。ちなみにJapanの大会はテストケースが本当に豊富なのですが、これ全部手で入力させる気なのでしょうか。
http://poj.org/problem?id=2044悪問
http://poj.org/problem?id=2045悪問
http://poj.org/problem?id=1981PCKのあの問題の元ネタ？
http://poj.org/problem?id=3009実装
http://poj.org/problem?id=3327おかしな入力

・おわりに
こんなに長い日本語を打って気が狂いそうです。嘘です。でも確かにかなり気疲れしました。
ところでPKUのなかなかに種類の多い出典をみんなに分かってもらえれば満足できます。PKUに登録してみんなやってくれても満足します。適当に競技プログラミング初心者に広めてくれるのも満足します(TopCoderのほうがいいとも最近良く耳にしますね)。
ちなみに過去の話。
中2のときにJOIに初参加して競技プログラミングというものの存在を知り(Bランクだけど！Bランクだけど！！)、semiexpと同じ部活であることを利用して、っていうと変だなぁ、まあsemiexpによってPKUというものを教えてもらいました。
その後中3のJOI予選まではJavaだけでそれなりにコーディングをして、(多分100問も解いてない？)、無事に予選通過して、一応問題演習としてPKUをして、本選にいって、そこでようやくAOJというものを知ることになりました。すなわちそれまでの間、AOJを知らなかった僕は、競技プログラミングの練習の場はPKUにしかなかったわけで、PKUにはそこらへんの思いがあります。
さてその後本選も通過して、合宿に行って、そしてそこでTopCoderというものを知るんですね…はい。過去の語りでした。すみません。

25日(Calendar最終日)も近くなりましたね。あとの数人もがんばってくれると期待しています。それではさようなら。
f:id:tozangezan:20111224001729p:image
PKUさすがだよ、なんでこんなページでスペルミスするのさ……(Recent Rankingにて)