PCK2015本選参加記

参加記というか、参加した証拠(入賞)すら得られていないので敗北記。

• 浜松 -> 会津若松
• 東海道新幹線と東北新幹線をクリアした後、磐越西線
• 東海道新幹線はINF回目だけど、その後ははじめて
• 東北新幹線は4列
• レールが狭いから?
• なんか新幹線競プロしてたのですぐ着く
• 昨年のICPCを適当に
• 4完
• 磐越西線は闇
• 狭い
• 長い
• さすがに在来線競プロは不可能
• 1時間強
• 18時到着
• そんな寒くない
• ホテルへチェックイン
• ワシントンホテル(みんなそうらしい
• 我々は和室
• 畳の匂い
• 夕ごはん
• ラーメン二郎
• ちょっと並ぶ
• 周りはほとんど高校生や大学生
• 熱い
• 舌やけどした
• 美味しい
• 周りからの視線をちょっと気にする
• (側近の方が居座ってないではやく。。って言ってたから)
• ちょっと早く食べる
• 意外と胃が大きい
• 早食いフェーズはAcceptした気がする
• ちょっと足りないのでプリン
• 甘い
• さらに競プロ
• 一昨年のICPC
• 4完
• 昔解けた素数洞穴解けないけどなんなの
• 時間が溶けた
• 解法合ってるのになんか通らない暗示?
• 睡眠フェーズ
• 寝れるはずがない(n回目
• n ≧ 5
• n = 1とか 2 とかのときよりは余裕で寝れたと思う
• っていうか、福島県寒いって聞いてたけど暑い
• 暑くて眠れない
• 2日目
• 朝食
• 適当に済ませる
• 納豆がないのでつらい
• コンビニへ昼食を求めに行く
• 納豆巻がある
• 買う
• やったね
• バスに乗って会津大へ
• 昼食
• 酢飯に納豆はあわn
• でもおいしい
• プリンもクリームがかたよってたけど美味しい
• 開会式
• 見たことがあるひとが多い
• 筧先生知ってる
• 競技
• 最も辛い瞬間
• とりあえず1問目を相方に任せる
• 3 を読むけどこれ桁DPだ(甘い考察
• ICPCの覆面算だっけ
• 4 を読むけど日本語が分からなくてつらい
• 10分くらい、・・・。って感じ
• ボッコｔかマルグとかで作問者を推察
• なんかこれ多倍長でしょっておもう(幼児並の考察
• なんかこれ繰り返し二乗法でしょっておもう(小学生並の考察
• そもそも問題文読めないし焦っている
• その後10分眺めてなかったことにして、5を読む
• 20秒眺める
• あっこれ校内のオンランジャッジに入ってるUSACOの問題そのままだ
• 解けそう(明確な確信
• 相方や周りのチームの状況を見るけど、1問目なんなんだろう
• なかったことにして 2 問目
• 裏で私が 1 を考察
• これなんか面倒くさい全探では
• 頭いいやり方と悪いやり方がありそう
• 明確に頭がわるいやり方
• 2 問目Acceptしたらしい
• 1 問目時間かかりそうだけどやる
• x,yが2つでy,zが2つでx,zが2つあれば良いなぁ
• 適当に割り振ってソートしてぎゅわんってやる
• 汚いソースコードになってしまった
• なんとか賞とれない
• とれる解法ではない
• いろいろあったけどサンプル一致したので提出
• Accept
• 3 問目も時間かかりそうだけどやる
• メモ化なんていらなさそう
• 覆面算のソースを脳に思い浮かべながらそれをコピー
• 入力がめんどくさい
• バグバグ
• ビット操作に失敗している
• (ここnext_permutation()使ったら良かったね)
• FCSとかヘッダ・チェックサムとか私の頭に実装されていれば良いのに
• つらい
• なんとかつじつまを合わせたけどいろいろ合わない
• 入力形式が違ってた、つらい><
• 時間を失い頭を失う
• なおすと通ったので提出
• Accept
• 4 問目はよくわからないので相方に和訳してと懇願
• 5 問目は絶対的確信があったので3分で実装して提出
• Accept
• 4 問目の和訳が終了したらしい
• どうやら多倍長は計算量がつらいらしく、繰り返し二乗法も使えなさそう
• 2^a * 2^b = 4^(a+b) という新定義を導き出す
• Σ4^(ai+bi) からひいてけばいいのかなぁ
• 4のpiyo乗と2のhoge乗を組み合わせるのつらくね?
• 結構時間がたったあと 2^a * 2^b = 2^(a+b) だったことに気づく
• 数学疎い
• てかこの問題数学とかではないのでは
• なんか2^(a+b)と2^xの形になってるわけだし、2は外せるのでは
• そんなイメージをもって、なんか図を書く
• やっぱa と b 足して、右に伝搬させながら割るだけでは
• この制約で線形解は自明かつ自明
• 解法かっこいいよね
• よい
• 提出
• Accept
• ココらへんで引率の顧問が気になる
• ちょっと後ろ見上げて探す
• 真ん中ら辺
• どうでもよかった(我に帰る
• 6はまだ誰も提出していないので闇
• 7は読むのがめんどい
• 8は割と区間DPで行けそう
• テストケース20個だし、O(n^3)だろうなぁ
• 幅決めて終始点決めて、なんか頑張ってMerge
• かなりつらい
• なんか考えてみると パターンがいろいろありそう
• ちょっとなぁ
• 9も見てみる
• 複数の交差判定を logNあるいはlog^2 n でやりたいわけね
• データ構造ゲーかなぁ
• 解けそう
• Y軸とX軸を分けると楽そう
• ある線が新たに加えられる線分とする
• 直交する線との交差判定(平行線同士は適当で
• ノードにx or y座標の集合を持たせておけば、にぶたんでその区間内に横線があるかどうかわかる
• 区間へのx or y座標の追加と、区間の線分の有無を調べる機能をもたせれば良さそう
• X軸Y軸を入れ替えて2つseg木生やせば余裕そう
• いろいろバグってるけどなんとか終わる(20分前
• (ていうかここで20分前なのね><)
• 提出
• 不正解
• 平行線同士を適当にやったのが裏目に出ていそう
• なんかとまどいつつなおす
• 提出
• メモリ超過
• そんなメモリ厳しいんだ
• で、あとこれ解は正しいんだ
• しっかりメモリのことを考えて丁寧に実装
• メモリと仲良くしたい
• 提出
• 時間超過
• えっ・・・・。
• あーーーー。
• 5秒でO(Nlog^2N)おちるの
• logNが20程度だから・・・400 × 10^5 = 4 * 10^7
• POJかな
• 二分探索の回数を半分にした
• 提出
• 時間超過
• けどちょっと早く終わった気がする
• ・・・。
• 定数倍改善ゲーなの(疑心暗鬼
• 途中にrand() % 2を埋め込んで提出
• 不正解
• 定数倍改善ゲーなの()
• 時間がきてしまった
• 撃墜
• ホテルへ
• あれ名札がない
• 名札がないと明日の昼食が
• スタッフへ
• 何とかしていただけるらしい
• 申し訳がない感じ
• あとから9問目はジャッジのプロに時間制限5秒で、手元で7秒とか言われてかなしい
• かつ解は正しいらしい
• 悲しみの果て
• よくよく考えるとこれ春合宿のときも無駄な定数で落とした気がする
• 私が書いた任意のコードに定数INFがかかっているのでは
• 留年すれば2度目のチャンスがありそう(進路決まってたりして誰も許さなさそう
• あと学ランを着ていて暑くなったので脱いだ
• 名札あった。
• (申し訳がない感じ)^2
• スタッフへ
• じゃんけん大会
• 最初にパーだして負けたのでかなしい
• 翌日9問目について痛恨の事実が判明
• 平衡二分木のSTLのsetを使うところは良かったらしい
• setのlower_bound()するところでSTLのlower_bound()を用いていた
• ランダムアクセス不可能なのでO(N)
• seg[k].lower_bound(x) でよかった
• ていうかなにを考えてSTLを使ったんだろう(多分何も考えてない
• 座標圧縮フェーズでSTLのやつ使った(これはvectorでO(logN))からその流れかも
• そこ直す(3箇所)
• 手元で0.2秒になる
• 出したやつ、O(N^2logN)だしそりゃ間に合わないよね
• 表彰式
• 10位(悲しみ
• あれ解けてたら5位だったのにつらい
• 6やって1WA以内なら8位だったみたいだけどこれは結果論っぽい
• でも6やって9やらなきゃ悔いは少なかったかも