この記事は拙著「AtCoder 凡人が『緑』になるための精選50問詳細解説」のサンプルです
価格：100円
kindle：https://www.amazon.co.jp/dp/B09C3TPQYV
booth(pdf)：https://sano192.booth.pm/items/3179185
前：https://qiita.com/sano192/items/40fdf83cedacbc9d68a6
次：https://qiita.com/sano192/items/c908830ad0800afe139f
【目標】
・ソートを実装できるようになる
・ソートの計算量がO(NlogN)であることを覚える
【概要】
競技プログラミング必須のテクニック、ソート(並び替え)を使えるか問う問題。ソートが使えるだけで解ける問題の幅がぐっと広がるのでこの問題で身につけてしまおう。
【方針】
高さが高い順に並び替え、2つ目の山の名前を出力すれば終わり。
この問題を解くためには2つの知識が必要だ。
(1)二次元配列
山の名前、高さという2つの要素を一緒に受け取り、記録していかなければならない。
こういった場合は二次元配列を使うのが便利だ。
二次元配列はリストの中にリストを入れる方法。書き方は
リスト.appned(リスト)
以下のコードをコピペして実行してみよう。
mountains=[]
mountains.append([8849,"Everest"])
mountains.append([8611,"K2"])
mountains.append([8586,"Kangchenjunga"])
print(mountains)
「出力結果」
[[8849, 'Everest'], [8611, 'K2'], [8586, 'Kangchenjunga']]
mountainsというリストの中に更に[山の高さ,名前]というリストが入っているのがわかるだろう。
このようにリスト.appned(リスト)と書くことでリストの中にリストを入れることができる。
二次元配列から要素を取り出すときは以下のように書く。
print(mountains[0][0])
print(mountains[1][1])
print(mountains[1])
「出力結果」
8849
K2
[8611, 'K2']
mountains[0][0]
は
0番目のリスト(水色の0) の 0番目の要素(赤色の0)
つまり
8849
mountains[1][1]
は
1番目のリスト(水色の1) の 1番目の要素(赤色の1)
つまり
K2
mountains[1]
は
1番目のリスト(水色の1)
つまり
[8611, 'K2']
を意味する。
よりきっちりとした説明はAtCoder公式が解説を作っているので参照してほしい。ただしこのページの意味がきちんと理解できなくても問題は解ける。
二次元配列の作り方と、要素の取り出し方をわかっていれば十分だ。
https://atcoder.jp/contests/APG4b/tasks/APG4b_t
(2)リストのソート
ソートとは並び替えのこと。リスト内の要素を小さい順または大きい順に並び替えるテクニック。
書き方は
リスト.sort()
と書くだけ。
例として
A=[1,4,2,8,5,6,7,9]
というリストを作って並び替え、出力してみよう。
A=[1,4,2,8,5,6,7,9]
A.sort()
print(A)
「出力結果」
[1, 2, 4, 5, 6, 7, 8, 9]
このように小さい順に並び替えられていることがわかる。
大きい順にしたいときは
リスト.sort(reverse=True)
と書く。
二次元配列をソートした場合、先頭の要素に沿って並び替えられる。
例として
mountains=[[3193, 'Kita'], [3189, 'Aino'], [3776, 'Fuji'], [3190, 'Okuhotaka']]
というリストを大きい順にソートした場合は以下のようになる。
mountains.sort(reverse=True)
print(mountains)
「出力結果」
[[3776, 'Fuji'], [3193, 'Kita'], [3190, 'Okuhotaka'], [3189, 'Aino']]
「先頭の要素」=「山の高さ」が高い順に並び替えられていることがわかるだろう。
ソートの計算量はリストの要素数がNの場合、O(NlogN)となる。
Nが大きい場合や、何度もソートを行う場合はTLE(実行時間制限超過)することもあるので注意。
【実装】
入力を受け取る。まずはN。
N=int(input())
次に山の高さ、名前を格納するリストを作る。名前はmountains。
mountains=[]
ここからfor文で一行ずつS,Tの受け取りを行う。
Sは文字列、Tは整数となるが、まず文字列としてS,Tを受け取り、Tを整数=intに変換すればよい。
そして[山の高さ,名前]をmountainsに入れ、二次元配列を作る。
for i in range(N):
S,T=map(str, input().split())
T=int(T)
mountains.append([T,S])
格納ができたら山の高さが高い順に並び替える。
mountains.sort(reverse=True)
最後に2番目に高い山の名前を出力して終わり。
pythonのリストは0からインデックス番号が始まるから、2番目に高い山のインデックス番号は1になることに注意しよう。
print(mountains[1][1])
【コード全文】
N=int(input())
mountains=[]
for i in range(N):
S,T=map(str, input().split())
T=int(T)
mountains.append([T,S])
mountains.sort(reverse=True)
print(mountains[1][1])
この記事は拙著「AtCoder 凡人が『緑』になるための精選50問詳細解説」のサンプルです
価格：100円
kindle：https://www.amazon.co.jp/dp/B09C3TPQYV
booth(pdf)：https://sano192.booth.pm/items/3179185
前：https://qiita.com/sano192/items/40fdf83cedacbc9d68a6
次：https://qiita.com/sano192/items/c908830ad0800afe139f