質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.35%
Python 3.x

Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。

Python

Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。

Q&A

解決済

1回答

780閲覧

python3の時間短縮の方法

subskull

総合スコア13

Python 3.x

Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。

Python

Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。

0グッド

0クリップ

投稿2020/04/20 00:44

編集2020/04/20 01:32

N人の社員からなる会社があり、各社員には 1…N の社員番号が割り当てられています。
社員番号 1 の社員以外の全ての社員には、自分より社員番号が小さい直属の上司がちょうど 1 人います。

Xさんが Yさんの直属の上司であるとき、Y さんは X さんの直属の部下であるといいます。
社員番号 iの社員の直属の上司の社員番号が Aiであることが与えられます。各社員について直属の部下が何人いるか求めてください。

python3

1 2N=input() 3A=input().split() 4Al=list(A) 5a=0 6for a in range(int(N)): 7 a=a+1 8 b=(Al.count(str(a))) 9 if b>0: 10 print(b) 11 else: 12 print(0) 13

Atcoderの上記のような問い(https://atcoder.jp/contests/abc163/tasks/abc163_c)で上記のようなコードを書いたのですが、実行時間超過してしまいました。どこをどう言った風に変えると時間短縮が可能ですか。

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答1

0

ベストアンサー

list.countは要素を先頭から逐次探索するので、O(n)です。
for文内にそれを埋め込むと、全体ではO(n^2)になります。

辞書を用意して Ai を集計していけば良いでしょう。
集計はO(n)で、求解はそれぞれがO(1)なので全体ではやはりO(n)で実行できます。

コードの貼り方について

teratailには、コードを見やすく表示する機能があります。
質問編集画面を開き、コードを選択した状態で<code>ボタンを押して下さい。
Python

特にPythonの場合、インデントが崩れるとコードの意味が変わってしまいます。


また問題を引用するのであれば、引用元のリンクを貼るようにして下さい。

投稿2020/04/20 00:49

編集2020/04/20 00:51
LouiS0616

総合スコア35668

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.35%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問