POJ Monthly Contest – 2009.04.05

ICPC

北京大学オンラインジャッジが主催するプログラミングコンテストに出てみました。ICPC形式で5時間8問です。前情報なしで参加したのですが、いつも通りの可も無く不可も無くな成績でした。

問題A Conscription

少年少女たちを軍隊にスカウトする。一人スカウトするためのコストは10000だが、既に誰かをスカウトしてある場合、その人と親密度dの人はコスト10000-dでスカウトする事ができる。全員をスカウトしたときの最小コストを求めよ。
ぱっと見でグラフ問題だという事は分かります。少し考えて最小領域木だ分かりました。Prim法で書いたところTLEし、Kruskal法で書き直して通しました。
一問目から最小全域木が出るとは思いませんでした。

問題B Find the parameter

以下の式の(x,y)の座標が何点か与えられる。a0〜a9を求めよ。
y=\sum^{9}_{i=0} \exp ( a_{i} x )
全探索を十重ループを書いて通しました。yの値を絶対誤差で評価するコードがWAだったため、二乗誤差が最小になるa0〜a9を求めるコードを書いたところ通す事ができました。斬新な問題だったと思います。

問題C I know the k-th integer

1〜nまでの数を辞書順にソートしたとき、k番目の数がmである事が分かっている。nの値を求めよ。
数論です。思いつきませんでした。

問題D Windy's ABC

A・B・Cの文字のみからなる文字列Sを並び替える。このときそれぞれの文字はRA・RB・RC文字までしか移動させてはならない。RA・RB・RC・Sが与えられたとき、何通りの並び替えができるかもとめよ。
最後に見たA・B・Cの位置のDPだと思って書いたのですがTLEでした。やはりDPは鬼門のようです。

問題E Newton’s Method

与えられた方程式をニュートン法を使って解く。何回で収束するかもとめよ。
苦手な構文解析でしたがオートマトン使って書きました。サンプルは通ったのですがWAでした。

問題F The merchant

木構造をしたグラフが与えられる。それぞれの点では商品を売買する事ができる。出発ノードと目的ノードが与えられたときの最大の利益を求めよ。
問題内容を勘違いしていたようで全く思いつきませんでした。

問題G Facer’s string

文字列S1・S2が与えられる。k文字の拡張共通文字列S3の数を求めよ。拡張共通文字列とはS1でもう一文字取ったとき、文字列がS2で出現しないような文字列である。
文字列系は苦手です。すいません。

問題H Ebbinghaus method

単語の暗記をする。暗記をするときには初めに暗記してから何度か何日か経った後に復習する。暗記と復習にはそれぞれ80分と40分かかる。一日に勉強に使える時間は120分である。全て暗記し終えるまでに何日かかるかもとめよ。
数論系は苦手です。すいません。

最終結果

40位/375人という全くぱっとしない成績でした。せめてもう一問解きたかったです。というか問題難易度高いよ・・・。

Contest - POJ Monthly Contest -- 2009.04.05 http://acm.pku.edu.cn/JudgeOnline/showcontest?contest_id=1339