金魚亭日常

読書,ガジェット,競技プログラミング

AtCoder Chokudai Speed Run #001

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 が使える.

f:id:what_alnk:20170730140441p:plain

L辞書順で何番目?

N回交換してソートできるか.

なので,J 問題と同じくバブルソートの交換回数を求めて,Nと比較する.

これ,Nの方が多い場合,同じやつの交換を繰り返せばいいので,差が偶数かどうかで判定できることはわかるけど,Nの方が少ない場合はこれでいいのだろうか,と思った.

AtCoder Chokudai Speed Run #001