競技プログラミングをやっていると多次元配列をINFや-INFで初期化したいことはよくあるかと思います。
ここではmemsetを利用した初期化の方法について解説します。
memsetは1byteごとに指定した値(memsetの第二引数の値)で埋めていきます。
ということはmemsetの第二引数の値は1byte以下の値で十分だということがわかります。
1byteは8bitなので、16進数だと2桁分になります(16進数では1桁が4bitに相当します)。
たとえばint型の配列nについて考えてみましょう。
int型はたいてい4byteです。
ということはmemsetの第二引数で1byte分の値を設定すると、それが4回繰り返された値が配列の一要素の値となります。
つまりint型の配列nに対して
memset(n,0xff3f,sizeof(n));
と
memset(n,0x3f,sizeof(n));
は同じで、どちらも配列nの各要素を1061109567(=0x3f3f3f3f)で初期化します(intは4byteなので32bit、つまり16進数だと8桁になります)。
つまり、memsetの第二引数で16進数で値を設定するときは下位2桁で十分で下位2桁以外は無意味となります。
先の例でいうと0xff3fのffの部分は無意味です。
では、8bitで最大の値と最小の値はいくつでしょうか。
なお、ここでは、8bitで最大の値をINF、8bitで最小の値を-INFと考えたいと思います。
2の補数表現だということを考慮するとMSB(最上位bit)が1だと負整数になるので、
8bitにおける最大の値は2進数で表現すると01111111、16進数で表現すると0x7fとなります。
また、8bitにおける最小の値は2進数で表現すると10000000、16進数で表現すると0x80となります。
まとめ
INF(=2139062143)で初期化したいときは
memset(n,0x7f,sizeof(n));
-INF(=-2139062144)で初期化したいときは
memset(n,0x80,sizeof(n));
とするのがよさそうです。
配列nの要素がINFかどうか判定するときは
int型の場合は0x7f7f7f7fと比較
long型の場合は0x7f7f7f7f7f7f7f7fと比較
と比較することになります。
もしINFや-INFの値を厳密に設定したいときは
最初の次元数がNのint型の配列n(たとえばint n[N][N+1][N+2])に対して
fill((int*)n,(int*)(n+N),INF);
で初期化することもできます。