Codeforces Round #500 (Div. 2) の感想

問題

codeforces.com

結果は、問題Aだけ解くことができました。英語があまり得意ではないので、自動翻訳にかけながら解いていました。英語も勉強しないといけませんね。

A. Piles With Stones

題意を理解するのに結構時間が掛かりました。

この問題を解釈すると、石の数を二回数え、その結果があり得るかどうかを判定するというものです。

一回目に数え終わったあとに、石を別の山に移動させるか、石を消滅させるかといったことが行われます。

したがって、二回目にチェックした石の数の総数が二回目よりも多くなることはありません。なので、石の総和を計算すれば良いことが分かります。

B. And

これも題意を理解するのに時間が掛かりました。コンテスト中に解くことは叶いませんでした、終了後に解くことができました。

ある配列の要素 と自然数 の論理積が の値になります。具体的に示すと、

＆

となります。この操作によって得られる配列の中で、 () を満たす要素を作り出します。このとき、操作の最小回数を答えます。操作に得られない場合、 を出力します。

考え方

＆ としたとき、 となればその要素は変化しません。以後その値に操作を加える必要はありません。僕の解法は、Mapのキーに要素の番号を指定し、キーに配列の番号と操作回数を持つ二次元配列を指定しました。これで、ある値を得るために必要な操作回数とその要素番号を記録できます。

また、操作を行う値はHashSetに格納しました。HashSetの中身が0となればこれ以上操作はできないということです。

うまく説明できませんが、コードを見ればなんとなくわかると思います。

コード

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class ProblemB {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int x = scan.nextInt();

        //ArrayList<Integer> list = new ArrayList<Integer>();
        ArrayList<Integer> list = new ArrayList<Integer>();
        Set<Integer> set = new HashSet<Integer>();
        HashMap<Integer, int []> map = new HashMap<Integer, int []>();
        for(int i = 0; i < n; i++) {
            int t = scan.nextInt();
            set.add(t);

            int[] a = new int[2];
            a[0] = i;
            a[1] = 0;
            map.put(t, a);
        }
        scan.close();
        if(map.size() != n) {
            System.out.println(0);
            System.exit(0);
        }
        int min = 0;
        while(set.size() != 0) {
            for(int i : set) {
                int t = i & x;
                //list.add(i);
                if(i != t) {
                    if(map.containsKey(t)) {
                        int []a1 = map.get(i);
                        int []a2 = map.get(t);
                        if(a1[0] != a2[0]) {
                            int ans = a1[1] + a2[1] + 1;
                            if(min == 0) {
                                min = ans;
                            }else if(min > ans) {
                                min = ans;
                            }
                            //System.out.println(ans);
                            //System.exit(0);
                        }
                    }else {
                        list.add(t);
                        int[] a1 = new int[2];
                        int[] a2 = map.get(i);
                        a1[0] = a2[0];
                        a1[1] = a2[1] + 1;
                        map.put(t, a1);
                    }
                }

            }
            if(min != 0) {
                System.out.println(min);
                System.exit(0);
            }
            set.clear();
            for(int i : list) {
                set.add(i);
            }
            list.clear();

        }
        System.out.println(-1);
    }
}

感想

CS Academyに続き海外のコンテストに参加したんですが、問題が難しくアルゴリズムとデータ構造の勉強が足りません。また、問題が英語で与えられるので英語力も必要となります。