大手前プロコン 2019 やってみた
大手前プロコン 2019 とは
大阪城の真ん前にある府立大手前高校では 2 年前から SSH (スーパーサイエンスハイスクール)の行事としてプログラミング学習会を開催してきました。今年度は 8 月 1 日、2 日に初心者・未経験者対象の講習を実施し、3 日には大手前プロコン 2019 オンサイトを実施しました。
今年の大手前プロコンは初心者も楽しめるようたくさん部分点を用意したり、かつ春合宿erにも苦戦してもらえるよう難しい問題を用意したり、writer の皆様とたくさん打ち合わせをして開催したものでした。各問題にもたくさんの思い入れがあるので、ここに書き記していこうと思います。
問題 A 寝坊だ！ピ太郎！ (writer : kotamanegi さん)
ほぼ原案通りの出題でした。せっかく大手前プロコンに来てくれた人に 1 完はして帰ってほしいということでした。
原案では、Yes / No を出力する問題だったんですが、どうせなら文字列を扱えなくても解けるようにしてしまおうと思って、0 / 1 を出力する問題に変更しました。我ながら優しい。
問題 B 駒 (writer : yamunaku さん)
原案は無限に伸びた数直線上で行ってたんですが、左端の駒より左に集めるのは意味がない、みたいな考察が少し大変かと思って、マス上での問題への変更をお願いしました。
小課題 1 の提案はきたむーで、ループも回さず解けるので A しか解けなかった人には是非拾ってほしい部分点でした。
小課題 2, 3 の提案は yamunaku さんで、「集める」を意識させる小課題をご用意くださいました。
満点解法はやや難しかったようです。
問題 C カード並べ 2 (writer : olphe さん)
僕がいじったのはもともと数列だけだったのを、カードの設定を付け加えたぐらいです。問題特有の性質を考える必要があって、ほどほどに難しいですが、実装は楽です。
小課題の中では 2 が一番解きやすいと思うので、是非取ってほしかったです。
上級者は数列の数え方に被りがあってもいい場合も考えてみて下さい。問題文中の例だと、{1 2 1 2 1 2 1 2} に {1 2 1 2} が 3 回出てきていると考えるわけですね。
問題 D FizzBuzz (writer : Hoget さん)
この問題は今回のセットの中で最も好きです。本当に予選 4 で出てきそうな問題。数学的な知識を背景にしつつ、DP という情報科学的なテクニックも使う。大好きです。
小課題を考えるのがかなり大変だったんですが、N=M が出てきた後に、全部同じ文字列にすることを確か僕が提案しました。これら小課題によって、3、5 の倍数の判定法をきちんと意識させ、満点解法に近づいてもらいたかったです。
なお、mod は 3 で十分です！！！！！15 じゃないよ！！！！！低速な言語でも通るように制限を緩くしたので mod 15 にしても C++ とかなら通りますが、mod 3 で解く人をもう少したくさん見たかったです・・・。
問題 E 最悪の教頭 (writer : WA_TLE さん)
元ネタは最悪の記者 3 (JOI 2017/2018 春合宿 Day 2) です。問題文をちょっとだけいじるはずが、いろいろ辻褄の合わない点が出てきて、細々改善を重ねてきていたんですが、コンテスト中にも新たな不備が発覚してしまいました。申し訳ないです。
この問題はひらめき一発、実装はわずか数行、といった感じでした。僕はひらめきませんでした。丁寧に考察してあげると、わかると思います。たぶん。
小課題はやるだけなので、是非取って欲しかったですね。
この問題難易度について、本選1 ～ 2 問目相当と記載していたんですが、もう少し難しかったかもしれないですね。
問題 F 天秤とコイン (writer : drafear さん)
典型テクの合わせ技みたいな問題です。これはかなり論理的に解けると思っていて、DP を知っているのに解けなかった人は、是非僕が書いた公式解説を読んで欲しいです。
小課題はすべて drafear さんの提案なんですが、僕は部分点解法が全くわかりませんでした。満点解法はわかるのに。そういうこともあるので、是非各小課題についても改めて考えてみて欲しいです。
なお、僕は提案から 3 週間ぐらいずっと、左側の更に積まれているコインの途中を抜き取って右に移してもいいと誤読していたので、ずっと頭を抱えていました。
問題 G 空をかけるピ太郎 (writer : gotoloop さん)
ストーリー部分は僕が後から勝手につけました。「空」を「そら」と読むのか「くう」と読むのか、自分でもよくわからないので、英語名で読んでやってください。ストーリーの元ネタは時をかけるビ太郎 (JOI 2018/2019 春合宿 Day 3) です。
この問題の小課題 1 はスーパー簡単、何なら 1 問目より簡単なので、是非取って欲しかったです。(ここまでわざわざ見なかった人に加え、問題文の読解ができなかった人もいたようです)
小課題 2、3 は確か僕が提案して、(遅延)セグ木で殴るつもりだったんですが、imos をしたり、範囲を merge したり、いろいろな解き方が見られたようです。
満点解法は原案をもらって 5 分ぐらいで思いついたので、かなり簡単だと思っていたんですが、実装面で詰まっている人が多かったようです。僕はこの問題の実装は全然重くなと思っているんですが、個人差ですね。多分 JOI で春合宿の対策をした人は、全然重くないと感じると思います。
問題 H 美味しい飴 (writer : Pulmn さん)
小課題 1 : やるだけ(といっても DP)
小課題 2 : 差分を使って DP を頑張る(鍛えればできるようになるらしい)
小課題 3 : 天才解法が降ってくれば簡単
みたいな感じです。かなり難しくなってきたという感じです。難しいのでコメントできません。
問題 I ピーターランドの道路整備 (writer : hos さん)
問題名が長いです。ごめんなさい。
めっちゃ難しいです。小課題 1、2 は簡単なので取りましょう。満点解法は丁寧に考察すればいい感じに式変形出来て、実装を頑張ります。
コンテスト時間の不足は明らかなんですが、JOI 春とは違ってライブラリの使用が OK なので、何とかなるかなと思ってました。あと数分足りなかった方が 2 人いらっしゃった感じです。
問題の難易度について
大手前プロコン公式として見解ではなく、きたむー個人の意見なのでご注意ください。
JOI 非公式難易度だと、1-3-4-6-7-7-9-11-12。
具体的な基準では、
- JOI 1 次予選突破 : 120 点以上
- JOI 2 次予選突破 : 340 点以上
- JOI 本選突破 : 560 点以上
- JOI 春合宿突破(IOIer になる) : 740 点以上
ぐらいだと思います。参考にしてください。
JOI に出る人へ
部分点もっと取ってよ！！！
JOI はどれだけ部分点を取れるかを競っているコンテストです。わずか数点の差で泣くこともあるのです。
JOI 出場予定で部分点を全然取りにいかなかった人は先が暗いです。部分点を取る練習をしてください。特に春合宿で一切部分点を取らないと 0 点になりえます。1 完出来てない人はそこそこいます。
某 IOIer は難問を解くときには誤読防止のためにまず最小部分点を数分で通すと言っていました。そういう使い方もあります。部分点とうまく付き合える人が JOI では明らかに有利なのです。
今回、writer の皆さんには、「JOI の模擬試験を作りたい」みたいなことを言ってきました。大手前プロコンはそういうコンテストです。writer の半分以上が JOI で活躍していた人です。もはや JOI なんです。しっかり解きなおしをして、本番に備えて欲しいと思います。
