きのうのQUPT

昨日(3月28日)九州大学プログラミングコンテスト(QUPC)に参加しました
誰も一緒に出る人がいなかったので一人での参加

QUPCってどんなの

• 九州大学のICPCチャレンジ部がAtcoder上で開催したコンテスト
• ICPC国内予選突破できるかできないか、ぐらいの人を想定している
• 5時間開催されていて、全部で8問が出題された

手を付けた問題(A～D,H)の概要

A - 成績判定

最低合格ラインを全探索で求めた

B - 元素の系統名

入力に対応した元素名をswitch-case文で出力するだけの糞コードを書いた

C - 案内所

指定された文字列の全探索を普通にやると、多分TLEして80点の部分点がもらえる
TLEしそうだなーと思い最近覚えたメモ化を使って計算量を落とす。通る。バンザイ！

D - 切符分割

パッと見て「ダイクストラっぽい」と思ってよく読むが、どうもそれだけだと部分点しか貰えないっぽい
ダイクストラ勉強中だし、not部分点解法が思いつかないしでスルー

H - お風呂は気持ちいい

なぜか通してる人が問題番号のわりに多かったのでチラ見、部分点解法が簡単っぽかったので手を付ける
魔力受け渡しのルートが分岐しないので、ルートたどって魔力が足りているかを見るだけ
なぜか途中で大事な変数に上書きするミスを犯し、WAを量産しながら部分点を獲得

結果

A,B,C完答で300点、Hの部分点で40点、合わせて340点の58位だった
ゼロsubmiterを除くと97人参加していたっぽいので、半分以下の順位

感想

• CまではWAを出さず、1時間以内に解けたのでまぁよかった
• ダイクストラやDPなど、中途半端にしか知らず使えない手法をさっさと使えるようにならないとダメっぽい
• DPを学ぶ過程で覚えたメモ化が利用できたのでちょっと嬉しかった
• わりと出来たかなと思っても この程度の順位だったので、ICPCアジア予選目指す人の強さが身に染みた