AtCoder の新しいウェブサイトのテストとして開催されたコンテスト.
12問 速解き.
A 最大値
数列の最大値を出力
max()
B 和
数列の和を出力
sum()
C カンマ区切り
数列をカンマ区切りで出力
join()
D ソート
数列をソートして半角スペース区切りで出力
sort()
, join()
E 1は何番目?
index()
F 見える数
「数列 a に含まれる整数のうち、1≤j<i≤N を満たす任意の j において、 aj<ai を満たすような i がいくつあるか出力しなさい。」という問題.
0番目は必ず条件を満たすので,まず一つ.
あとは,数列を1からn-1まで順番に見ていって,自分より左の最大値より大きいかを判定する.
G あまり
読み込んだ数列を連結した数値を 1,000,000,007 で割る.
H LIS
数列から好きなだけ要素を取り除いて単調増加数列を作る時の,最大の長さを求める.
二分探索する.
I 和がNの区間
連続区間の和がNになるものの数.
左から順番に和を求めて行って,和がNを超えたら次に行く.
J 転倒数
バブルソートの交換回数.
転倒数,と来たら,BinaryIndexedTree (BIT) , とアリ本にも書いてあるのだけど,このスライドがわかりやすかった.
www.slideshare.net
K 辞書順で何番目?
こういう操作で数えられるが,よく見ると BIT が使える.
L辞書順で何番目?
N回交換してソートできるか.
なので,J 問題と同じくバブルソートの交換回数を求めて,Nと比較する.
これ,Nの方が多い場合,同じやつの交換を繰り返せばいいので,差が偶数かどうかで判定できることはわかるけど,Nの方が少ない場合はこれでいいのだろうか,と思った.