JOI予選までにこの弱い頭はなんとかなったのでしょうか
※この記事は ICT Advent Calendar 2016 の12日目の記事です。
12/11、JOI予選がありました。ぼくが競プロを知ってからのことを振り返ります。
適当に勢いだけで書いたのでめちゃくちゃな文になっていると思いますが許してね❤️
競プロの存在を知ったのは去年の後期、M教授がもつプログラミングIの講義でkurokojiが隣の席になったときでした
ぼくはその頃から講義レベルなら普通に演習問題を解くことができていたので、その時間の演習問題を解終わると時間を持て余していたのですが、隣にいたkurokojiが「AOJとかやらないの？」と聞いてきたので初めてAOJと競プロの存在を知りました。
ただまあ、その時の僕はICTにはいってすらなく、興味だけはあったもののやる気がなかったのでそのまま時間が流れました。
2015年12月
ちょうど去年の今頃ですが、同級生らがJOIに参加するといっていたことでJOI自体の存在は知っていましたがやはりその時も参加はおろか、競プロすら始めていませんでした。
2016年1月末
なにを思ったか、C++をほんの少しかじります。その練習程度にHello Worldを書いたりなどしてAOJを初めて使いました。
2016年3月末 (?)
結局1ヶ月くらい競プロをせずに時間が流れます。
それで、いつの間にかICTの春合宿に参加することになっていて春合宿に参加しました。
確かこの時期にslackに入ったと思います。
1day1problemが始まったのもこの時期だったと思います。ぼくが競プロを本格的に初めたきっかけでもあるこの1day1proについては、運営をしてくださっていたコーヤ先輩がICT Advent Calendar 2016 の2日目の記事に書いていますのでぜひご覧ください。
Kick-ass 1day-1pro Carnival - さいどうにっき
春合宿中、アイデア出しがあってつらいつらい言ってました。午後から夜中にかけてはそれに時間が吸われていましたが午前は申し訳程度に競プロをしていたように思います。
あとお金があったので蟻本を買いました(ちなみに、現在財布に9円しか入っていません)
2016年4~5月
まばらではありますがちょこちょこ問題を解いていました
確かこの時期にはABCのC問題が解けことがある、程度の感じだったと思います
それとkurokojiとチームを組んでPCKに出ることになりました
kurokojiが自分より無限に強く、本当に自分でいいのかみたいな気持ちながらも誘いを受けたのを覚えています
2016年 6月
何もしませんでした(←!?)
今冷静に振り返ってみてもここは焦って精進すべきところだと思います。
多分テストがこの時期にあったんじゃないかと踏んでいます。
2016年 7月中頃まで
この時期もほとんど何もしていなかったに等しいですが、少しずつ蟻本をよんでいたりした記憶があります
2016年 7月下旬 ~ 8月上旬
夏休みです
各位が高専プロコンで死にそうになっていたのを覚えています
ぼくはぼちぼち蟻本を読んでいました
家がドがつく田舎にあるので、固定回線はおろか、モバイルですら怪しいみたいなところに帰省していたためですかね
2016年 8月下旬
PCKが近づいてきて、さすがに焦りました
合宿前日くらいにPCKの予選があり、超焦って蟻本を読んでいました。理解力を総動員して蟻本を読んだおかげでこの時にぼくの競プロ力はぐっと伸びたと思います
フローは流した(フローなので)
2016年 PCK予選当日(9月10日)
普通の結果を残しました。ダメダメでもなく、できたわけでもなく、ただ自分の実力が出て相応の結果が出た、といった感じでしょうか。
ただ、それが無性に悔しくて悔しくて、ここから目標を完全にJOIに向けます。
おりさの先輩と初めて話したのもこの日です。*1初対面で煽られました。Advent Calenderは書かないんでしょうか。
それと、久留米のらてまるたさんがPCK予選問を1WAも出さずに全完して1位で通過していたのを見て、「かっけぇ......」となったことを覚えています。そんなぼくの目標の一人であるらてまるたさんはICT Advent Calendar 2016 の22日目の担当になっています。*2
素敵な記事を期待しています。
2016年 9月 夏合宿
ぼくだけ高専プロコンに出ないせいで暇(相対評価です)だったので1年生の教育係?として1day1pro改め1day3proをしていました。
まあまあ辛かったけど楽しかったのでまあよし。
自分の精進も忘れてはいなかったので。(記憶が確かなら1日で50ACとかしていた気がする)
zig-zag numberをおりさの先輩*3に手伝ってもらいながら通したのもこの時でした
2016年 10月
学校が始まりだらだらしていた。
JOIの問題を解いている形跡があるので一応精進はしているみたいだけど、やる気が起きなくてやるだけをやっていた気がする。
2016年 11月
無限に焦っていた。JOIまであと1ヶ月しかないって時期なのに何も見ずに*4解けるDPが通学経路とか簡単な桁DPだけだったので絶望的だった。
テストがあると気がついたが迷わず捨てて、ただひたすら無限に精進していた。
朝起きて解いてない問題を数問見て覚えて午前の講義中ずっと考察、昼休みにコーディングして午後もまた考察。みたいな生活を11月半ばから続けていた。
11月も半ばにさしかかってきたところで簡単なDPの解法がすぐにわかるようになっている気がしていた。
11/20、中学2年生のsquareプロとE869120プロが作問しているs8pcがAtCoder上で開催された。
軽い気持ちで参加したぼくは1問しか解けないままコンテストが終了した。
本気でやったのに1完である。
この時ほど焦りを感じたことはなくて、今でも思い出すと鳥肌が立つし吐き気までしてくる。大嘘だけど。
ぼくはTwitterしまくり芸人なので多くの時間をTwitterに費やしていたがこのままえではまずいと思ってアカウントを一時的に消した。消えるのが怖かったので1週間後にひそかに復活させておいた。
2016年 12月
完全に競プロのこと以外考えていなかった。ボロボロの答案が返ってきてちょっと落ち込んだけど、そんな場合じゃなかった。
ひたすらにJOI非公式難易度表を埋めながら吸収できる分だけ吸収してと、無限に精進をしていた。
2016年 12月10日 (JOI前日)
偉大な先輩であるところのkagamiz先輩がJOI予選の模擬を開催していた。
結果は1 ~ 3問目AC、5問目ACの4完で、いい感じに実力がついていることはわかった。提出練習は何度もやっていたけど、緊張感を持ってやったのは初めてだったのでいい練習になった。本当にありがとうございました。
この日の夜、AtCoder Regular Contestが開催されていて、いつもなら普通に参加して普通に終わるところだけど、完全に自信を喪失したs8pcの件があったので問題を見るだけにとどめておいた。
F問題を一番最初に見たのだが、不思議とすぐDPだとわかったし、その解き方も少し考えればすぐにわかった。今思えばDPの特訓の成果だったかなと思う。
2016年 12月12日
JOI当日。みんな緊張しているみたいで、kurokojiなども険しい顔をして一人で昼食を食べていた。(一緒に食べたが)
まあ、不思議と緊張はなかった。緊張がなさすぎて午前中まるまる寝ていた。後輩が質問したいけどいいですかと言っていたのに2時間後くらいにレスポンスを返したことはこの場を借りて謝罪したい、大変気持ちよく寝させていただきました。
競技中、もうアドレナリン出まくりで競技前には無限に寒かった(このとき半袖です)のが、むしろ無限に暑くなっていた。
1から3問目ははいって感じですぐさま通した。
4問目
緊張しながら問題文を読んだら一瞬でbitDPだとわかった。これはいけると思って実装したがいくつかバグが出て少し苦戦、30分くらいでようやく書ききった。
ここまで1時間近く経過していて、5問目6問目を頑張ってみようとなった。
5問目
同じ標高の場所はないとなって、これは一番小さい場所から決め打ちしていくしかないと思ったのでpriority_queueだと思った。
周囲に尾根だと決まっている場所があるならその場所も尾根になるなとなって、そこを基盤に条件文を書いていたが、状態のもち方がよくなくて、1ケース目と4、5ケース目だけが通って60点になった。
6問目
ダイクストラを拡張するとよさそうだと直感的に思ったので、とりあえずダイクストラを生成。
priority_queueに いつもの重み、次の辺に加えて、部屋に入れるかの条件分岐に使うための時間を新たに持ってダイクストラを変形させていった。
時間の部分を正負をもって表現していたが、配列に使う問のめんどくささを考えて素直にbitを持てばよかったなと思っていたりします。
結局バグが生えて時間が足りず、5分前くらいにダメ元でoutputを投げたがもちろんWA、提出ミスがなければ460点になりました。
競プロを初めた2月3月あたりから今までにかけて、本当に楽しかった、といったのが感想です。
確かに精進は一人でしかできないしつらい時もあったけど、orisano先輩やlatte0119さんなどから知識を吸収して問題を解いて、解けた時は本当に気持ちよくて。
知識はそれ自体に価値があるんじゃなくて知る過程に価値があると学びました。
ただ知っているだけよりも、問題を解くことを通して得た知識は体の奥底に定着する感じ、といったところでしょうか。
これからも精進していきたいと思います。
ぼくをここまで育ててくれたorisano先輩、コーヤ先輩、もからとびあさん、本当にありがとうございました。*5
JOI予選までにこの弱い頭はなんとかなったのでしょうか？
PS : ところでorisano先輩はAdvent Calenderを書かないんでしょうか。25日が空いていそうですよ。
JOI本選 - ぴょんぴょん川渡り ペンキの色
2008年の予選・本選の問題はこれで全完(?)しました
ぱっと見やるだけDP、やってみるとやるだけDP
AOJ特有の複数データセットのおかげでvectorの初期化を忘れており死んでいて無限に時間が吸われたのでAOJに感謝ですね
i 行目の 左から j 番目の石から i + 1行目の k番目に渡る時のコストと今までのコストを足したものが先のコストより小さいなら値を更新、みたいなDP(m回まで1行飛ばしで進めるのでその分もうまく使いますが)
forでDPを解くのを避けてきていたけどそろそろ避けるのをやめていきたいと思ったのでfor で解いた
問題見た瞬間「あ！これ魚の生息範囲で見たやつだ！*1」となった
こんな感じの座圧は一度しか解いていなかったけどこれがわかったことには成長を感じています
座圧していい感じに処理した後は深さなり幅なりで数えあげて終了(完)
どちらの問題も比較的簡単だった気がする(ほんまか)
ペンキの色は座圧だ！となってから時間がかかってしまったのでイメージだけでなくきちんと紙などに書きながら考察していきたい
JOI頑張るJOI
*1:進研ゼミでゎなぃ
JOI予選 - ビンゴ
元気でした(過去形)
ここからまあまあ長い前置きです
先日、我が校は中間試験だったわけで、その中にプログラミングの試験があったのです。
その中の問題の一つに、ビット演算を使って8bit整数の正負を判定しなさい、といった問題がありました。
模範解答は "( (n >> 7) & 1)" だとか "(n & 128)" みたいなものでしょうか。
しかし、某が "(n & 10000000)" と書いていて、なんやこれは(驚愕)となっていたのが実際に動くんですよ。
それで教員やら僕やら回答者やらが困惑する、といった事件がありまして。*1
後日調べたところ、10進数 "10000000" を二進数に変換すると "100110001001011010000000" になって、下8bitが "たまたま" 一致した、と夕飯のときに聞いてその時は納得したのですが、この世にたまたまはない。と、かの有名なぼく*2が言っていたので、その時から気になってしまって土日かけて調べました*3
考えたこと : 10 ^ n を二進数表記した時、下 n bitと10進数表記が一致するのではないか
結論から言えばこれは正しいみたいです。
数学的帰納法とかで証明しようとすれば、最終的に奇数の冪は奇数になるか、といった命題に帰着できるはずなので興味があれば考えてみてください
実はこれまでのことは夕飯を食べながらすでにあらかた考察は終わっていたのですが、他の進数での和、積、分配法則、交換法則とかとかがどうなっているのかとかあまり知らないなと思いまして。
基数を変換しただけなのでほとんど自明に成り立つと思うんですけど、そもそも10進数でのこれらのことすら知らないんですよね。
今度時間があったら考えてみようかと思います。
前置きおわり
まあまあ前に解いた問題
問題を読みます
問題を読むと、n * n のビンゴ == 長さ n * n の単調増加列であることがわかるので、何も考えずにO(MSN^2) のdpを書いたのですが -> TLE
本当によくわからなくて死んでいました
わからなすぎてむしろわかりそうになってきたので解説を見ながらコードを書いたのですが、微妙な理解しか出来ませんでした・・・・
どうやら空間計算量を落として高速化すると通るらしい
また忘れた頃に解き直そうかと思います
ただでさえ DP が苦手なのに for で解こうとすると死んでしまうので慣れていきたいです
ぴょんぴょん川渡りを for で解こうと頑張っています(誰か助言とかくれたらうれしいです)
JOI予選 - タクシー
ビンゴを飛ばしています (2回目)
明日テストらしいので今日は競プロしません
今日解いた問題です
問題は読んでください
方針としては、それぞれの街からいける街を幅をしながら新たな有向グラフとして構築、その上でダイクストラをするといった感じ
ぱっと見やるだけだったので何も考えずに書いたらWAが出た(このとき関数名がbfsなのにdfsを書いています)
WAが出た理由がよくわからなかったので、もう少し慎重にコーディングすることにして、グラフの構築・ダイクストラを分けてやったらそれでもWAが出た(このとき関数名がbfsなのにdfsを書いています)
眠かったので寝たらbfsになる夢を見て自分がdfsを書いていることに気がついたので帰宅後書いたらMLEになった(このとき枝を刈らずに再帰しているため重複しまくり芸人しています)
さすがに気がついたので今度は無駄な再帰せずにくえうえでやったら通った(完)
解法はすぐに思いついくけど意味不明なバグを生成してしまうみたいなことが最近多いので筋肉つけたいと思いました。
はい
