お知らせ
- 講評(kagamiz, kyuridenamida, japlj)を公開しました. (2014/11/15) NEW!
- A ~ F 問題までの解説を公開しました. G は後日公開予定です.(2014/11/15) NEW!
- このページを公開しました. (2014/11/15) NEW!
講評
kyuridenamida
皆さん，コンテストお疲れ様でした．楽しんで頂けましたでしょうか．
僕はもともとこのコンテストのメインメンバーだった気がするのですが，いつの間にか非アクティブ並の出現度になっており，受験や卒論・文化祭・高専プロコンを理由に仕事を先延ばしにし続けていました．
ていうかそもそも発足は一年以上も前だった気もするのですが，僕の作問した問題は1問もありませんでした．僕は何をしていたのでしょう．
そんな僕の代わりになぜかただのテスターであったJAPLJがメインメンバーになっており，バリバリのセンスを発揮していました．
さて，悲痛の催促される度に申し訳ない思いをしながら仕事するする詐欺を行い，それがさらに悲痛の催促に繋がっていた過去を思い出します．
結局自分の担当が全く無かったので，他の方が作ってくれた問題の文章を担当したり，テストケースを作ったりしていました．それで許してくれた慈悲の塊みたいな writer 陣には頭が上がりません．
一番申し訳無さのピークだったのは昨日と今日です．G問題で死ぬほど頑張っているkagamizとJAPLJを目の前にして，Gの解法が全く分からない僕は呆然と立ち竦んでいました．
そんな大戦犯であった僕ですが，せめてもとの思いで，コンテストに画像を提供することにしました！
トップページの写真など，我ながらなかなかイカれしていると思います．
また，賞品も気合を入れて描きたいと思います．
個人的な反省点は多いですが，主催者目線では良いコンテストだったと思っています．Gのデータセットが完成したときには感動しました．
ご参加頂いた皆さん，並びに準備に携わった全ての方々のご支援，ご協力に厚くお礼申し上げます．
japlj
各問題の講評です。
【A: ブロックの移動(Blocks)】
かがみずくんはめちゃくちゃ太っています
↑最高の書き出し
【B: コミュニケーション能力(Communication Ability)】
かがみずくんはポジティブなので，友達はもちろんのこと，友達の友達，友達の友達の友達....と，交友関係をたどってたどり着ける人物は等しく友達だと思い込んでいます．
↑これすき
【C: 山登り(Mountain Climbing)】
奇抜な形状をしており、頻繁に土砂崩れが発生する、誰も管理していない山に登る岩井君は完全に山登りのプロ。
【D: たのしい運動会(School Sports is Fun)】
この問題設定ならカズマ君がインドア派である必要はないと思うんですけど。
【E: はじめての動的計画法(Easy Dynamic Programming)】
問題文中の問題 "Do use Dynamic Programming" の設定おかしくないですか。
そもそも胡瓜の重さの和が W """以下""" でサインが貰えるの奇妙だし、サインがたくさん欲しいからといってサインが貰える胡瓜の集合の個数を求めるのもおかしいよね。重さ W 以下の胡瓜を 1 個ずつレジに持っていけば良いと思う。
【F: タイトル未定(Untitled)】
誰か自然な問題設定ください。
【G: 42】
はた迷惑な王だなカガミズ。
kagamiz
講評と一緒に思い出話をさせてください. コンテストの特設サイトに書いているように, K4PC の起源は以下の tweet でした.
@kyuridenamida 今年もk2pcやりませんか〜
— 榛葉(Shimba) (@kagamiz) 2013, 5月 15ここでいう K2PC というのは, "Kyuride Kagamiz Programming Contest" のことで, 2012 年 8 月に AtCoder で開催したものです. (http://k2pc-easy.contest.atcoder.jp/, http://k2pc-hard.contest.atcoder.jp/)
K2PC の他にも, きゅうりさんに協力してもらって開催したコンテストはいくつかあります. 今回もそれらのコンテストと同じように開催するつもりでした.
ただ, 2013 年はきゅうりさんがとても忙しくしていたため, 2 人で問題準備をするのが大変ということで, ey くんの助けを借りて, JAPLJ 先生に tester をやってもらうことにしました.
最初は割と順調に問題案が出たため, AtCoder には 2013 年 7 月頃にコンテストを開催したいと伝えていました.
ただ, 既出の問題や解けるかわからない問題が含まれていたので結局開催を見合わせることになりました. 結局, 10 問近くボツ問を産んでしまいました. 彼らにも成仏してほしいものです.
ゆっくりと作業の進む作業窓は音ゲーマー交流所になりました. また, コンテスト名を決めるときに, JAPLJ さんが "kagamiz の A, kyuri の U, japlj の J, ey の Y をとってYAJU コンテストだ" とかいいだしたので コンテストの作業窓は"野獣コンテスト作業場" という名前を冠しました. ey くんごめんね.
コンテスト結果について
成績上位者は 1 位から順に Snuke さん, uwi さん, hogloid さんになりました. おめでとうございます.
Snuke さんは本番中に kagamiz という名前で参加していたので, AtCoder の中の人を驚かせていました. 最後の問題をといて 1 位はめちゃめちゃ格好良いですね.
uwi さんは WA なし, hog さんは F の FA を出していました. 解くのもとても早くてすごかったです.
Writer 当てクイズもなかなか盛り上がってよかったです. lyoz さんが 4 つ AC で単独優勝しましたが, 3 問当てる人もそれなりにいてさすがでした. japlj さんがG を担当しているという票がめちゃめちゃ多かったのですが, japlj さんは実は tester として K4PC に参加する予定(当初) なので, 原案は 1 つも出さない予定(当初) だったのです. kyuri さん原案なしなのはトラップですね.
ナイスコード賞は natrium さんに贈呈されます. コードはこちら から確認できます. 美しいですね.
ちなみにこれを twitter で告知したらめちゃめちゃ RT されてしまって携帯の充電が危うくなりました.
商品としてはポッポのアイコンを贈呈しようと思います. よーし描いちゃうぞ.
それぞれの問題について
次に, 2013 年 5 月発足したチームがいつ問題を提案したかというのに注目しながら以下の各問ごとの講評を見てください :).
A ブロックの移動(Blocks) First Acceptance : kmjp (01:12) Total Acceptance : 201 件 Total Trying : 205 人 Total Submission : 279 件 原案 : kagamiz Proposal Date : 2013 年 11 月 28 日
いきなり最初の時点では準備していなかった問題です. 実はこいつは兄弟問題がいたのですが, 兄分が難しすぎたので弟分だけコンテストに顔を見せることになりました.
kmjp さん, 72 秒で正解ってすごいですね... それなりに問題文の箇所が長いので FA は 2 分はかかると思っていました.
B コミュニケーション能力(Communication Ability) First Acceptance : 068_atetubou (05:12) Total Acceptance : 90 件 Total Trying : 171 人 Total Submission : 532 件 原案 : kagamiz Proposal Date : 2013 年 10 月 9 日
またまた最初の方では用意されていなかった問題です. K4PC は最初, 前回の K2PC のように Easy と Hard で分けるつもりでいたので, この問題は微妙な難易度ということでボツになりかけていました. ですが, A のあとにいきなり C が来ると難易度の差が激しくなるということでこの位置にこの問題が持って来られました.
提出件数がすべての問題の中で 1 番高かったです. C++ ユーザの方なら std::set の使い方の良い練習問題になると思います.
C 山登り(Mountain Climbing) First Acceptance : ຣസںƙᘓ(19:38) Total Acceptance : 55 件 Total Trying : 77 人 Total Submission : 190 件 原案 : ey429 Proposal Date : 2013 年 8 月 9 日
彼も実は最初には準備ができていなかった問題です. ey くんはプロなので, 最初から入出力を大体作っていました. この辺から大分提出が減ってきている印象を受けますが, 挑戦してくれた方はほとんど AC しているようなので良かったです.
このページの解説に載っている方法以外にもたくさん解き方があります. いろんな角度からこの問題を解くと良いと思います. とくに, データ構造を使わずに時間反転的な発想で解く解は最近よく見かけます.
D たのしい運動会(School Sports is Fun) First Acceptance : semiexp (27:48) Total Acceptance : 54 件 Total Trying : 61 人 Total Submission : 133 件 原案 : ey429 Proposal Date : 2013 年 6 月 26 日
じつはこいつが問題の中では長老です. 他の問題たちが既出とNP 困難に彷徨う中, これだけ生き残りました. 当初, ey くんは複雑な解き方を想定していましたが, JAPLJ さんによってすごく単純な実装が導かれました. ただ, テストケースの準備をする時期になると ey くんと連絡を取ることが難しくなってしまったので, テストケースに原案者の意思を盛り込めませんでした. C 問題とそこまで正解者数が変わらないのが面白かったです. みなさん, ナイス DP です.
E はじめての動的計画法(Easy Dynamic Programming) First Acceptance : hirosegolf (63:41) Total Acceptance : 23 件 Total Trying : 57 人 Total Submission : 174 件 原案 : kagamiz Proposal Date : 2013 年 10 月 27 日
NP 困難の問題ばかり生やしていたので, ちゃんと考えた問題の解法を伝えないとと思って悩んでいる時期に思いついた問題でした. 最初は解けなかったのでボツフォルダにつっこんでいました. しかし, 考察を進めると解けることに気づいて, 最初に用意していた制約 x ≦ 3 * 10^5 も x ≦ 10^{18} まで拡大することが出来ました. 思いついた問題はすぐに放流せずに残しておきましょう. 解ける日が来るかもしれません.
正直もうちょっと E を 解く人は少なくなると思っていましたが, 多くの人に解いてもらえてとても嬉しいです. 個人的には今回作題した 4 つのなかで一番気に入っている(G は原案の制約がずっとゆるかったので...)んですが, 皆さんには楽しんで頂けたでしょうか？ みなさんがどう解いたか気になるので, ぜひブログなどをかいて僕に教えてください!
F タイトル未定(Untitled) First Acceptance : hogloid (108:35) Total Acceptance : 4 件 Total Trying : 22 人 Total Submission : 100 件 原案 : japlj Proposal Date : 2014 年 9 月 20 日
こいつが一番若い問題です. もともと 6 問しかなくて, なんかバランスが悪いなあとなっているところでできた問題です. この問題の元となる問題を KyuR1 さんが 1 問寄稿してくれたのですが(!), 難度が微妙だったので reject されかけました. そこに japlj さんが improvement を加えて, コンテストに足りないグラフ成分を補ってくれました.
出力が意地悪になっていたのは想定していなかったです. ごめんなさい. 数字だけ見ると総 AC 率が 4 % とかでヤバい. 時間内に解ききってくれた hog さん, uwi さん, anta さん, sugim さんはありがとうございます.
G 42 First Acceptance : ຣസںƙᘓ (230:51) Total Acceptance : 1 件 Total Trying : 25 人 Total Submission : 48 件 原案 : kagamiz Proposal Date : 2014 年 2 月 28 日
この問題が K4PC 開催空洞期に考えられた問題です. そもそも, 2014 年 2 月 28 日に何があったかというと, KIC (KCS Irregular Contest) #001 がありました. このコンテストのラスボスの問題として, ガバガバ制約でこれを出題しようとしたところ, japlj 先生によって problem improvement が行われ, K4PC のラスボスを飾ることになりました.
とはいえ, ガバガバな準備で月日が経っていき, 開催前日に想定解が落ちるという最悪な事態が発覚して焦りました. その中でもきちんとした解法を夜中 3 時まで考えてくれた japlj 先生には頭が上がりません. ぼくは疲れて寝てました. ぼくは違うアプローチで問題を解くため(本質は変わらないんだけど), Java を使う事になりました. わかったのは Java に演算子のオーバーライドがなくてつらいという事実だけでした.
最終防衛問題ではあったものの, 不安を煽るような通知をたくさん書いてしまったため皆さんのコーディングの手を止めてしまったかもしれません. 大変申し訳ありません. その中最後までこの問題に挑んで, AC してくれたkaga...snuke さんには感謝してもしきれません. 解いていただきありがとうございました.
ちなみに, 問題名の 42 はミズゴロウがハイドロポンプを覚えるレベルから来ています. 皆さんもミズゴロウもかわいがって, ハイドロポンプを覚えさせてやってくださいね.
大量に文章をかけたのでぼくの中の K4PC は終わりに近づいています. 一緒に準備をしてくれたスタッフの皆さん, コンテストに参加していただいた皆さん, AtCoder の皆さんには大変お世話になりました. もし次があれば, そのときも面白い企画と一緒にコンテストを開催できればな, と思っています :). 楽しんでいたでけたのであれば何よりです. ではありがとうございました.