python collectionとかいう神ライブラリ

最適化問題を解いた

私、哀川は前回の反省を活かし、最適化問題と全探索の問題を中心に勉強を進めていきました。

いざ、Atcoderへ

ということで、哀川は最適化問題と全探索の問題に関しては、万全を期して206に望みました。（いや、そんな気になっていただけというのは後の祭り）

A問題は速攻で解き、B問題も少し苦戦しながらも解けました。

そして、、、C問題！

「これは。。最適化問題だ！！！」

やったー！直近でやった内容を駆使すれば解ける！哀川はルンルンな気持ちで問題を解き進めました！

実際のコード

import itertools
n = int(input())
ns = list(map(int, input().split()))
count = len(ns)*(len(ns)-1)/2
minus = 0
for x, y in itertools.combinations(ns, 2):
   if x == y:
       minus += 1
sum = count - minus
print("%d" % sum)

「よし！vscode上でも動作確認したし、これでおけ！」

と思いながら、提出。結果は、、、

AtCoder「TLE（時間かかりすぎだよ）」

また、お前かぁぁぁああああ！！！

ぐぬぬ。どうやらfor文を２重にまわしているのが、良くないみたい。

「そんなん、しゃーないやん！！！」

結果的に、206では、A,B問題しか解けなかった。。。

レートが少し下がった。。。。まぁ、まだ灰色だから気にしない！！

大事なのは、復習！！

復習内容

ということで、後日いろいろ調べてみると

【AtCoder解説】PythonでABC206のA,B,C,D問題を制する！ - Qiita

これは、、、僕のための記事！！

解けなかったC問題、D問題を中心に解説を呼んでみると、

以下引用内容

すべての i,ji,j の組を試すと計算量が O(N2)O(N2) になるので、TLEになります。

ん？　O(N2)O(N2)とはなんぞや？

ということで、教えてgoogle先生！！

[初心者向け] プログラムの計算量を求める方法 - Qiita

上記の記事によると、、

計算量は一般に、OO記法（オー記法、もしくはビッグオー記法と呼ぶ）を使って表します。OO記法では計算量を、O(n)O(n) や O(n2)O(n2) のような形で記述します。

「入力サイズ nn が増加するにつれて、実行時間が n2n2 に比例して増加する」ということを表しています。

ふむふむ。要するに二次関数的に増えるということっぽい。

今まで、「とりまfor文でいいべ」

と思っていたのが、だめだった・・

前回もTLEにやられたので、やっぱり計算量とか探索方法をちゃんと考えてから、コードを書いていきたいと思います！