season's quarterly

数学/物理/プログラミング

2020年JMO予選参加記

1月13日(日)に開催された日本数学オリンピック予選に参加しました。

精進

JOI予選が終わってからは競プロの精進をいったん休止して（コンテストには出てた）、学校の図書館で数学オリンピック事典や過去問を借りて、冬休み中に勉強してました。数学オリンピック事典には、JMO以外にもAIMEやUSAMOなどの海外の問題もあり、分野ごとに問題を解くときのコツなどが紹介されていたのでとても参考になりました。他にもだま (@dama_math) | TwitterさんのJMO本選模試をやったりしました。

当日

競技前

電車に乗ったときから腹痛でした（こういうイベントのときに腹痛になるのやめたい）。予選会場の最寄り駅のトイレで下して、ことなきを得ました。

予選

1

百の位をa,一の位をbと置くと、2a+b \equiv 0 \pmod{7}なので全て求めると14個。

2

正六角形の中心をOと置くと、\triangle{HOC}は\triangle{GBC}を右に60°回転させたものなので、B,O,H,Eが水平に位置していることが分かります。つまり\triangle{EFH}は直角三角形なので、EH=\frac{1}{2},FE=\frac{\sqrt{3}}{2}より面積は\frac{\sqrt{3}}{8}。

3

6は1,5としか隣合わないので隅に置く。1,5の置き方が2通りあり、2,4の置き方が2通りあるので、4\times 2\times 2 = 16通り。

4
  • n^2が二桁のとき、n^2 < 10^2,n^3 < 10^3より不適。
  • n^2が四桁のとき。32^2 \leqq n^2,32^3 \leqq n^3より不適。

従ってn^2が三桁、n^3が五桁となる。10^2 \leqq n^2 < 10^3, 10^4 \leqq n^3 < 10^5より22 \leqq n \leqq 31。本番はごり押しでn = 24となりました。

5

まず絶対値が最小のものを考えると、x_iがそれぞれ0,1,2,1,2,2,3,3,2,3となる。これは符号が負になってしまうので、x_iのうちの一つをx_i^2 - iを符号が逆で、二番目に小さくなるように選ぶ。倍率を考えると、x_9を2から3に変えると、\frac{7}{5}で二番目に小さくなるので、答えは84。

6

大きい正方形の左上の頂点から点線に向かって垂線を引くと直角三角形ができます。この直角三角形に三平方の定理を適用して、
\sqrt{3^2 - \left(\frac{1}{\sqrt{2}}\right)^2} = \sqrt{\frac{17}{2}}
となる。直角三角形に含まれる鋭角三角形の辺の長さはそれぞれ1 , \frac{\sqrt{17}-1}{\sqrt{2}} , 3となる。この三角形は三つの正方形の斜辺がなす三角形と相似なので、二番目に大きい正方形の一辺の長さは、\frac{\sqrt{17} - 1}{\sqrt{2}}となる。余弦定理を適用すると鋭角の\cosは、
\frac{1^2 + \left( \frac{\sqrt{17} - 1}{\sqrt{2}} \right)^2 - 3^2}{2 \cdot 1 \cdot \frac{\sqrt{17} - 1}{\sqrt{2}} } = \frac{1 - \sqrt{17}}{\sqrt{2}(\sqrt{17} - 1)} = - \frac{1}{\sqrt{2}}
なので鋭角は135°である。つまり斜線の三角形の二つの正方形に挟まれる角は135 - 45 - 45 = 45なので面積は、
\frac{1}{2} \times 1 \times \frac{\sqrt{17} - 1}{\sqrt{2}} \times \frac{1}{\sqrt{2}} = \frac{\sqrt{17} - 1}{4}

7

DPをします。a,bの差が2または3 \Leftrightarrow b - a \equiv 2,3 \pmod{5}と考えると分かりやすいです。一般に2 \times nのマス目を考えて、列を増やしていくと右端の2マスに対してそれぞれ3通りの数字の列を付け加えることができます。n = 1のとき10通りなので、10 \times 3^{1009}となる。

8

初期値を1,2,3,4,5としてしまったため、2^{34}と書いてしまった。正答は9 \times 2^{19}です。
この時点で時計を見るとまだ1時間ほどでした。それからしばらく9番を考えていました。

12

後半の問題は全く分からなかったので、唯一頑張れば当たりうる12番の構築をやっていました。とりあえず19が構成できました。

その後のムーブ

解けそうにない9-11を適当に埋めたあと、15:00-15:30で1-8の見直しをしました。最初1番を15、5番を120と書いていたので結構危なかったです。時間に余裕のあるうちに見直しができて良かったです。最後の30分はもう一度12番を考えて、22を構成しました。

終了後

直ぐにTwitter上で解答があがりました。8を間違えてしまっていたようなので悔しかったですが、とりあえず7点とれたらしいので良かったです。12番は23が構築できたらしいのでかなり惜しかった。今回は去年に比べて易化していて、ボーダーは8とか9とか言われていて、最高点は11点のようです。例年、Aランクの最高 - 最低 = 3 or 4なので本戦は微妙でした。

感想と結果

競技前はかなり緊張していたのですが、本番は去年よりも落ち着いて臨めたので良かったです。幾何は座標を使わずに解けて嬉しかった。あと4番の24^2 = 576, 24^3 = 13824はかなり気に入りました。
予選突破者は正式発表されてなかったのですが、URLをエスパーしてTwitterで流れてきました。（その後正式に発表されたらしい）JMOのボーダーは8点で、最高点は11点でした。去年よりも成長したと思っていたし、成功したと思っていたので、とても悔しかったです。しかも最初7点だと思ったのがJJMOのボーダーだったという後味の悪いムーブをしました。数学オリンピックは結局二回しか出ませんでしたが、去年本戦に出れただけでも良かったと思うことにします。本戦erは各位頑張ってください。

JOI2019/2020予選参加記

本選はこちらです。
season1618.hatenablog.jp

一次予選

一次予選はせっかくなので3回とも出ました。

第一回

一回目は弊校のパソコン部員（一年生3人、二年生1人）で集まってやりました。

  • A-3つの整数...数字が二種類しかないので全部足すとわかりやすいです。
  • B-母音を数える...mapを使って数えます。
  • C-マージ...アルゴリズムがマージソートそのものなので、sort(v.begin(),v.end())をやるだけでよいです。

全完するのに7分弱かかりました。残りの時間は図書館で借りた「数学ガール ポアンカレ予想」を読んでいました。結果は3人が全完、1人が200点だったので、全員一発で一次予選を突破できました。

第二回

二回目は自宅のパソコンから出ました。

  • A-試験...高い方二つとありますが、全部足して一番小さいものを引くと簡単です。
  • B-文字列の反転...丁寧にやります。
  • C-最頻値...カウントして最大値を出力します。

第三回

今回は修学旅行中でした。少し前にノートパソコンを買ってもらったので、一次予選すべてに出ることができました。

  • A-Xに最も近い値...区間[L,R]と原点の位置関係で場合分けします。
  • B-キャピタリゼーション...順番に見ていって、joiが来たらJOIに変えます。
  • C-最長増加連続部分列...これも前から見ていって丁寧にやります。

二次予選

今年もJOI期間中にテストがあった（？）ので、少し辛かったです。

精進

コンテストはAtCoderだけでなくyukicoderにも積極的に出るようにしました。二次予選の2週間にJOI難易度表を初めて見たので、本格的に埋め始めました。


とりあえず難易度1から1問ずつ解いていって、自分に適当なのは難易度6くらいかなと思い、難易度6を埋め始めます。また、JOI予選ボーダーは難易度7くらいとも聞いたので難易度7も少し埋めました。前日にライブラリを整備しました。セグメント木が出るかも？ということだったので、一応実装しておきました。前日や当日はあまり問題を解くモチベーションが湧かず、解いた問題の解説を読むなどしていました。二次予選は再び学校に集まってやりました。

A:ポスター

4通り全部比較します。移動の回数を足すのを忘れないように注意。

B:いちご

貪欲でできるらしいですが、確信できなかったのでシミュレーションでやりました。ちょっと焦る。

C:桁和

典型的なDPの問題。

  • dp[i]:操作を何回か繰り返してiになるような整数の個数
  • d[i]:iの桁和

とすると、最初dp[i]=1として、j < min(55,i), d[i-j] = jなる整数jに対してdp[i] += dp[i - j]とすればよいです。

D:テンキー

まず前処理として各キー間のコストを求めておきます。座標にしてマンハッタン距離にすれば簡単です。(Mで割ったあまり,最後の桁)のpairを作ります。答えは(0,0)から(R,i)(i=0~9)まで移動するときのコストの総和の最小値なので、各pairに辺を張って最短経路問題を解けばいいとわかります。メモリが危なかったのですが、ダイクストラ法で通ります。
ここまで1時間30分ほどかかりました。

E:じゃんけん式

ワイルドカードのある数式が与えられるので、答えがAとなる数式の総数を求めよという問題です。僕と同じく解法以前に実装が分からなかったという人が多かったようです。単語だけは知っていたので、ポーランド記法とかで調べたのですが、入力として与えられるのは中置記法と呼ばれるもので、あまり検索に引っかかりませんでした（下手なだけ）。Dまでが比較的簡単だと思っていて、ボーダー付近にいるのではと感じていたので部分点だけでも取りたかったのですが、残り1時間30分なにもできませんでした。

終了後

TLを見ただけでも全完者がちらほらいて、400点もそれなりにという印象でした。当初はボーダー全完ありうるのではという言説も見かけましたが、最終的には330~350点に落ち着いたようです。

結果

400点ペナルティ0。一年生は1人が200点、2人が0点という結果となりました。
400点ならさすがに通るだろうと思っていましたがやはり不安でした。結果発表はその週の木曜日にあり、Aランクボーダーは350点でした。パソコン甲子園の本選に行ってからオンサイトにとてもあこがれていたので嬉しいです。本選は2月8日~9日にあるようですが、9日は僕の誕生日です（まあどうでもいい）。悔いのないように頑張ります。

PCK2019本選参加記[AはDPのA]

予選はこちらです。
season1618.hatenablog.jp

1日目

移動

4時間目まで学校の授業を受けて、昼食を食べてから出発しました。郡山行きの新幹線がlog K (@Selfgrudge) / Twitterさんと
https://twitter.com/nn1k_?s=17さんのチームと同じでした。


ホテルについてすぐ顧問の先生にステーキ宮に連れていってもらいました。ただで食うステーキは最高です。

yukicoderオンサイト

ロビーでオンサイトをやるという話だったので、行ってみることにしました。僕はノートパソコンを持っていないのでスマホコーデディングです。そこで
tatyam (@tatyam_prime) / Twitterさんの名刺を貰いました。A,Bを通したあとCが解けそうにないので、E869120さんが作ったゲームをやりました。僕はそこそこの点数だったのですが、先輩がもう少しで殿堂入りするところだったらしいです。その後
matumoto1234 (@toyama_tty) / Twitterさんと
https://twitter.com/yta1719さんとエンカしました。

2日目

競プロ歴1年

実は、僕は丁度一年前のこの日に、顧問の先生に誘われてパソコン同好会に入り、競プロを始めたという経緯があります。競プロを始めたその日にパソコン甲子園の本選に出るというのはとても感慨深いです。

午前中

朝食はホテルで出ました。卵がおいてあったので迷わず卵かけご飯にしました。


腹が減っていたのでいつもより多めに食べました。ところが、これが原因だったのか、あるいは昨日のステーキが重かったのか、腹痛を感じ始めます。これは自分だけ腹痛甲子園かな~と思っていると、幸い開会式の前に下したので、集中して競技に取り組むことができました。

競技

競技環境

youtubeの動画を見ていたので、L字型の机だと思っていたのですが、今年はそうではありませんでした。長方形の机の左右にディスプレイがありました。左側には、コーディングのためのエディタとコンパイラ、そして提出用画面とキーボードが用意されていて、右側には、本選ともう一つの本選の順位表が表示されていました。キーボードは普段使っているものよりもキーが高く、個人的には扱いにくかったです。エディタのTeraPadもハイライトが分かりにくかったり、自動インデントがないなどかなり不便でした。また、いちいちコマンドを打ってコンパイルするという方式にも慣れませんでした。
分担

  • 先輩...2,3
  • 自分...1,4,5
問題1 目盛りのないストップウォッチ

t/a*rを出力すれば良いです。

問題3 海苔

僕が問題3、先輩が問題5を考えていたのですが、早速何十行にも及ぶ理解不能なエラーが出てしまい、先輩に相談します。自分は後から知ったのですが、どうやら"y1"が標準ライブラリ中の変数と被ってしまっていたそうです。一人だと詰んでたところでした汗。

問題4 へびの脱皮

そのすきに問題4を考えました。脱皮するごとにooの数が二倍に増えるので、計算をすると解けました。ここまでは0ペナでした。順位も上の方だったので今回は上手くいくのではと思いました。

再び問題3

サンプルを通して提出すると、初めてのペナが出ました。この時点ではまだ焦りはなかったのですが、コーナーケースをいくつ見つけても通らないので後回しにすべきかと考えます。同じ頃先輩も問題5でエラーを量産し始めます。

問題5 デジットK

どうしてもバグが取れないので、思いきって交換することにしました。問題5は、ぱっと見で思った解法が先輩のそれと同じであることを確認したので、より確実そうな方法をとることにしました。整数の上からs桁目を選ぶ範囲を指定して、前から見ていったときに初めて最大の数値が来たときに選択します。これはある範囲にある数字の個数を累積和で求め、最大の数値を決定するという前処理をすることでできます。
先輩が問題3を17:23に通し、自分も問題5を17:32に通すことができました。これは3完で終わってしまうかなーと覚悟していたので良かったです。この時、順位表が誤って更新されていたため、全体で17位だと分かりました。でも風船はもらえませんでした。かなしいね。翌日、パソコン甲子園ツイッター班の投稿を見ると、自分たちの提出の後に二回逆転されていたので、最終順位は19位だと思われます。

感想
  • エディタやコンパイルなど、色々と慣れていなかった。
  • 問題3は僕の苦手な形式の問題で、長方形の重なり方を全て把握するのに時間がかかった。
  • 途中までは順調だったが、二人とも沼にはまってしまい、後半の問題を考察する余裕がなかった。

交流会

チーム「らてｄ」と同じテーブルでした。最初顧問の方と話していたのですが、二人を紹介してくれたのでエンカできました。


大エンカ大会を経験。
交流会の夕食も結構豪華で、寿司やケーキもありました。
交流会の後もたくさんの方とエンカしました。

NIKKEIコン

今回は部屋でやりました。先輩も久しぶりにコンテストに出ました。配点が1-3-6だったので、スマホコーディングで早解きできない自分は冷えを確信していたのですが、余興ということで出ました。やはりレーティングは下がったのですが、楽しかったです。

3日目

モバイル部門&いちまいの絵CG部門

午前中はパソコン甲子園の他競技の観戦をしました。僕はモバイル部門にはあまり興味がなかったので、一通り見た後はエモい絵を探して写真を撮ったりしていました。

本選問題解説

問題文に目を通していて解けなかったものについては非常に参考になりました。また解いた問題に関しても、別の解き方があったりと、様々な視点を知ることができました。

感想

地域枠とはいえ、パソコン甲子園本選に出場することができて嬉しく思います。この三日間を通してtwitterでしか知らなかった人と知り合ったり、本選出場者しかできないような貴重な経験をすることができました。とても楽しい三日間だったので、またオンサイトに出たいという気持ちも強くなりました。JOIも近いので精進を怠らず、次の目標(青になりたい)を目指していきたいと思います。

PCK2019予選参加記[AはDPのA]

本選はこちらです。
season1618.hatenablog.jp

チーム紹介と当日まで

弊校のパソコン部(今年の5月に部に昇格したばかり)は、4チームが参加登録をしました。
我々はチーム名AはDPのA(先輩public_yusuke (@public_yusuke) / Twitter,僕season (@season1618) / Twitter)で出場しました。他の3チームは全員1年生です。ちなみに先輩は同じ日に学校で行われていた模試をサボって参加しました。競プロerの鑑ですね(模試は後日受けた模様)。
予選の1週間前に台風15号が来て、停電した上インターネットも使えなくなり、精進どころではなくなってしまいました。電車も運休して、車のガソリンも補充できるかわかりらなかったのですが、幸い金曜日の朝に電車が動き、夜に停電と電波障害が解消しました。ライブラリをslackに貼ることもできました。とはいえ1週間も競プロに触れていない状態で、先輩も受験勉強のため競プロを休止しており、結構厳しい状況だったのではと思います。

予選当日

準備と分担

  • ライブラリをslackに貼り、印刷する。
  • 学校の図書館からC++リファレンスを借りる。
  • 先輩...1,2,4,6
  • 自分...3,5,8

問題の考察

問題1 柴犬の数

先輩が問題を読んで僕が実装しました。R+B+W+Gを出力すれば良い。

問題2 アスキー文字

最初僕が実装したのですが、早速エラーを吐きました。先輩に投げます。開始3分にして精神を病むゲームと化した。

問題3 ２の累乗

律儀にwhileでやると良い。

問題5 ねこのあな

論理的に甘かったためまたエラーを吐きました。自分のプログラミング苦手説が浮上。

問題7 アカベコ２０

ぱっと見で自分の苦手な問題だなあと思いつつしばらく考察したが、解けそうにないので問題8に移ります。

問題8 矢印

これも随分と右往左往したのですが、結局は駒が両端に寄せられた状態で落ち着きます。最初駒を全て右端に寄せておきます。左から順に見ていって、左矢印より右矢印の方が多くなったところで左端に寄せます。カウントをリセットして同じことを繰り返します。

問題10 トーナメントの記録

この時点で順位表を見ると、24位と思ったより良い成績でした。他のチームの状況を見る限り、解くとしたら問題9より問題10であると判断します。実際しばらく考えて木DPをすればいいとわかりました。グラフ理論楽しい。残り時間30分。実装を始めますが、ライブラリ含めて実装が下手くそだったため、間に合わず終了。後日AOJで無事ACしました。

結果と感想

  • 結果は1~6,8の44点(7完6ペナ)、順位表凍結時点で24位でした。

  • 時間制限よりペナルティの方を優先すべきと認識していながら、問題をよく読まなかったりテストしなかったりして、余計なエラーを吐いてしまった。
  • 練習はしなかったが、二人でいい具合に問題を分担・相談できたと思う。

凍結時点で24位だったので可能性はあると思っていたが、残り30分でどれだけ順位が入れ替わったか、地域枠がどのようなものか把握していなかったので、かなりうやむやだった。結局地域枠で本選出場を果たすことができたので、とても嬉しかった。本選で結果を出すのはほぼ不可能でしょうが、悔いのないように頑張りたいです。