【ハッシュメニュー】ハッシュ関数を作ってみよう (paizaランク C)-解答例-PHP編

2022年7月19日

【ハッシュメニュー】> FINAL問題ハッシュ関数を作ってみよう (paizaランク C 相当) [難易度: 1600 ±31]

※リンク先へ移動するためには[paiza]へのログインが必要です。

問題文

文字列を受け取り、0 以上 100 未満の整数を返すハッシュ関数を作成してみましょう。

ハッシュ関数は、以下のような性質を持っていることが期待されます。

・同じ入力に対して、常に同じ出力を返す
・出力から入力を推測することが難しい
・出力が一様に分布している (出力値に偏りがない)

これらの条件をなるべく満たすような、オリジナルのハッシュ関数を作ってみましょう。

n 個の文字列が与えられるのでそれぞれの文字列について、あなたが作ったハッシュ関数を用いてハッシュ値を計算し、出力してください。

この問題は決まった答えがないため、スペシャルジャッジを採用しています。ジャッジプログラムは、あなたの作成したハッシュ関数が 1 つめの条件を満たしている場合に正答とします。

どんな文字列に対しても 0 を返すハッシュ関数を用いてもこの問題は正解することができますが、この関数は 3 つめの条件を全く満たせていません。

また、文字列の長さを返すハッシュ関数を用いてもこの問題は正解することができますが、この関数は 2 つめの条件を満たせていません。

2 つめと 3 つめの条件がなるべく満たされるように、工夫してみましょう。

入力値（例）
5
abc
bca
cab
aaa
abc

出力値（例）
14
11
11
6
14

解答例

<?php
    $n = trim(fgets(STDIN));
    
    for ($i = 0; $i < $n; $i++) {
        $s = trim(fgets(STDIN));
        
        $hash = 0;
        
        for ($j = 0; $j < mb_strlen($s); $j++) {
            $hash += ($j + 1) * (ord($s[$j]) - ord('a') + 1);
        }
        $hash %= 100;
        echo $hash. "\n";
    }
?>

<?php

$n = trim(fgets(STDIN));

for ($i = 0; $i < $n; $i++) {

$s = trim(fgets(STDIN));

$hash = 0;

for ($j = 0; $j < mb_strlen($s); $j++) {

$hash += ($j + 1) * (ord($s[$j]) - ord('a') + 1);

}

$hash %= 100;

echo $hash. "\n";

}

解説

ハッシュ関数を好きに作っていいという問題で、色々作れそうでしたが公式の解答を参考にしました。

文字列"a"に1、"b"に2、...、"z"に26を割り当てて入力文字列に対して、

H(s) = (c_1 * 1 + c_2 * 2 + ... + c_n * n) % 100

をハッシュ関数として採用しています。

ord()というのは、アルファベットを数値に変換する関数です。

ord関数は以下の文法で使用できます。

ord('文字列')

ord("A") //65
ord("a") //97

返り値は文字列のUnicodeコードポイントを表す整数が返されます。

ord関数は1文字に対して有効なので、文字列は1文字しか設定できませんので注意が必要です。

解答例

解説

カテゴリー