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;
?>
文字列を配列でアクセスできるので１文字ずつアスキーコード変換して配列に入れる。
答えが NO になる例外を弾き、１文字のパスワードとそうでないもので処理を分ける。
後は28行目に書いたようなやつのためにshuffleして入れ替えておく。コレで確実。
あとはアスキーコードを逆変換して出力！