＼はい、2つのグループに分かれてー／

「2人組を作ってー」と空目した人は
そういう話ではないので安心してほしい。
なんであの言葉はみんながドキッとするんだろうね。

この様な問題が出た。

E - Select Mul（注：問題のタイトルです）
問題文

整数N が与えられます。N の各桁の数字を取り出して並べ（並べる順序は好きに変えてよい）、2 つの正整数に分離することを考えましょう。

例えば、
123 という整数に対しては以下の 6 通りの分離の仕方が考えられます。
12 と 3
21 と 3
13 と 2
31 と 2
23 と 1
32 と 1
なお、ここで分離されたあとの2 整数に leading zero が含まれていてはなりません。例えば、101 という整数を 1 と 01 の 2 つに分離することはできません。また上述の「正整数に分離する」という条件より、101 を 11 と 0 の
2 つに分離することもできません。

適切にN を分離したとき、分離後の 2 数の積の最大値はいくらになりますか？

制約
・N は 1 以上 10の9乗 以下の整数
・N には 0 でない桁が 2 つ以上含まれる
入力
入力は以下の形式で標準入力から与えられる。
N
出力
分離後の2 数の積の最大値を出力せよ。

AtCoder Daily Training All 2025/02/20 20:30Start E - Select Mulより

まず考えないといけないのはNを桁毎にどの様に分けるかという事だ。
3桁の数字なら1つを選んで、残りと乗算。
4桁の数字なら1つを選んで、残りと乗算、加えて2つを選んで残りと乗算。
5桁の数字なら1つを選んで…もう良く分かんなくなってきた。

ここで使うのが2進数なのである。
2進数はご存じの通り0と1で表す数値の表現方法である。

左の10進数をそれぞれ2進数にしたもの（下4桁）

ここで右の2進数に注目してもらいたい。
3桁の数字があるとして
1が付いている桁の数字をAグループ
0が付いている桁の数字をBグループと割り振ると
1～6の表現で全パターンの分け方が網羅できるのである。
（問題の趣旨からしてA,Bそれぞれに分けないといけないので
全部がどちらかのグループに分かれてしまう000(0)，111(7)は除外）

分かり易く図示したもの。3匹の動物がビットに応じてグループに分けられる
（追記：例えば1と6ではグループが違うだけで分け方としては一緒である。
ループ上限は半分でいいのかもね）

それぞれをグループ分けしたら今回の問題では
「2つのグループの積の最大値」を求めるので
グループ毎に「降順（大きい数値から小さい数値へ）」に並べ直し
数値化の上、乗算を行い、既存最大数値と比較という流れになる。
また、leading zeroについては積算なので結果が大きくなる事は無い。
（102より012の方が小さいので掛けた所で結果は小さくなる）
従って考慮は不要になる。
除算だったらzero divide（0除算）があるので考慮しないといけないけども。
出来たコード（C言語）を以下に示す。

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

// QuickSort用(char型用：降順)
int f_Sort(const void* pcv_1, const void* pcv_2)
{
    if ((char)(pcv_1) > (char)(pcv_2))		    return -1;
    else if ((char)(pcv_1) < (char)(pcv_2))		return 1;
    else return 0;
}

// bitマスクにより全パターン洗い出し
long long f_GetMaxProduct(char* pc_Num)
{
    int i_Len = (int)strlen(pc_Num);
    long long ll_MaxProduct = 0;
    int i_Cnt,i_Cnt2;
    int i_Digit = (1 << i_Len) - 1;
    for (i_Cnt = 1; i_Cnt < i_Digit; i_Cnt++)
    {
        char c_Left[11] = "", c_Right[11] = "";
        int i_li = 0, i_ri = 0;

        // 各桁を左右のグループに振り分ける
        for (i_Cnt2 = 0; i_Cnt2 < i_Len; i_Cnt2++)
        {
            // Bitが1の場合はc_Leftへ、0の場合はc_Rightへ
            if (i_Cnt & (1 << i_Cnt2))
            {
                c_Left[i_li] = pc_Num[i_Cnt2];
                i_li++;
            }
            else
            {
                c_Right[i_ri] = pc_Num[i_Cnt2];
                i_ri++;
            }
        }
        c_Left[i_li] = 0x00;
        c_Right[i_ri] = 0x00;

        // 片方が空なら処理をパス
        if (i_li == 0 || i_ri == 0) continue;

        // それぞれを降順（つまり最大値）にソート
        qsort(c_Left, i_li, sizeof(char), f_Sort);
        qsort(c_Right, i_ri, sizeof(char), f_Sort);
        long long ll_LeftNum = atoll(c_Left);
        long long ll_RightNum = atoll(c_Right);
        long long ll_Mul = ll_LeftNum * ll_RightNum;
        if (ll_Mul > ll_MaxProduct)
        {
            ll_MaxProduct = ll_Mul;
        }
    }
    return ll_MaxProduct;
}

int main(void)
{
    char c_Num[11] = { 0 };
    long long ll_Result;
    
    scanf("%s",c_Num);
    ll_Result = f_GetMaxProduct(c_Num);
    printf("%lld\n", ll_Result);

    return 0;
}

何で急にこんな問題を記事にしたのか。
2進数で2グループに分ける方法をコロッと忘れていたからである。
（もしくはｎ個の中からm個を選別する方法としても応用可能）
しばらくこのパターンをやってなかったら頭の中から抜け落ちていた。
備忘録としてここに残しておこうと思う。