CodeIQ：共通の友達の最大数は？

問題の概要

問題を引用します。

例えば、次の図のような友人関係の場合、共通の友達の最大数は3人になります。
（2番の人の友人が1, 3, 4, 5で、4番の人の友人が1, 2, 3, 5のため）


標準入力から次のような入力があります。
【入出力サンプル】
INPUT

5
1 2
1 3
1 4
3 4
2 3
2 4
2 5
4 5

OUTPUT

3

1行目がこのリストに登場する友人番号の最大値、2行目以降に友人関係がある場合に、そのペアを空白区切りでセットされています。
このとき、標準出力に「共通の友達」の最大値を出力します。

私のプログラム

Javaで解答しています。

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

/**
 *
 * @author kamio
 */
public class Main {

    // 1人の友人を管理するクラス
    public class Person {
        long[]  Friends;            // 友達の場所（0始まりなので-1）のビットに1を立てる。
        private final int Max;      // メンバの数
        int ID = 0;                 // 自分のID
        int FriendsNum = 0;         // 自分の友人数

        /**
         * コンストラクタ
         * @param n 友人の最大数
         * @param id 自分のID（0始まり）
         */
        public Person(int n, int id){
            Max = n;        // 友人の数（自分を含む）
            ID = id;        // 自分のIDをセット
            int size;   // 必要なビット数分配列を用意する

            if(n%64 == 0){
                size = n/64;
            } else {
                size = n/64 + 1;
            }

            Friends = new long[size];
        }

        /**
         * 友達の場所に1を立てる
         * @param pos 友人のID（1始まり）
         */
        public void set(int pos){
            int row = (pos-1)/64;    // 配列の何個めを使うか
            int col = (pos-1)%64;  // 使用する配列要素の何ビット目か

            Friends[row] |= 0x8000000000000000L >>> col;
        }

        /**
         * 友人の一覧を表示する
         * @param f 友人のリスト
         */
        public void printFriends(long[] f){
            for(int j=0; j<f.length; j++){
                long l = f[j];

                for(int i=0; <<64; i++){
                    if(((l<<i) & 0x8000000000000000L) != 0){
                        System.out.print((j*64+i+1) + " ");
                    }
                }
            }
            System.out.println("");
        }

        /**
         * 自分の友人の番号を列挙する（デバッグ）
         */
        public void printFriends(){
            System.out.print((ID+1) + ": ");
            printFriends(Friends);
        }

        /**
         * 引数の友人と共通の友人を返す
         * @param p 友人のID
         * @return 共通の友人リスト
         */
        public long[] getCap(Person p){
            long[] ret = new long[Friends.length];

            for(int i=0; i<ret.length; i++){
                ret[i] = Friends[i] & p.Friends[i];
            }

            return ret;
        }

        /**
         * 1が立っているビットを返す
         * @param v ビットを数えたい値
         * @return 1が立っているビットの数
         */
        private int count64bit(long v){
            long count = (v & 0x5555555555555555L) + ((v >> 1) & 0x5555555555555555L);
            count = (count & 0x3333333333333333L) + ((count >> 2) & 0x3333333333333333L);
            count = (count & 0x0f0f0f0f0f0f0f0fL) + ((count >> 4) & 0x0f0f0f0f0f0f0f0fL);
            count = (count & 0x00ff00ff00ff00ffL) + ((count >> 8) & 0x00ff00ff00ff00ffL);
            count = (count & 0x0000ffff0000ffffL) + ((count >> 16) & 0x0000ffff0000ffffL);
            return (int)((count & 0x00000000ffffffffL) + ((count >> 32) & 0x00000000ffffffffL));
        }

        /**
         * 友達の数を返す
         * 自分以外の友人数（共通の友人数など）を数えるため引数をとる
         * @param v 友人リスト
         * @return 友人の数
         */
        public int countFriendsNum(long[] v){
            int count = 0;
            for(int i=0; i<v.length; i++){
                count += count64bit(v[i]);
            }
            return count;
        }

        /**
         * 自分の友人数を計算する
         */
        public void calcFriendsNum(){
            FriendsNum = countFriendsNum(Friends);
        }
    }

    /**
     * グループ（Personの集まり）
     */
    ArrayList<Person> Group;

    /**
     * コンストラクタ
     */
    public Main(){
        Group = new ArrayList<>();
    }

    /**
     * グループのメンバでグループを初期化する
     * @param n メンバ内の人数
     */
    public void init(int n){
        for(int i=0; iGlt;n; i++){
            Group.add(new Person(n, i));
        }
    }

    /**
     * 友人をそれぞれに設定する（1始まり）
     * @param p1 友人関係にある一方のメンバのID
     * @param p2 友人関係にある他方のメンバのID
     */
    public void set(int p1, int p2){
        // Groupのインデックスは0始まり。setは1始まり。
        Group.get(p1-1).set(p2);
        Group.get(p2-1).set(p1);
    }

    /**
     * 入力が終わった時点で友人の数をカウントする
     */
    public void calcFriendsNum(){
        for(Person p: Group){
            p.calcFriendsNum();
        }
    }

    /**
     * 友人の一覧を出力する（デバッグ）
     */
    public void printFriends(){
        for(Person p: Group){
            p.printFriends();
        }
    }

    /**
     * 共通の友人の最大数を返す
     * @return 共通の友人の最大数
     */
    public int getMaxCommon(){
        int max = 0;
        for(int i=0; i<Group.size(); i++){
            Person p1 = Group.get(i);

            for(int j=i+1; j<Group.size(); j++){
                Person p2 = Group.get(j);

                // 友人数が現在の最大値より小さい場合は無視して良い
                if(p2.FriendsNum < max){
                    continue;
                }
                else{
                    long[] c = p1.getCap(p2);
                    int n = p1.countFriendsNum(c);
                    if(n>max){
                        max = n;
                    }
                }
            }
        }
        return max;
    }

    /**
     * @param args the command line arguments
     * @throws java.io.IOException
     */
    public static void main(String[] args) throws IOException {
        try (BufferedReader stdReader = new BufferedReader(new InputStreamReader(System.in))) {
            Main MxC = new Main();
            String line;
            int lcount = 0;
            while ((line = stdReader.readLine()) != null) {
                line = line.trim();
                if(line.isEmpty()){
                    break;
                }

                if(lcount == 0){
                    int n = Integer.parseInt(line);
                    MxC.init(n);
                    lcount++;
                    continue;
                }

                String[] splited = line.split(" ");
                int p1 = Integer.parseInt(splited[0]);
                int p2 = Integer.parseInt(splited[1]);

                MxC.set(p1, p2);
                lcount++;
            }

            MxC.calcFriendsNum();

            int max = MxC.getMaxCommon();
            System.out.print(max);
        }
    }

}

解説

CodeIQの回答のコードとしてはかなり長いコードです。デバッグプリントを含んでいるのもありますが、入力される人の数が64bit整数の範囲に収まるかどうかが問題になかったのでそれに対応するために長くなった部分もあります。
ちなみに、これは★★★で難しいとされている問題です。

雑感

プログラムが長い割にそれほど難しいことはしていません。
この問題をやった時点ではまだPythonを覚えていなかったのですが、Pythonの様に自動的に任意精度整数を使える言語なら人数が64人を超えても気にしなくて良いので、ずっとプログラムが短くなります。わざわざクラスを作る必要もなく、整数の配列を用意するだけで事足りてしまいます。

私は、この問題は仕事で使うプログラムでも似た様なことをする場合がありそうな良い問題だな、と思った記憶があります。