season's quarterly

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

大学受験記（共通テスト）

season1618.hatenablog.jp

全体の感想

2020年って結構やばくて、受験を差し引いても高校三年間で一番忙しかった気がする。具体的には、JPhO予選（一次予選落ち）出たり、
SuperCon予選に参加したり、コロナの影響でJOI本選落ちでもAPIOに参加できるようになったり、
PCK予選出て、SuperCon予選通過したけどコロナで本選が立ち消えになった代わりに富岳使えることになったり、JChO予選（一次予選落ち）に出たり、PCK予選通ったので今度は
本選出たりしてました。あと夏休みにSATの研究始めたり、11月から毎週進捗会に参加したりと、本当にわけが分かりません。共通テストの前日も進捗会に参加してたのはイカれてたと思う。本格的に受験勉強を開始したのは9月の下旬くらいだったと思います。
時間とお金の無駄だと思っていたため塾には行きませんでした。金銭に余裕がある方ではないのでね。あと参考書も買うつもりはなかったんですが、親が勝手にZ会の共通テスト攻略演習というのを注文していました（12か月分3万円）。国語と英語と地理はこの問題集を使いました。
競プロは8月に休止したけど、アニメはずっと見てたしTwitterもやめなかった。

9月

ここで9月の進研模試の結果を見てみましょう。

  • 国語98(現80 + 古18)
  • 英語96(R61 + L35)
  • 数学187(IA87 + IIB100)
  • 物理100
  • 化学63
  • 地理52


...
当時の自分の実力をまとめるとこんな感じだと思います。

  • 国語：現代文は運、rand(60, 90)。古文漢文はカス。
  • 英語：Rは最後まで文章が読み終わらない。語彙力が壊滅的。Lはカス。
  • 数学：まあできる。
  • 物理：まあできる。
  • 化学：計算問題はできる。無機有機はカス。
  • 地理：常識がない（「ロシアは社会主義」「スイスは経済的に少し貧困だよね～」）。

というわけでこの時期から頑張って勉強します。

10月

英語Rはそれまで本文を全部読んでから設問を読んでいました。WPMを改善する方向の努力はあんまり効果が無かったので、立ち回りを工夫することにします。設問を読みつつ本文を読んでいくと意外と最後まで読み切れました。それからコミュ英の授業が教科書の読解から私大過去問の演習に変わりました。貰ったテキストに載っていた英単語がレベル別に分かれていたのが単語を覚えるモチベーションになったと思います。これで20点上がります。
英語Lは中学からほとんど勉強したことがありませんでした（CDプレイヤーを持ってなかったのでしょうがない）。ちなみにYouTubeで英語聴いてもまともに上達しませんでした。初心者がやっても効果ないかもしれん。今回はウェブ音声が入手できたのでやっと勉強します。サンプル問題を一回分復習するとなぜか平均に到達しました。これで30点上がります。
単語を覚えるにあたってそもそもどの単語を覚えれば良いか分からなかったりしたので、よく出てくる評論のテーマで調べてました。WikipediaやYouTubeでglobal warming, climate change, air polution, earthquake, volcano, extinction, civilization, hierachy, social class, solar system, self-driving carなどで検索してみると多少対策になります。volcanoの記事を読んでいて、「eruptってなんだっけ...噴火か（n回目）」みたいな。文章の中で同じ単語が何度も出てくるので覚えやすいと思う。
無機化学と有機化学の勉強をします。20点上がります。

11月

11月のマーク模試の結果です。

  • 国語122(現68 + 古54)
  • 英語153(R86 + L67)
  • 数学177(IA92 + IIB85)
  • 物理87
  • 化学81
  • 地理50

古典が上がってるのは、現代文を急いで読んで古典をしっかり読んだら意外と内容が取れたからだと思う。
古典の授業が演習になりました。古文単語を少し覚えます。あと基本的に恋と仏教と自然を愛でるくらいしかしないので単語の意味を決め打ちできるのかなあと思ったりしました。漢文は親しみのない意味でも結構熟語で使われてるんだなって気付いた。例えば、

  • 少：若い→少年
  • 経：営む→経営
  • 済：救う→救済

ちなみに「経」と「済」は経世済民で覚えれば良いと思います。こういうのは漢字一字で検索すると少 | 漢字一字 | 漢字ペディアとかが出てくるので、熟語と合わせて馴染みのない意味が見つかったりする。ばらつきが酷いけど古典で50点ほど取れるようになってたと思う。

12月

地理で山脈の位置とか覚え始める（は？）。あと地誌と各国の経済成長とか。一番意外だったのはイスラエルが先進国だったことです。10点上がります。
本番までの足掻き

1月

国名と位置を覚えます（は？）。地誌は民族・言語・宗教、移民難民、紛争の内容とかを調べた。半導体って精密機械じゃないらしいです（時計とか）。
青パックやりました。

本番

本番前日にごちうさの最終話をもう一周しました。「チノおねえちゃん...」で萌え尽きた。
規則正しい生活習慣を送りましょう。


本番で最も重要なのは、受験票を持っていくこと、電車を乗り間違えないこと、名前と受験番号を書くこと、選択問題を間違えないこと、マークをずらさないことです。これが本質だと言っても過言ではない。
本番に自己最高点、受験生の鑑では。でも満点は取れませんでした。英語Rが何故か8割いってた。嬉しい。現代文で運が良くて94点だったの嬉しい。
ありがとう...

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ランクでした。本選の点数には多少悔いが残りましたが、交流もできたし、ファイルや本も貰えたし、色々な話を聞けたので有意義でした。