読者です 読者をやめる 読者になる 読者になる

ヘクトのメモ

なんとなくいろいろ書いていくと思います.

KUPC 2015

KUPCに個人で参加してきました.
結果は48位でした.

以下,コンテストの詳細


銀座に向かう.
ATNDのトラップを回避して会場に着く.
開始が20分遅れたので,自己紹介タイムが設けられる.


0:00 Start!

A問題に取り組む.
貪欲すれば良さそう.
書くけど,1WA
テンプレートが悪さをしていた.
修正して提出する.

0:06 A AC

B問題が面倒くさそうだからC問題を見る.
与えられたグラフに対して,WFしてから元のグラフと一致しているかどうかを見る.
0:13 C AC

B問題に取り掛かる.
頭を働かても,答えが思いつかないで全探索する.
テーブルのマス数N=100に対して,計算量O(N^5)だから答え出るのだろうかとプログラム動かす.
すぐに解答がでてくる.textで提出
1:18 B AC

D問題に取り掛かる.
ある地点に移動した時の最大金額を求めるようなコードを書く.
最後のサンプルが通らなくて,しばらく放置する.
変数ミスだった.修正して提出
2:30 D AC

E問題に取り掛かる.
正方形に内接する正三角形とか調べる.
長方形の長い方の辺の2点と向かいの中点の三角形が最大になるとか気づく
サンプルは通る.でも,WA

H問題に切り替える.
X=Nの時が答えの上限になるから-1にはならない.
LSBの方から貪欲に見るコードを書く.
WA
シミュレーション解と合わせて調べてみて,無理そうと放置

F問題に取り掛かる.
スタックとキューの違いをどうするかが思いつかない.
そこで,構文木を書いてみる.
スタックとキューからDFSとBFSの関係を考えてみる.
構文木の深い方から,同じ深さのものを計算していく.
また,右・左の順にQueueにPushする.
構文木の生成をスタックで書く.
サンプル通る.提出する.
4:04 D AC

E問題に再び取り掛かる.
三角形をパラメータで決められると考える?
凸関数の最大値を求める問題になりそう? (たぶん,嘘まじっている)
長方形に内接する三角形の1辺の最小値を返す関数fを作る.
関数fに対して,三分探索する.
サンプル通る.良さそうと思い,提出する.WA多発する.
バグ修正する.提出する.
4:41 E AC

G問題に取り掛かる.
各人がBi以下の人にマッチングして良いというインデックスiを求める?
この配列に対して,バブルソートの交換回数を求める.
サンプル通る. WA
5:00 Finish!

G問題の解法はうまくマッチングだったみたい...
去年に比べると解いた問題数が3問から6問に増えて,驚いた.
G,H,I問題まで復習かな...
F問題はDFSとBFSの概念を比較して,解くという問題で楽しかった.
最後に,KUPCのスタッフの方々お疲れ様でした.
(あと,ケータリング・お菓子美味しかった.)

解答コード
All submissions - 京都大学プログラミングコンテスト2015 | AtCoder