season's quarterly

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

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

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分でどれだけ順位が入れ替わったか、地域枠がどのようなものか把握していなかったので、かなりうやむやだった。結局地域枠で本選出場を果たすことができたので、とても嬉しかった。本選で結果を出すのはほぼ不可能でしょうが、悔いのないように頑張りたいです。