DevAchieve: [競技プログラミング][PHP][AtCoder]謎のたこ焼きおじさん

B - 謎のたこ焼きおじさん

時間制限 : 2sec / スタック制限 : 10MB / メモリ制限 : 64MB

問題文

あなたはたこ焼きを買いに来たところ、伝説のたこ焼きマスター高橋社長に認められ、
新しく作るたこ焼き屋さんの店長を任されました。
店長に任命されたあなたに与えられた最初の仕事は、お店の看板を作成することでした。
ところが高橋社長は~~使えない~~時間がないので、
たこ焼き屋さんの名前は決めましたが、看板を作るのはあなたに任せて去って行きました。
その際に看板を作るための英字ブロックが入ったいくつかのキットを渡されました。
英字キットとは、ランダムな英字ブロックが含まれている袋のことです。
例えば英字キットを表す文字列が ABCC であるような英字キットの場合、

英字ブロックAが1つ含まれている。
英字ブロックBが1つ含まれている。
英字ブロックCが2つ含まれている。

とみなすことができます。
つまり、英字キット ABCC 1 袋につき、
英字ブロックAと英字ブロックBを1つずつ、英字ブロックCを2つを看板に用いることができます。
高橋社長から渡された英字キットは全て同じ英字キットだったので、どのキットを開けても中身は全く同じです。
あなたは看板にお金をかけるわけにもいかないので、開封する英字キットを最小にして残りは返品したいです。
どれだけの英字キットを使うことで、お店の看板を作ることができるでしょうか。

入力

入力は以下の形式で標準入力から与えられる。

N M
name
kit

入力は 3 行ある。
1 行目にお店の名前の文字数 N (1≦N≦50) と、
英字キット 1 袋に入ってる英字ブロックの数 M (1≦M≦50) が空白区切りで与えられる。
2 行目にはお店の名前を表す文字列 name が N 文字で与えられる。
文字列 name に含まれる文字は A-Z のみである。
3 行目には英字キットに含まれている英字ブロックを表す文字列 kit が M 文字で与えられる。
文字列 kit に含まれる文字は A-Z のみである。

出力

看板をつくるために必要な英字キットの最小数を標準出力に 1 行で出力すること。
与えられた英字キットで看板を作成することができない場合は、-1を出力すること。
また、出力の最後には改行をいれること。

出典

B: 謎のたこ焼きおじさん - AtCoder Regular Contest #008 | AtCoder

回答

AtCoder/arc008_2.php at master · wada811/AtCoder · GitHub

<?php
fscanf(STDIN, "%d %d", $n, $m);
for($i = 0; $i < $n; $i++){
    $name[] = fgetc(STDIN);
}
fgetc(STDIN); // throw line feed code
for($i = 0; $i < $m; $i++){
    $kit[] = fgetc(STDIN);
}
fgetc(STDIN); // throw line feed code

$name_counts = array_count_values($name);
$kit_counts = array_count_values($kit);
foreach($name_counts as $key => $name_count){
    if(array_key_exists($key, $kit_counts)){
        $diff[] = max($name_count - $kit_counts[$key], 0);
    }else{
        $count = -1;
        break;
    }
}
$count = isset($count) ? $count : max($diff) + 1;
echo $count.PHP_EOL;
?>

一文字ずつ配列に保存して改行コードを捨てるのが10行目まで。
array_count_valuesで配列の値の数を数えて配列化したら
店名に含まれるアルファベットが英字キットに含まれるかarray_key_existsで探す。
見つからなかったら店名は完成しないのでカウントを -1 にして break する。
見つかったら差をとる。マイナスになったら0にして配列に詰める。
差の最大をmaxでとるが、差なので英字キット1袋分カウントが減るから+1する。

抜けは無さそうなんだけど AC にならないケースがあるみたいなんだよなぁ。
どなたかわかる方コメントや @wada811 にリプライください。お願いします。

追記(2012/09/29): ACになりました。

<?php
fscanf(STDIN, "%d %d", $n, $m);
for($i = 0; $i < $n; $i++){
    $name[] = fgetc(STDIN);
}
fgetc(STDIN); // throw line feed code
for($i = 0; $i < $m; $i++){
    $kit[] = fgetc(STDIN);
}
fgetc(STDIN); // throw line feed code
 
$name_counts = array_count_values($name);
$kit_counts = array_count_values($kit);
foreach($name_counts as $key => $name_count){
    if(array_key_exists($key, $kit_counts)){
        $counts[] = ceil($name_count / $kit_counts[$key]);
    }else{
        $count = -1;
        break;
    }
}
$count = isset($count) ? $count : max($counts);
echo $count.PHP_EOL;
?>

引き算でキット数を計算するのが問題だったようです。
コメントくださったAyaka Kashiyamaさんありがとうございました。
英字毎にカウントは独立しているので考えるべきは以下のパターンくらいだったでしょうか。
(name, kit) = ('A', ''), ('', 'A'), ('A', 'A'), ('AA', 'A'), ('A', 'AA'), ('AAA', 'AA')
1番目はキットに存在しないので -1, 2番目は存在しない英字なのでチェックが行われない, 3番目は 1/1 で 1,
4番目は 2/1 で 2, 5番目は 1/2 で ceilで切り上げて 1, 6番目は 3/2 で同様に切り上げて 2 になる。
うーん。悔しい。反例を見つける力が足りない。悔しい。

DevAchieve

ページ

2012/09/28

[競技プログラミング][PHP][AtCoder]謎のたこ焼きおじさん

B - 謎のたこ焼きおじさん

問題文

入力

出力

出典

回答

追記(2012/09/29): ACになりました。