【Java】HashSetはぇぇぇーーーーってなった
競技プログラミング始めました
仕事でコード書く機会があまりにないので、ストレスが溜まってきた。ということで、AtCoderあたりやろうかなーと。また、スマホのアプリでも作りたいんですが、時間がかかるのとリハビリもかねてまずはコード書くことから始めました。
AtCoder Beginner Contest 073
過去問とかやってみてもCまでは何一つ悩むことなく、解ける感じでした。
しかし、今回Cでつまってしまった。はずかしー。言語はとりあえずJava
こんな感じ。
・A September 9 ふっ ちょろいぜ。OK！
・B Theater ふっ ちょろいぜ。OK!
・C Write and Erase ふっ ちょろいぜ。あれ、おわんないぞ・・・
TLE！ん？実行時間制限超過？
いやー実行時間なんて気にして実装したことなんてないわー。
とりあえず、下記で書いた。
import java.util.ArrayList;
import java.util.Scanner;
public class Main
{
public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
ArrayList A = new ArrayList();
for(int i=0;i<N;i++)
{
int a_i=sc.nextInt();
boolean find = false;
for(int j=0;j<A.size();j++)
{
if(a_i==A.get(j))
{
find=true;
A.remove(j);
break;
}
}
if(!find)
{
A.add(a_i);
}
}
sc.close();
System.out.println(A.size());
}
}
上記は、TLE(実行時間制限超過)。
これあれかーーー。二重ループの中が重いやつかー。二分探索にしよ。でWiki見て理解して載ってたC言語をJavaに書き換えて作ったのが下記。
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;
public class Main
{
public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
LinkedList A = new LinkedList();
for(int i=0;i<N;i++)
{
int a_i=sc.nextInt();
int index= binary_search(A,a_i,0,A.size()-1);
if(index==-1)
{
A.add(a_i);
Collections.sort(A);
}
else
{
A.remove(index);
}
}
sc.close();
System.out.println(A.size());
}
final static int KEY_NOT_FOUND =-1;
static int binary_search(List list, int key, int imin, int imax)
{
if (imax < imin)
{
return KEY_NOT_FOUND;
}
else
{
int imid = imin + (imax - imin) / 2;
if (list.get(imid) > key)
{
return binary_search(list, key, imin, imid - 1);
}
else if (list.get(imid) < key)
{
return binary_search(list, key, imid + 1, imax);
}
else
{
return imid;
}
}
}
}
びっくりするくらい何も変わらない。final付けたり、 ArrayListをLinkedListに変えたりもじもじしたんだけど、ちょっとしか早くならない。もじもじしてたら、終わってしまった。Javaで解けてる人の解答みるとHashSet*1を使ってる。でHashSet使って作り直したのが、下記。
import java.util.HashSet;
import java.util.Scanner;
public class Main
{
public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
HashSet A = new HashSet();
for(int i=0;i<N;i++)
{
int a_i=sc.nextInt();
if(!A.contains(a_i))
{
A.add(a_i);
}
else
{
A.remove(a_i);
}
}
sc.close();
System.out.println(A.size());
}
}
ハッシュはぇぇぇーーー！！ACになった！！間に合わなかったけどｗｗｗ
なんでもかんでもListにぶち込むのはよくないと。趣味でやってるとこういうところの感度が磨かれない気がする。重複した値を格納できないので、使い道が限定されるような気もするけど、勉強になった。
余談
というか、Javaで競技プログラミングってどうなんでしょうね。
遅くて不利な気もするけど。
あと、5分で全部解いてる人とかどういうことｗｗｗ
自前である程度定型的な部分のコードを用意しているとしても早すぎるｗｗｗ
おそるべし競技プログラミングの世界
