paizaオンラインハッカソンLiteに参戦
m人以上を満たす最小コストを求める問題だったので
ナップザックすればいいと思いググってやり方を調べたが
一定以下で最大値を求める方法ばかりだったので
以下の方法でやることにした。
方法
必要人員m,会社数n,人q_i,費用r_iとする。
最大人員manMax = Σq_i(i=1 to n)である。
普通に動的計画法でやるとmanMaxを最大値にして、mを超えた分の最小コストを計算してしまう。だが、0～m-1は無駄である。
使わない人間をカウントすることを考え、manMaxの中で不要な人員とその最大コストを計算すれば以下のようになる。
不要な人員target = manMax - m
不要なコストwallet = max(targetのコストをDPする)
最大コストmaxCost = Σr_i(i=1 to n)
m以上の最小コストAnswer = maxCost - wallet
重要なのはtargetに"-m"項が入ることで、計算量がO(Σq*n)からO((Σq-m)*n)に落ちることである。
maxManがmに近いほど有利で、mが大きくなっても有利なのでcase6,7に効果が期待できる。
結果
POH Lite 0.01s
全ては0.01のために
Console.WriteLineを1回だけ呼ぶだけで0.01s遅くなることが分かった。
そして入出力ゲーをしてアンマネージドな関数を使用したが、0.01にならなかった。
厄介な壁にぶつかって、アルゴリズム見直しすら考慮したが
dp配列の初期化が以下のように-1埋めになっていたので
古いコード
for (int i = 1; i <= target; i++) // 未使用は-1埋め
dp[i] = -1;
C#の配列初期値0を生かして
dp[0] = 1; // 使用中は1以上とする
上記のように1オフセットすることにし、最終結果の計算で1戻すことにしてみた。
それで0.01になったのを見ると、初期化すらC#は遅いので0のままでどうにか処理できる手法をとった方が良いのかもしれない。
(それとも">=0"と">0"で有意差があるのか？)
ソース
初回0.01sのコードはコメント類や未使用コードが残っていたので整理した。
このコードも0.01sを確認済み。
using System;
using System.Text;
using System.Runtime.InteropServices;
using System.Collections.Generic;
namespace ConsoleApplication2
{
class Program
{
[DllImport("libc")]
static extern int read(int handle, byte[] buf, int n);
[DllImport("libc")]
static extern int write(int handle, byte[] buf, int n);
[DllImport("libc")]
static extern void printf(string format, int value);
static int readRef = 0;
static byte[] rBuf = new byte[10000];
static int readint()
{
int ret = 0, tmp;
while ((tmp = rBuf[readRef++] - '0') >= 0)
ret = ret * 10 + tmp;
return ret;
}
static void Main(string[] args)
{
int m, n, maxMan=0, target, maxCost=0, wallet=1, current, val;
read(0, rBuf, 10000);
m = readint(); // 目標
n = readint(); // 会社数
int[] man = new int[n];
int[] cost = new int[n];
for (int i = 0; i < n; i++)
{
maxMan += man[i] = readint(); // 人数
maxCost += cost[i] = readint(); // 費用
}
target = maxMan - m; // 不要な人月最大値
int[] dp = new int[target + 1];
dp[0] = 1; // 使用中は1以上とする
if (man[0] <= target)
wallet = dp[man[0]] = cost[0] + dp[0]; // 初期値
for (int i = 1; i < n; i++ )
{
current = man[i]; // 処理中の会社の人月
for (int column = target - current; column >= 0; column--)
{
if (dp[column] > 0 && (val = dp[column] + cost[i]) > dp[column + current] )
{
dp[column + current] = val;
if (val > wallet)
wallet = val; // 残る金額最大を目指す
}
}
}
printf("%d\n", maxCost - wallet + 1); // 費用最大値-残る金+1=最小金額
}
}
}
結論
DPじゃなくコスト率のほうが簡単と言う情報が出て、そっちに行きかけたがなんとかなってよかった。
Consoleの付く関数は死んでも使ってはいけない。
VSでこのコードを動かそうしても動かない。libcをmsvcrtにしてもダメでどのDLLにすればいいのか分からない。
お陰でデバッグが面倒であった。
DPを配列じゃなくSortedDictionaryなどにしてAddでやったら有意に遅いので辞めた。
ハッシュ効率と再ソート時間が単純な配列走査に劣るらしい。