回答編集履歴
2
そういやunorderedの方だった
answer
CHANGED
|
@@ -4,6 +4,6 @@
|
|
|
4
4
|
|
|
5
5
|
どうすれば良いのかというとハッシュ値を使います。ハッシュテーブルは聞いたことがありますか？そうです、ハッシュテーブルの仕組みと同じような物を使えば、**前と同じ文字列があるかどうかがO(1)で判断できます**。その繰り返しなので、最終的にはO(N)になると言うことです。
|
|
6
6
|
|
|
7
|
-
他言語であれば、C++なら`std::
|
|
7
|
+
他言語であれば、C++なら`std::unordered_set`、Javaなら`java.util.HashSet`、Pythonなら`set`、Rubyなら`Set`を、JavaScriptなら`Set`というものが標準で用意されていますので、こちらを使うと簡単に書けます。しかし、Cにはこのような便利なオブジェクトの型は用意されていません。ですので、自分で作る必要があります。
|
|
8
8
|
|
|
9
9
|
ハッシュテーブル、セット、等のキーワードでCでの実装方法を探してみて下さい。
|
1
ちょっと言葉を追加
answer
CHANGED
|
@@ -1,6 +1,6 @@
|
|
|
1
1
|
Cではやりたくない問題ですね。[Rubyなら7行](https://atcoder.jp/contests/abc164/submissions/15809303)で済みますから。
|
|
2
2
|
|
|
3
|
-
まず、解き方が間違っています。文字列を一つ一つ比較していくとなるとO(N^2)の時間計算量が必要です。しかし、この問題はO(N)に抑えることができます。
|
|
3
|
+
まず、解き方が間違っています。文字列を一つ一つ比較していくとなるとO(N^2)の時間計算量が必要です。これではどんなに頑張っても時間内に終わらすのは難しいです。しかし、この問題はO(N)に抑えることができます。
|
|
4
4
|
|
|
5
5
|
どうすれば良いのかというとハッシュ値を使います。ハッシュテーブルは聞いたことがありますか？そうです、ハッシュテーブルの仕組みと同じような物を使えば、**前と同じ文字列があるかどうかがO(1)で判断できます**。その繰り返しなので、最終的にはO(N)になると言うことです。
|
|
6
6
|
|