season's quarterly

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

PCK2020本選参加記[EngelBæts!]

11/14に開催されたパソコン甲子園2020本選に参加しました。
予選参加記はこちらです。
season1618.hatenablog.jp

開会式

https://www.youtube.com/watch?v=Dglj2Yvm9PE

本選当日


今回はオンライン開催ということで、本選競技中の選手の写真を撮ることになっていたのですが、開始30分程で撮ることになっていました。

問題1 ケーキの価格

差が税率2%分かつpは50の倍数なので50で割る。

問題2 角度の変換

3600で割ったり、3600で割ったものに3600をかけて引いて60で割ったり、60で割った余りを取ったりするとできます。

問題3 ホットケーキ

焼く回数に差ができないように焼くと最小の回数にできる。例えばホットケーキA,B,C,D,Eがあったとする。一回目にA,B,Cを焼いて、二回目はまだ焼いていないD,Eを優先してD,E,Aを焼く、三回目はまだ一回しか焼かれていないB,C,D,Eを優先してB,C,Dを焼くというようにする。よって\lceil 2N/3 \rceilを出力すれば良い。ただしN = 1の時だけ2。これを忘れて1ペナ。

問題4 最小のMAW

辞書順最小であるためにはS中の最も小さい文字だけを使うことが必要。この文字をcとする。Tの長さをS中のcの最大の連続する個数より1多くすれば、その他の条件も満たすことができる。

問題5 スロットマシン

列ごとに0-9の個数を数えて、掛けて足せば良い。
ここまでで34分。去年は競技時間いっぱいかけて5問正解だったのでかなり余裕です。この時点では11位だったらしい。まあ高難度解けないとだめだよね。

問題6 はんぶんこ

尺取りでやるんだろうなあとか思いつつ実装しきれる自信がなかったので飛ばします。

問題7 旅館の客室番号

8進数にして引き算して10進数に直せば良い。100桁なので多倍長整数で足し算（引き算）と掛け算の筆算を実装するのが大変だった。が、どうしても通らないので15:30頃に問題6に戻る。

椅子を温める

実装ができたので提出するが通らない。6も7も解法は分かってるのに通らないのできつかった。何も分からないので問題7で愚直解法と比較してみたが違う答えが出てこない。16:20頃にとりあえず怪しいところを変更して提出するとAC。草。問題8に移る気にはならなかったので、問題6のコードのデバッグに取り掛かる。面積の式が間違ってたので喜々として提出するけどWA。結局原因が掴めないまま競技終了。

結果

まあ去年より解けたから良いんではないでしょうか。
f:id:season1618:20201114201029p:plain
f:id:season1618:20201114201017p:plain


全体の解答状況
f:id:season1618:20201114201021p:plain
やはり問題6の正答率が悪いですね。正答数、正答率共に問題8と逆転してるので、問題8をもっと考えれば良かったかも。

感想

ライブラリは今回も使いませんでした。今回は後輩が3問も通してて凄かった。

PCK2020予選参加記[EngelBæts!]

9/12に開催されたPCK2020予選に参加しました。
本選はこちらです。
season1618.hatenablog.jp
PCK2019の参加記はこちらです。
season1618.hatenablog.jp
season1618.hatenablog.jp

チーム

チーム名は「EngelBæts!」です。世の中には「Angel Beats!」「Angel係数」「Engel係数」という言葉があるのですが、「Engel Beats!」だけなかったのではい。10文字制限なのでスペースを排除してeaを発音記号でごまかしました。相方は競プロ未経験の一年生です。

練習

当日の一週間前から軽く練習を始めました。3年なので部活は休止してましたが、電車が来るまでの40分ほどでAOJ PCKの虚無埋めをしてました。前日は家で2018年の予選の難しい問題を解きました。9完できたので去年より成長したなあという感じです。

予選当日


去年は問題をよく読まなかったりサンプルを確認せずに提出してペナルティを重ねたので、今年はサンプルを全部確認してから提出するようにした。

問題1 緯度経度

La/3600,Lo/3600をそれぞれ出力。LatitudeとLongitudeというらしい。

問題2 商店街へのお出かけ

ヤエちゃんが辿り着けるとき(s \leqq m)1足して、タケコちゃんが辿り着けるとき(w - s \leqq m)2を足せば良い。

問題3 あいさつまわり

左端の座標をx、右端の座標をy、モチヒト君の現在地をmとすれば、min(m - x, y - m) + y - xが答え。

問題4 カラフル円盤通し

配列をreverse。初期値を0としてそれまでの最大値より真に大きければインクリメント。

問題5 写真の回転

写真を回転させる関数を作った。あとは回転数を数えて(1なら+1、-1なら+3)4で割った余りの数だけ適用させる。

この辺はよく覚えてないけど30分で5完したらしい。

問題6 テトラへドロン

color[i][j] = color[i-4][j-2]なので8通りだけ考えれば良いんだけど頭壊れるやつ。結局12パターン全部書き出した。これが一発で通ったのはかなり精神的に良かった。

問題7 加工機

最初素直に配列使ってやったらREになったので制約を見るとW, D \leqq 10^5だった。C \leqq 10^5なので削る区画を管理して、四方を見てどれだけ表面積が増えるか判断。区画が端にあるかどうかで場合分け。思ったより時間かからなかった。

問題8 高速道路網

最初dfsでやってTLEしたのでbfsでやった。トポロジカルソートのライブラリを印刷していなかったので、bfsでやるかーって実装したけど結局トポソになってた(は？)。ある頂点に辿り着いた時点での経路数C_iと経路長L_iをもっておけば、辺の終点でそれぞれ\Sigma C_i, \Sigma C_i + L_iと更新できる。WAになったので最大ケース(と思われる)を確認するとlongにすれば良いことが分かったのでそうする。


最初デバッグ出力を消し忘れていて、もう一度提出したんだけどジャッジが詰まってたので結果が分かったのは競技終了後だった。ここでWAだったらかなり悔しい思いをしていたので良かった。
問題9以降は見てない。

結果

f:id:season1618:20200916150211p:plainf:id:season1618:20200916150236p:plain


全体の解答状況
f:id:season1618:20200916150138p:plain
3と7の正答率が低いなあという印象。
実力枠じゃなかったのでちょっと不安だったけど、無事通っていたので嬉しい。ただで会津旅行行けないのは残念だけど。

感想

去年の教訓を活かすことができたので良かった。実際去年が7完6ペナだったので成績は良くなった。あと結局自分が全部ACしたけど、後輩も自分の後に通してて凄いなあと思った。

APIO2020参加記

https://apio2020.id/
https://contest.apio2020.id/
情報オリンピック日本委員会

経緯

2020年のAPIO(アジア太平洋情報オリンピック)は新型コロナウイルスの影響で現地開催ができなくなったので、JOI本選出場者で参加を希望した者のうち本選の成績上位60名が参加できるということでした。結局参加を希望したのが59名だったので全員参加できることになりました。やったー。


今年の主催はインドネシアです。人口が2.6億人いるのが意外だった。あと日本との時差は2時間。
インドネシア - Wikipedia

プラクティス

提出の仕方を確認した。

A.Accident Average

数列の追加クエリと範囲内の平均の最大値を求めるクエリのやつ。小課題1,2だけで16点。

B.Organizing Party

パーティで親しくなった人が一人でない人を探すインタラクティブ問題。二分探索で満点。

C.The Game of Pajel

パズルの得点を最大化するOutput Only。ケース1,2,3だけクリアして17点。
16 + 100 + 17 = 133点。まあプラクティスなので。

開会式

YouTubeで配信してた。最初はインドネシアの国家が流れてたらしい。最大で170人くらい視聴してた。
www.youtube.com
リンク変えて上げ直したらしくコメント欄もなくなってました。かなしいね。

競技本番

競技時間は選べるのですが、推奨時間(JOIのスタッフが待機している)である8月15日13:00-18:00に出ました。

A.壁の塗装 Painting Walls

Subtask1(12) f(k) <= 1
連番になっている作業員の長さをLとして(L + M - 1) / Mの総和。誤読してて一時間かかってしまった。(14:24)

B.都市の代表者の交換 Swapping Cities

Subtask3(17),Subtask4(20) 答えを決め打ち二分探索で深さ優先探索すればいけると思ったけどWAが取れず。(16:29)
Subtask1(6) 色々勘違いしてて30分かかってしまう。(17:07)
Subtask5(23) LCAでできると思ったけど時間が足りず。

C.楽しいツアー Fun Tour

時間がなくて見れなかった。

振り返り


結局12 + 6 + 0 = 18点。出来そうだと思った小課題をほぼクリアすることができなかった。普段のコンテストより圧倒的に時間が長いのにもたもたしてたら直ぐに終わってしまった。かなり悔しい。単純に5時間かけて18点しか取れないのがかなり辛い。人生で最も競プロができない(理想とかけ離れていた)5時間だった気がする。


目標は達成していた。

閉会式

こっちは230人くらい視聴してた。最後にメダリストが発表されました。
www.youtube.com
日本からは金1人、銀5人の6人が日本代表となりました。自分より年下の人がたくさん活躍してて凄いなあという感じです。そっか～～俺日本代表になり損ねたのか～実質サマーウォーズじゃん笑。
「何の日本代表になれなかったの？」
「えーっと、アジア太平洋情報オリンピックって言って」
「へーなんかやってみてよ」
「そうですね...先輩の誕生日いつですか」
「7月19日。平成4年の。」
「曜日がいつかわからない？wフッフッフw心配することなかれwwこんな時にも役に立つのが競技プログラミング、伝家の宝刀†二分探索†を使わせていただきますぞ！wwwまずは曜日を(0+2e9)/2=1e9にセットして……ウオーーーーーーーーーー！！！！！！！NP困難(悲しい)」
「...」

感想

悲しい。

SuperCon2020予選参加記[eightbit]

SuperConに参加するのは今回が初めてです。

チーム紹介

PCKの相方だったpublic_yusukeさんは卒業してしまったので、弊学パソコン部の競プロerは僕だけになってしまいました（後輩にはAtCoderアカウントは作らせたけどコンテストは出ていない）。そこで問題は一人で考えることにして後輩に参加だけお願いすることにしました。今年から顧問の先生も変わったので、参加の旨を伝えたのも3日前だったのですが、何とか必要なものを提出することができました。
チーム名はeightbitです。半角英数字8文字以内だったので自己言及的に適当にeightbitにしました（半角英数字8文字は全然8bitではないのですが）。

自分の解答

問題の概要を説明すると、二つの文字列が与えられて「代入」と「入れ替え」という操作のみで変換することが可能かどうか、また可能な場合にはその手順を示すというものでした。操作にはコストが決まっており、正解数が同じ場合よりコストの小さい方が高く評価されます。
自分はまず、代入を済ませてから入れ替えをしようと考えました。まずS,Tに含まれる文字の数をカウントします。このときSの文字数の線形結合がTの文字数になるので、26次元ベクトルの間の行列を求めることに対応します。同じ文字で置き換えない限りは文字数を減らした方がコストが低くなるので、そのような変換方法を個数制限なしナップザックで求めます。変換不可能な文字が存在する場合はNOを出力してプログラムを終了します。S,Tは英小文字からなっており、途中の文字には大文字を使っても良いということだったので、すべて大文字を経由して変換しました。
次に入れ替えですが、最初はコストを最小にするような操作を見つけたので、それを書いていました。例えば54213という順列があった場合、1を左端に持ってくることを考えます。1の左隣から見ていって、入れ替えてもコストに無駄がないような数であれば入れ替えます。この場合1,2を入れ替えると2が遠ざかってしまいますが、1,4ならば無駄がないので入れ替えます。そのような数が必ず存在することは鳩ノ巣原理から簡単に示せます。
しかし操作数の上限がn \leqq 500,000と、上記のO(|T|^2)の方法では正解できないことに気付きました。結局、正解することを優先してコストのことは何も考えず、愚直に前から揃えていくという方法をとることにしました。
省いた部分もありますが大体こんな感じの解き方でした。

感想と結果

入れ替えの方法をもっと真面目に考えるべきでした。上手いアルゴリズムが思いつかなくても、いくつかの愚直な方法(前から揃える、後ろから揃えるなど)を比較して小さい方を取るなどの対処もできたはずです。問題に取り掛かるのも遅かったし、学校が始まって時間があまり取れなかったこともありますが、悔いは残ってしまいました。
Twitterを見る限り応募数はそんなに多くはないように見えました。また同校制限もあるので自称進としては相対的に有利だったのですが、かなり失敗したという感覚が強かったので、落ちるだろうなと思っていました。


SupercomputingContest2020/予選結果 - Supercomputing Programing Contest Official Site
予選通過することができたのでかなり驚きました。しかし同時に本戦の中止も発表されたので残念でした。

AtCoderで青色になるまでにやったこと

先日のABC168で念願の青になりました。いえーい。


f:id:season1618:20200518113200p:plain
変色記事を書くのはこれが初めてだし、色々語りたいので語ります。

目次

  • どんな人
  • 競プロを始める前
  • 競プロを始める
  • 緑になるまで
  • 水になるまで
  • 青になるまで
  • 感想

どんな人

県立高校の理数科三年です。パソコン部の部長をしています。実績は、PCKとかJOIの本選にいたりしました。数学と物理とコンピュータが好きな人です。
season1618.hatenablog.jp
season1618.hatenablog.jp

競プロを始める前

中学の頃はずっと数オリの勉強をしていましたね。なので競プロを始めた時点で必要な数学的知識（ユークリッドの互除法、エラトステネスの篩、フェルマーの小定理、逆元など）は大体揃ってました。なお、数オリの勉強はしていても数オリには出ませんでした（最初に出たのは高一）（はあ？）。
プログラミングを初めてやったのは中一の時です。Javaでシミュレーションとかを作ってました。その頃からTwitterは見てたけど競技プログラミングという言葉は聞いたことがなかったです。実は科オリつながりで情報オリンピックの問題を覗いたことはあるのですが、なんじゃこりゃという気持ちになりました。（後にJOIの本選に出場するとは夢にも思わなかった。）

競プロを始める

競プロを始めたのは高一の11月です。その時期に、情報の授業でプログラミング（Excel VBA）をやってました。出された課題は全て一瞬で解いていたので、先生にパソコン部に来ないかと誘われました。放課後にパソコン室に行くと、そこでpublic_yusuke (@public_yusuke) | Twitterさんと会いました。ナチュラルに数学基礎論の本を持っていたり、タイピングが早かったりと結構衝撃的だった。その日に競技プログラミングのことを教えてもらって、いくつか問題を解きました。
f:id:season1618:20200518120507p:plain
（考察だけやって実装はほとんど先輩にやってもらいました。）考察だけとはいえ水diff下位の問題をACしているので、この時点で緑くらいの実力があったのではと思う。

緑になるまで

Javaしか知らなかったのでAPG4bを履修しました。ここでは単純な制御文とか配列、関数を覚えたようです。この時はまだ自分の気持ちをコードに反映できないことが多く、STLとかデータ構造とかは他人の提出を見て学習していました。最近のAPG4bならその辺もカバーしてるんじゃないかな。
f:id:season1618:20200518121836p:plain
初めて出たコンテストはこれですがUnratedでした（問題の不備とかではなく、最初からUnratedだった）。
（当時）レーティングが付くと聞いていたのになぜ？よく見るとrating対象が-になっているな。レーティングが付かない回もあるのか。
（現在）Unrated、めちゃくちゃ珍しいじゃねえか。運が悪すぎる。
48分で2完してました。
f:id:season1618:20200518122149p:plain
次に出たのがRaredでした。なかなか良いパフォを取っています。
自分が緑になった頃はあんまり知識は必要なかったのですが、最近だとABC4完するためには
アルゴリズム

  • 全探索、bit全探索
  • 貪欲
  • 累積和、尺取り法
  • 単純なDP
  • DFS、BFS
  • 累乗の計算(繰り返し二乗法)

数学

あたりを身に付ける必要があると思います。あとC++のデータ構造(map, set, pair, queue, deque)も身に付けると良さそう。知識をあまり必要としない問題でも、数学的な思考を要求されるみたい。
f:id:season1618:20200518134620p:plain
2月に緑になりました。

水になるまで

新たに習得したのは

  • 二分探索
  • ダイクストラ、ワーシャルフロイド、(ベルマンフォード)
  • 高度なDP
  • トポロジカルソート
  • 二部グラフ判定
  • Union-Find

などです。ABCを30分くらいで4完できると大体水パフォが出ます。
f:id:season1618:20200518135851p:plain
始めてから半年ほどで水になりました。旧ABCの内に水になれたので嬉しかったです。一旦緑落ちしたのですが、その後は安定して水パフォが取れるようになりました。この頃に競プロのTwitterアカウントを作りました。

青になるまで

ここから長い停滞が始まります。PCKやJOIの本選には出場しましたが、水の中間である1400に到達したのも12月になってからでした。3月初めには一気に1300にまで落ち込んでしまいます。本格的に精進を始めたのは4月の初め頃です。以下の内容は自分の所感なので、ほどほどに参考にしてください。

モチベーションの保ち方

レーティングにこだわるよりは問題を解きたい欲を重視していた。

取り組む問題

例えば水上位なら水diffが大体解けて、青diffが少し解けるくらいの実力だと思います。なので自分の色と同じか一つ上の問題に取り組むと良さそうです。自分も早解きよりは根本的に実力を上げたかったので、主に水diff、青diffの問題を解きました。たま～に黄diffが解けます（うれしい）。あと虚無埋めはしませんでした。

問題にどれくらい時間をかけるか

少なくとも30分は考えてると思います。長い方だと3時間くらい。コンテスト中はそうもいかないけど、趣味なのでゆっくり考えた方が楽しいです。自分に解けない問題が解けると楽しいので。数時間で解けないときは諦めます。数オリの勉強をしていた頃は、解説のある問題が少なかった（というかどこに載ってるか知らなった）こともあり、1,2週間くらい考えてました。解けない間の二週間はずっと鬱状態なのですが、解けるとめちゃくちゃ嬉しいです。ただ長考する習慣はつくけど、これはさすがに効率が悪くて、もっとやりようがあったなあと反省してます。

解説を読むとき

分からない問題の解法には次のパターンがあると思います。

まず知ってるアルゴリズムだったとき。知ってるのに解けないことありますよね（あります）。そういうときは解法のリストを作成しておくと良いと思います。リストに「二分探索、左右から累積和、単調...」的なことが書いてあって、これ二分探索で解けるじゃん！！、とか。
知らないアルゴリズムならある程度仕方ないので、その機会に勉強しました。
3番目はどうなんだろ...経験以外に思い付かないです。
あと解説ACはしませんでした。AtCoder Problemsに色がつくのが嫌だったため。

知識

水色と必要な知識はあまり変わってないと思います。青diffは数学問が多い印象だったので。Segment Tree, BIT, フローとかは使いませんでした。でも問題を解くごとに知見は得られるので、そういった経験が貯まった感はあります。

精進の様子

f:id:season1618:20200518155659p:plain
f:id:season1618:20200518155740p:plain
f:id:season1618:20200518160209p:plain

というわけで自分の所感でした。

感想

たぶん弊学初の青コーダーなので嬉しい。今年の目標の一つも達成することができました。

JOI2019/2020本選参加記

予選参加記はこちらです。
season1618.hatenablog.jp
2月8,9日に行われた日本情報オリンピック本選に出場しました。

準備

取り敢えずJOI難易度表の難易度6,7をできるだけやりました。8以上は全く手を付けていません。
また今回は名刺を作りました。PCK本選の時に何人かの方から名刺を貰ったので、自分も作ってみたいと思い、Word で作成しました。

一日目

控室

午後2:50くらいに会場であるつくば国際会議場に着きました。


控室には続々と競プロerが集まっていて、KowerKoint2010 (@KowerKoint2010) | Twitterさん、1 (@1st_vil) | Twitterさん、square1001🌸 (@square10011) | Twitterさん、zer0-star (@0x_zer0star) | Twitterさんとエンカしました。受付を忘れていたので受付に行くと、IAのファイルや「みんなのデータ構造」を貰うことができました。

プラクティス

プラクティスでは、本選環境の確認をしつつ問題を解きました。エディタはEclipse,Geany,Vimなどから選ぶことができて、僕はGeanyを選びました。自動インデントもシンタックスハイライトもやってくれるので、この点に関してはPCKのTeraPadよりだいぶ使いやすかったです。それから二回質問をしました。二回目のトラブルでは、helloを出力するはずなのになぜか4が出力されるという問題に直面しました。どうやらコンパイルできてなかったらしい。早々に全完した
えくと (@ecto0310) | Twitterさんも横にいてアドバイスを貰いましたが、ずっと同じ出力で変わらなかったので、チューターの人を呼びました。結局コンパイルではなくビルドをしろということでした。ちなみにビルドが何かを知っていますか？僕は知りません（ア）。3完しかできなかったのでかなりやばいと思いました。


ちなみにプラクティスの問題は毎年同じらしいです。

講演

オープンソースソフトウェアのすすめというタイトルで、濱野賢一朗
Kenichiro HAMANO (@hamaken) | Twitterさんの講演を聞きました。高校の時は数オリに出ていて、19歳で本を書いたらしい。


本人からリプを貰えて嬉しかった。

夕食会

最初に予選全完者の表彰がありました。それが終わると今度は一人ひとり前に立って自己紹介をしました。自分の時が一番盛り上がらなかった気がします（泣）。


競プロerの自己紹介、Twitterネタが飛び出していてとても面白かった。「ACそのまさかだよ」の本人の方がいたり、「シンガポールに行きたいかーー」と叫んでいたりと熱狂していた。

宿

JOIの宿は筑波研修センターというところでした。部屋にトイレや風呂はなく、机とベッドだけが置いてあり、正に独房という感じでした。PCKの時に比べると大分快適さに欠けていました。あとトイレの便器が冷たかった（小便器はなかった）し、トイレには石鹸がなかったので水道で手を洗いました。


一階でWi-Fiが使えたので参加記を途中まで書きました。あとisooooo_19 (@19_iso) | Twitterさんに会いました。久しぶりにJOI難易度表を開いてみたら表示できたので、難易度7を一問解きました。この日の夜はコンテストがなくて残念でした。部屋に戻るとお腹が空いたので、ホテルを出て直ぐのコンビニでおにぎりとたまごサンドとチョコレートを買いました。

二日目

誕生日

コンビニに入ったタイミングで携帯を見ると、丁度0時になりました。実は僕の誕生日でした。


皆さんありがとうございます。おかかのおにぎりを食べてからは速やかに就寝しました。

朝食

朝は目覚ましをかけておいて良かったです。一日目は風呂に入っておらず、大浴場は朝は開いてなかったので、シャワー室を利用しました。その後朝食を食べました。これもPCKより簡素でした。


朝食後にAndroidのアップデートをしたのですが、
というわけでスマホが使えなくなりました。

本選競技

本選は9:00-13:00の4時間かけて行われました。結局小さなマスコットを用意することはありませんでした。

1-長いだけのネクタイ(Just Long Neckties)

ソートして順番に取っていけば良い。貪欲を確信するのに少し時間がかかった。微妙に誤読していて、max(A_i - B_j , 0)の和の最小値だと思っていた。ただ実装の方針はほぼ同じだったので助かった。B_iとペアになりうるのがA_i,A_{i+1}だけなので、pairの配列でそれぞれfirstとsecondに突っ込む。後は配列を二つに分けて（一方が空になることもある）、左側からfirst、右側からsecondを取っていったときの最大値を順番に求めればいい。一瞬セグ木がよぎったが、冷静になると左右から累積maxを取れば良いと分かった。

2-JJOOII2

予めJ,O,Iの累積個数をカウントしておき、それぞれの個数がK個になるような区間を求めていけばO(N)で解ける。それぞれ一時間ずつかけて、この時点で二時間経過していた。

3-スタンプラリー3(Collecting Stamps 3)

最初に考えたのは嘘解法でした。次に考えたのも嘘解法でした（）WAが各課題に散らばっていたので、部分点は取れませんでした。

暫定得点・解説

200点でした。競技中も思っていたのですが、3完が無限人いました。競技中は3で部分点を取っても結果には影響しないだろうと思っていたため、最初から満点解法を目指していたのですが、解説を聞いたら、もっと小課題を気にかければ良かったなあと思いました。あと後半は問題文を読んでいなかったので、少しでも目を通しておけば良かったです。5の解説がよく喋る人でとても面白かった。
ちなみに夜にABCがあったのですが、今回は出ませんでした。

結果と感想

後日ボーダーが発表され、Aランクは301点以上でした。僕は一応Bランクでした。本選の点数には多少悔いが残りましたが、交流もできたし、ファイルや本も貰えたし、色々な話を聞けたので有意義でした。

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は各位頑張ってください。