ページ

2012/12/09

[競技プログラミング][PHP][DigitalArts プログラミングコンテスト2012]Password

B - Password

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

問題文

セキュリティに興味がある高橋君は、デジタルアーツ株式会社に就職したい青年です。
そこで、高橋君は自分が運営するサービスであるAtCoderのセキュリティについて見なおしてみることにしました。

現在AtCoderのシステムでは、パスワードは 1 文字以上 20 文字以下の英小文字のみとしています。
そして、文字列 s に対してハッシュ値( hash(s) )を求める以下の式があり、
パスワードと入力した文字列に対して、それぞれこの式で算出したハッシュ値が一致すると、
入力した文字列は正しいとみなします。

hash(s)=Num(c1)+Num(c2)+…+Num(cN) (ci は文字列 s の i 番目の文字を意味する)

なお、上記の式の関数 Num() とは英小文字を数字に変換する関数で、
Num(a)=1, Num(b)=2, …., Num(z)=26 というように、
a から z に対して順に 1 から 26 までの数字を返します。

高橋君は、このシステムではパスワードと違う文字列でも
簡単にハッシュ値が一致してしまうことに気づきました。
例えば、文字列 abc のハッシュ値は、1+2+3=6 となりますが、
文字列 bbb のハッシュ値も 2+2+2=6 ですし、f も 6 になってしまいます。

高橋君は、現在使っているパスワードに対してどのような文字列が
正しいパスワードとして認識されてしまうか知りたいです。
正しいパスワード以外で条件を満たすものを 1 つ出力しなさい。
条件を満たすものが複数ある場合は、どの文字列を出力しても構いません。
もし条件を満たすパスワードが存在しない場合は NO と出力しなさい。
なお、AtCoderのシステムで入力できるパスワードは 1 文字以上 20 文字以下の英小文字のみなので、
答えとして出力する文字列もその条件をみたします。

入力

入力は以下の形式で標準入力から与えられる。
c1c2‥‥cN
入力には正しいパスワードを表す長さ N(1≦N≦20) の文字列が 1 行で与えられる。
正しいパスワードの i 番目の文字を表す ci は英小文字 (a-z) である。

出力

与えられた正しいパスワードを表す文字列と等しいハッシュ値になる英小文字 1 文字以上 20 文字以下の文字列を、
正しいパスワード以外のいずれか 1 つ出力せよ。
また、そのような文字列が存在しない場合は NO と出力せよ。
なお、出力は 1 行のみとし、最後には改行を出力せよ。

出典

B: Password - DigitalArts プログラミングコンテスト2012 | AtCoder

回答

AtCoder/digitalarts_2.php at master · wada811/AtCoder · GitHub
<?php
$password = trim(fgets(STDIN));
$ascii_a = ord('a') - 1;
$numbars = array();
for($i = 0, $end = strlen($password); $i < $end; $i++){
    $numbars[] = ord($password[$i]) - $ascii_a;
}

$sum = array_sum($numbars);
// special case
if($sum === 1 || $sum === 26 * 20){
    // 'a' or 'zzzzzzzzzzzzzzzzzzzz'
    echo 'NO' . PHP_EOL;
    exit();
}

$answers = array();
if(count($numbars) === 1){
    // 'b' - 'z'
    $answers[0] = $numbars[0] - 1;
    $answers[1] = 1;
}else{
    while($sum){
        $answers[] = min(26, $sum);
        $sum -= min(26, $sum);
    }
}
// ex. 'za' -> 'az'
while($answers == $numbars){
    shuffle($answers);
}

$another_password = '';
for($i = 0, $count = count($answers); $i < $count; $i++){
    $another_password .= chr($answers[$i] + $ascii_a);
}
echo $another_password . PHP_EOL;
?>
2行目でtrimし忘れて意図しない改行コードで答えが合わなくて泣きそうになった。
文字列を配列でアクセスできるので1文字ずつアスキーコード変換して配列に入れる。
答えが NO になる例外を弾き、1文字のパスワードとそうでないもので処理を分ける。
後は28行目に書いたようなやつのためにshuffleして入れ替えておく。コレで確実。
あとはアスキーコードを逆変換して出力!