迷いませんか?

プログラミング、電子工作、ゲーム・・・etc、色々やるけど中途半端なブログです。

JOI'18春合宿参加記

JOI春合宿2018

JOI本選通ったため春合宿に行ってきました
これを書いているとき僕はまだ春合宿中です
何日目かあててみてください
文章の変化とかから頑張ればわかりそう

一日目

部活のえんやこらをした後に東大に入ってパスタを食べて偏差値を上げる
データセンターについた後、プラクティスを頑張る
1. なんかコミュニケーションなんですがコミュ障なのでなかなか通らない 2. エスパーなんですが、超能力者なので3回ぐらいで通る(超能力者なので)
3. Output OnlyなんですがOutputする、LinuxかCに慣れてないと厳しそう
4. 電 子 レ ン ジ 4問目なので当然一番難しい

この後オリセンに行き講義を受ける
簡潔データ構造面白そうとなるけど途中までだったので悲しい気持ちになる
頭がないので計算量とてつもなく気持ち悪いと思いました

ねる

二日目

起床できる
朝ごはんに向かうとめっちゃ混んでいる、やばい
社会性の塊なのでバスの出発時間には当然間に合う

競技1日目が始まる

一問目

木で頑張ろうみたいな
何もわからず何もわからなかったため何もわからなかった
部分点だけセグ木で取る

二問目

幾何で頑張ろうみたいな
とりあえず部分点だけ取ろうとしたらめっちゃバグるためめっちゃバグる
終わる

三問目

整数二個はやばいためやばい
横に置くのと縦に置くのとそのまま置くのの数を全探索$O(N3)$を書く部分点ですね
そのまま置くのを高速化すれば嬉しそうみたいなことが分かる
sum(nCk * 4k * mPk)みたいな感じで二項定理とかで頑張ろうとするけど無理
ところで、そのまま計算することが小さければできるのでテーブルっぽく表示させて眺めます
なんか遷移が見えます(超能力者なので)
そこをDPにすることでなんとか満点がとれます

16+0+100でした

講義を受ける
双対難しいんですが慣れない5時間コンテストの疲れから序盤で寝てしまい途中から覚醒するも何も理解できないやつをする

解説

ねる

三日目

朝ごはんに行くとめっちゃ混んでいる(前日比INF倍、階段で下の階まで及んでいて何が起きているんだとなる)
社会性に満ちているのでバスの出発時刻+5分ぐらいに着く

競技二日目

一問目

整数二個じゃ~ん
眺める
わからないねと思い二問目三問目をやってきてから解く
わからなすぎるため小課題1の全列挙を書く
わからないね
全列挙ということは小さければ計算できるね
テーブル表示させよっか
にらみます
dp[i][j] = dp[i-1][j]*j+dp[i-1][j-1]*(i-j+1)という遷移が見えます(超能力者なので) 流石にレッド超能力者にはブルー超能力者なので及ばず部分点で止まりました

二問目

Output Only
完全に見た目がマラソンだったので最初に焼きなましか山登りを書いて時間内回そうみたいな気持ちになる
実装がバグって2時間半ぐらいかかる(vectorはeraseすると添字ズレするのに気づくことできないね)
回すけどすぐ更新止まるし頂点がかたまっていて乱数バグってんじゃーんとなる(解説情報ですが本質です、青なので気づけない)
まあそのまま何回か実行して出しまくるとある程度取れる
裏で回すと重くなるためやるべきではなかった

三問目

難しくないですか?難しいと思います
前に人の1後ろに行くことにしばらく気づかずなんか詰まる
それに気づいたらなんか座標+iが嬉しそうなことに気づいてO(1)で出せるように頑張りにぶたんする
なんか定数倍か何かがきつすぎたのか、scanfやprintfに直しても通らずlong longをintにしたら通った

49+54+100=203でした

講義を聞く
純粋関数型データ構造
怖いね

解説を聞く
一問目がわからない

寝る

四日目

朝起きる
前日の教訓を活かして早めに向かう
あまり並ばずにすむ(並ぶ)

社会性が高いのでバスの集合時刻に間に合う

競技三日目

一問目

コミュニケーション
与えられた頂点に番号がついているグラフを、頂点に番号がついていないグラフで表現しろみたいな問題
無向グラフだと考えることで頑張ってとく
有向グラフなので簡単に解けるらしくキレる

二問目

びたろうくんだれやねん
DAGなのでダイクストラで部分点を取ろうとしてTLEになってハマるを無限時間続ける
DAGなのでDPで出来る
部分点が取れる
満点思いつきたかったね

三問目

パット見簡単枠現実不可能枠
お気持ちになることで小課題1解法で小課題2まで通す
終了
やばDP書くけど重複して数えていることに気づき死ぬ

講義を聞く チューターが少ないことが印象的でした

解説を聞く
三問目理解できない

寝ます

五日目

起きる
もう全然混んでいない
余裕のバス搭乗AC

一問目

2乗DPを書きます。部分点を得られます
セグ木DPを疑いながらわからないため諦めます

二問目

リアクティブですね
補集合で二分探索を疑うとわかりかけるけど考察して実装始めると記憶が消えるため何もわからない
終了

三問目

グラフ、全点始点でうまくダイクストラを前計算して良さそうなのいくつか持てば良さそうとなる
部分点1しか通らなくて終了する

8+19+12=39
春合宿に感謝を告げて終了
サンキュー春合宿

二問目、春合宿中に1か2を争う簡単さっぽくて人生終了
通してたらJAPAN2だったんだよなぁって永遠に言い続けて死んでいきます

六日目

チューター企画のSKIコンビネータがある
純粋に難しいため難しく、異世界の科学を異世界の言語で学んでいる気分になっていた
面白いので頑張りたかったけど圧倒的に頭が足りなかった
地頭の塊になりたかった

まあここまでで実質終了なため終了
五、六日目の夜にワードバスケットやコードネームをやって楽しみました、楽しかった