PCK2018 参加記
明日 isucon 予選全然眠れないのと高校生活最後の学生向けプロコンだったので書きます
結果は 1, 2, 3, 4, 6, 7, 8 を AC
何故か5を落としているのと大量の WA で順位は30位入ったかな〜程度（凍結後ACしたので不明）
記憶が曖昧なので時系列はバラバラかもしれない
前準備
流石に３回目の参加ということもありいつも使ってるテンプレートとおまけ程度しか印刷せず
蟻本も持っていったが出番は無かった
開始後
１〜６は相方に任せる方針で７以降の問題を見た
見た目７と９が解けそうだったのでトイレに行った
14:00〜
１〜３問目を相方に書いてもらい一応自分も目を通して提出: AC
４問目も書き終えてもらいソースを見た時に while で書いていて危ないから if で書こうと言いつつもそのまま提出: WA
自明バグが合ったので提出: WA
意味がわからなかったので while を抹殺して提出: AC
WA の差で勝利は無理だろうと大量提出作戦を決意
14:30〜
ようやく7問目の実装に着手
自分の方針が N ^ 2 のことに気づくも書いている途中に思いつき提出: WA
自明バグ、提出: WA
自明バグ、提出: WA
自明バグ、提出: AC
この時点で確か15:00を回っており本戦出場を断念（５が厄介そうだったので）
15:15〜
6問目の方針を伝え実装してもらう: AC
5問目が思いつかないみたいなので自分も考える
実は制約が8秒で愚直解でも通るらしいが特に見ていなかった
適当に思いついて実装: WA
何が悪いのか分からずコードは完成させたので相方に投げた（後から別チーム確認すると方針は合っていた）
終了
6完という最悪の状態で終了
気分が最悪だったが終了１０分後くらいにふと提出履歴見ると8問目AC
脳汁がタプンタプンだった
競技を終えて
４問目と５問目で１時間以上使っていそうなので非常にもったいなかった
特に４問目はバグりそうだと思いつつも２回提出してしまったので反省
この程度の問題ならバグった時点で書き直したほうが圧倒的に早いという知見を得たのでまぁ
６問目も typo を一緒に探したりしていて割と時間食ってた
１〜８まで考察に１０分以上かかった問題は無かった気がするけどここまで手こずったのは普段から提出デバッグしているせいなので気をつけようと思う（ｎ回目）
とりあえず目標の３０位には届いていそうなので悪くは無いがもう少し丁寧にやれば結構順位が上がったので思い返してみるとなんとも言えない
ちなみに９問目は全く解けていなかった
余談
PCK 後の AGC で 900 点問題を初 AC でパフォ 2000 超え
実は前回超えたときは JOI 予選後の ARC だったので AtCoder 出る前に何かしら問題といたほうが良いかもしれないと気づいた
square869120Contest #5 I - Collecting Gems is Fun
条件分岐しまくったらWAが出てしまいコンテスト中にはACできなかったがその後無事４位(コンテスト中)に該当する点数を取れたので適当に方針を書く
https://beta.atcoder.jp/contests/s8pc-5/submissions/2365849
コードが非常に汚いのは方針事体はものすごくシンプルなので、なるべく早くACしたかったからです（それが故に墓穴を掘りましたが
まず重要な相対位置の設定に関してですが、
- (0, -1)
- (0, -2)
- (0, -3)
- (0, 1)
- (0, 2)
にしました
何故こうしたのかは後々説明します
次に移動の仕方についてですが、相対位置の設定を見れば分かる通り一番最初に右に３個ズレます
その後はずっと下に行って、一番下に着いたら右に６個ずれてずっと上に行って右に６個ズレて...の繰り返しです
移動中に close か get-close が出てきたらまずは左に進みます
ここで仮に far か get-far が出れば、もとのいちに戻り close であれば右にあるので取りに行きます
これにより相対位置 (0, 2) と (0, 1) のみ、またはそこにプラス (0, -1) に宝石がある場合は (0, 2) で6回、(0, 1)で4回の移動で取ることができます
もう一度 close か get-close が出れば同じように左に進みます
ここで far か get-far であれば、↑と同じような操作をすれば (0, -2) と (0, -1) プラス (0, 2) で8回, (0, 1) で6回の移動で取ることができます
もう一度 close か get-close も↑と同じ動作を行います
これにより宝石のある範囲が移動する回数になり
(0, -1) (0, 1) 4回
(0, -1) (0, 2) 6回
(0, -2) (0, 1) 6回
(0, -2) (0, 2) 8回
(0, -3) (0, 1) 8回
(0, -3) (0, 2) 10回
で宝石を取りに行くことができます
なぜ左から取るようにしたかというと右は未探索で他の宝石が入ってしまうためです
左に3、右に2 という理由について
まず何故左右でちがうかというと、仮に 3, 3 の場合、右に取りに行く時に誤動作する確率が多くなるからと↑のコードでは改修の際に消してしまいましたが枝刈りの余地を残せるからです（もしかしてこれが原因？
3 と 2 である理由については感覚的にこれが一番最適かなと思ったからです（適当）
100 / (右 + 左 + 1) * 100 + (200 - 同じ探索範囲内の数) * ↑の平均回数
でスコアがざっくり求まるので案外簡単に最適っぽいのは求められるのですが、残念ながら今回はWAだったため調整ができませんでした
提出人数が少なかったりそもそも適当に点数稼いで終わりの人も多そうですが自分の割にはとても良い得点が出たので方針載せておきました
セグ木を木構造のまま出力する
そのまま配列を出力しても見難いので作った
struct K { int l, r, h, k; }; void SegTree::out() { int t = 0, kn = 1; while(n > kn) { kn *= 2; t++; } int h[t + 1] = {0, 1}; rep(i, 2, t + 1) h[i] = h[i - 1] * 2 + 1; queue<K> q; K k = {0, n, 1, 0}; q.push(k); while(!q.empty()) { queue<K> nq; K pp = q.front(); if(pp.k > n) break; rep(i, 0, h[t]) cout << " "; while(!q.empty()) { K p = q.front(); q.pop(); cout << dat[p.k]; if(t > 0) rep(i, 0, h[t + 1]) cout << " "; else cout << " "; K lk = {p.l, (p.l + p.r) / 2, p.h * 2, p.k * 2 + 1}; K rk = {(p.l + p.r) / 2, p.r, p.h * 2, p.k * 2 + 2}; nq.push(lk); nq.push(rk); } t--; cout << endl; q = nq; } }
こんな感じに出力できる
テストケース程度なら問題なさそう？
学校生活振り返り
この記事は N高等学校 Advent Calendar 2017 21日目の記事です
ネタがないので過去を振り返ることになったのですが記憶が曖昧なので時系列順箇条書きで大雑把に書いていきます
競プロ関連のみにする予定だったけど１ページも埋まらなかったので学校生活全体を振り返ります
本当はポエムを書きたかったけど文章力の無さに驚いた
4月
N高提携スクール？のPHHに通い始める
あまり記憶は無いがPCが届かなかったことは覚えている
プログラミングはあまりやらなかった印象
5月
恐らく基礎文法を学んだ
HTML + CSS + JavaScript でスライドショー的なやつを作った気がする
jQuery も扱っていたが僕は何故使うかよく分からなかったので使っていなかった記憶
遅刻に緩い学校だと気づいてしまう
6月
Node.js を使ってサーバーサイドに関する知識を学んだ気がする
ここらへんでインフラ周りが出てきたと思うが当時はよく分からなかった印象
DBとか聞いてもメモ帳に書いておけば良いやんけ！！！とか思っていたので覚えようとしていなかったが正解かもしれない
午前の授業に30分遅れがち
7月
チーム開発が開始する
ゲームを開発するグループとwebサービスを開発するグループがあったがどっちも入った
ゲームはHTML5のcanvasでの作成だった
webサービスははてブっぽいのを制作
イスを活用し始める
8月
ゲーム開発の一回目の発表があった
作ったやつ
一応製作期間は1ヶ月あったが諸事情により２日で仕上げたものを発表した
上記の理由により[要出典]他のゲーム班の作品よりも圧倒的低クオリティかつ未完成品という良くない結果だった
メソッド名、変数名の重要さを知る
ここらへんから家でゲームをする時間を割いてプログラミングをする日がでてきた
運動をしなくなったせいか体の至る所に不調が出始める
9月
パソコン甲子園というものに出場する
結果は10問中4問正解で予選突破とかなり遠かった
学内ISUCONなるものが開催され1位を取れたが、アプリケーションが簡潔すぎてインフラはあまり関係なかったのでISUCONっぽくなかった
ついでに本当のISUCONにも出たが何もできずに死亡
都内の焼肉はコスパが最悪な事に気づく
10月
ここで webサービス + ゲームの制作発表
webサービスではスクレイピングと検索機能を担当して重みを付けたりしてみた
ゲームは未完成のまま発表の日を迎えたのですごく反省した
ISUCONで何もできなかったのが悔しかったのでインフラ関連を少しずつ勉強し始めた
授業ではあまり理解していないと思っていたインフラだったが、全体の流れをあまり把握できていなかっただけでそれなりに知識は付いていた
11月
ここでTwitter上の声優へのリプライをひたすら垂れ流すアプリケーションを作成したのですがいろいろあれなので公開しません
このアプリケーションが"まともな"webアプリを一人で作り終えた最初のアプリケーションだったと思います
意外と大半のオタクはマナーが良く、本当に一部だけが目立ってるんだなと思った
あとherokuはとても素敵だと思います
12月
JOIと言うものに参加して三完
順位的には中間くらいだったと思う
その後にたまたまAtCoderのABCで30位くらいを取れたので競プロモチベが上がる
N高のレポート提出締め切りがあったが、仲間との *\.✝絆✝./* により見事やり遂げる
某ゲームのイベントで時間と資産を大量に消費するが世紀の大爆死を遂げこの世の真理に辿り着く
1月
ゲームやったりアニメ見たり人生を満喫する
この時期はまたチーム制作が始まっていた(既に終わった?)気がするが何か流れた
2月
記憶喪失
3月
卒業制作でSNSを作成した（未完成
というのも企画から発表まで確か1ヶ月程しか無かったので僕程度がSNSを完成させられるはずもなく死亡
主にフロントが面倒くさかった間に合わなかった
提携スクール卒業😭
webアプリで一発当てて余生を優雅に過ごそうと決意
再び競プロを休んでいたがAtCoderのABCでたまたま一桁順位を取れてしまったのでモチベがまた上がる
4月
家の近くにプログラミングのバイトがないのでマクドナルドでバイトを始める
これは最悪の決断だったので時を戻せるなら園児に戻り英才教育を受けて天才になってた
人がいないと言われるがままにシフトを入れてしまってプログラミングがかなり疎かになる
5月
週一のAtCoder以外プログラミングをしなくなる
アルバイトの業務自体は楽だけど人種が完全に別世界のあれなので色々あれになって自分が社会不適合者だと自覚する
6月
SuperConなるものの予選に応募する
N高の強い人のおかげで難なく突破
7月
競プロを頑張り始める
競プロを頑張るにあたって基礎教養の無さに絶望する
主に英語と数学が必要に感じたがどちらも3以上の評定を取った記憶がない
8月
SuperConの本戦で座る役を務める
そのおかげ[要出典]で4位という結果を残す
カラオケ楽しい
9月
パソコン甲子園の予選に出る
2人組で出場するのだがペアがプロなので難なく突破
ただ、僕一人でも地域枠という形で予選を突破可能だったということだけは書き残しておきたい
ISUCONに向けて再びweb関連に触れ始める
10月
ISUCON予選に出る
メンバーは学生向けのISUCON勉強会に参加していた人で(学生)組んだ
学生枠で本戦出場した
終了30分前までfail(実は勘違い)からの5万点獲得という大波乱？が起こったのでかなり嬉しかった
アプリケーションは少ししか弄っていなかったので苦手だと思われたインフラの知識でどうにかできたのが良かった
11月
パソコン甲子園の本戦に出て9位
ペアの実力的に良い結果ではなかったがこちらも言い訳すると7問目は考察が完了して5問目は実装まで終わってたので実質3位(は？
終盤で解けた問題が積み上がっていくという事故が起きたので来年は実装速度を上げたいと思った
あとお互いに体の状態も良くなかったので来年は前泊したい気持ちがある(僕は単なる風邪明け
どうもプロの方が一人のほうがパフォーマンスが出るとの事なので来年は２チームに分かれて本戦に出る(予定)
ISUCONの本戦があった
結果はfailで終わってしまった
Node.js で出たのだがDBに入る予定のデータをメモリに乗っけた際に toString を抜いてしまい、バリデーション(恐らく型チェック)で落ちてしまったのだが型ガバガバ言語あるあるなのか挙動は至って正常なので原因特定に非常に時間がかかり3時間くらい使ってしまった
合計500行程度のコードを理解するのに2時間かかってしまったのも人のコードを読むのを嫌っていたからだと反省
アプリケーション重視で勝つなら今年が狙い目だっただけに非常に残念
12月
JOIの予選に出た
結果は386点で予選突破
しかしあまり良いスコアではないので本戦はもっと頑張りたい
某クラウドソーシングサイトでお金を稼げたが成長を全く感じないので選択肢としては無しかなという印象
総括
最初はN高の入学を考えている方向けに書く予定だったけど、ただただ事象を箇条書きするだけの無意味なものになってしまった
しかし過去を振り返ると将来へのモチベが上がってきたので誰にも読まれない技術ブログくらいの価値はあったかと思います
JOIやISUCONの結果を踏まえて自分が入学当初想像していたレベルは大きく上回っているかなと思います
しかしプロダクトを開発する能力は著しく欠けてると思うし、一般的な学生がプログラミングをやるとしたらそこを頑張るという印象があるので数値として出ない部分でも頑張っていきたい所存です
あとこの記事は主にN高生の方が見ると思うので宣伝ですが #club_computer で一緒に競技プログラミングをする方を募集しています
if文 for文 が書ける方なら始められるので気軽に参加してみてください
パソコン甲子園は年齢制限がないのでどなたでも出れます
現役？高校生の本戦出場枠を潰していきましょう！！！
もうひとつ最後に来年の ISUCON に一緒に出てくれる方を募集しています
目標は本戦出場くらいなので気軽に声をかけてください
ISUCON学生枠は非常に緩いのでwebアプリ応用くらいを終えていれば後は過去記事を読み漁るだけで勝てます(多分
