http://poj.org/problem?id=3345 いくつかの木が与えられ，その各ノードにコストが割り振られている． 全部で N 個のノードの中から M 個以上の頂点を選んだときの，コストの和の最小値を求めたい． ただしあるノードを選んだとき，そのノードのコストで，そ…

http://acm.pku.edu.cn/JudgeOnline/problem?id=3255 重み付きグラフが与えられて，2番目にコストが小さい経路のコストを出力する問題． 1番コストが小さいものなら普通のダイクストラ法でいいのだが，今回は2番目なので各頂点に対して2番目までのコストを覚…

http://acm.pku.edu.cn/JudgeOnline/problem?id=3615 N 個の駅があり，M 本の一方通行の道が繋いでいて，それぞれの道には高さ H_i のハードルがあるとする． 駅 A_i から駅 B_i まで行くとき，途中で越えなければならないハードルの最大の高さの最小値を出…

http://acm.pku.edu.cn/JudgeOnline/problem?id=2591 次のように定められた集合 S の N 番目(昇順)の要素を出力する問題． 1 は S の要素である x が S の要素ならば，2x + 1 と 3x + 1 も S の要素である その他は S の要素でない N の上限が 10000000 なの…

http://acm.pku.edu.cn/JudgeOnline/problem?id=3014 整数 n, m (1 ≦ n, m ≦ 4500) が与えられて，m を n 個の整数の和に何通りに分割できるか答える問題． ただし答えは非常に大きくなりうるので，答えを 1000000007 で割った余りを出力する． DP で解いた…

今日は 1008 -- Maya Calendar をちょっとがんばってみた。 問題文が長くて、理解するのにだいぶ時間がかかった。 ようするに 変換元の Haab => 一年は19ヶ月で、1-18ヶ月目は20日間で19ヶ月目は5日間(つまり一年は365日)。月の名前は pop, no, ..., cumhu, …

そんなテクニックも取り入れつつ、微妙に縮めたら 1002 が以前と同じ方針で 348B まで縮んだ。 c(int*a){a=*a-*1[&a];}i;j;d;main(n){int*m;char b[99];for(m=calloc(n=atoi(gets(b)),4);gets(b);i++)for(j=0;b[j];j++)b[j]>81&&b[j]--,m[i]=b[j]>64?10*m[i]…