解くに至った問題(7問)
ABC:009B/010B/057C/061C/096D
ARC:059D/084C
ARC084C
3つのリストA,B,Cを所持し、1<=i<=Nに対し、Aの中からBのi番目の要素より小さいもの、Cの中からBのi番目の要素より大きいものの個数をそれぞれ求め、掛け合わせた後でその合計を求めていくという方針
問題を眺めれば方針は立つものの、実装するときに1つのBの要素に対しA,Cの要素N個を見ていたらN^2の計算量になりTLE そこで、今回は二分探索を使う
Python3では二分探索のライブラリが存在する
import bisectを一行目に書いてから使う
bisectには、bisect_leftとbisect_rightが存在する。どちらも、検索したい数字がソート済み(昇順)リストの中になければ、リストの中にその数字を入れると何番目に入るかを教えてくれる(インデックスを返す)が、1つ以上存在したときにその扱いが異なってくる
①bisect_left
これは「ある数字未満の数字がリストの中にいくつあるか」という認識でよい 数字が既存の値の左側に入る
A = [1,2,4,4,5,6]に対し、
k = bisect.bisect_left(A,3)とすれば、
k = 2 と返ってきます (A = [1,2,3,4,4,5,6]で、3が入るとしたらリストの2番目)
また、
k = bisect.bisect_left(A,4)とすれば、
k = 2 と返ってきます (A = [1,2,4,4,4,5,6]で、既存の4の左側に入る)
②bisect_right
これは「ある数字以下の数字がリストの中にいくつあるか」という認識でよい 数字が既存の値の右側に入る
A = [1,2,4,4,5,6]に対し、
k = bisect.bisect_right(A,3)とすれば、
k = 2 と返ってきます (A = [1,2,3,4,4,5,6]で、3が入るとしたらリストの2番目)
また、
k = bisect.bisect_right(A,4)とすれば、
k = 4 と返ってきます (A = [1,2,4,4,4,5,6]で、既存の4の左側に入る)
ちなみに、bisect.insort_left(A,n)とすれば、leftで行ったのと同じ手順で、nをリストAの中に入れてくれる もちろんbisect.insort_right(A,n)もある
ARC059D
アンバランスな文字列
文字列が与えられて、その部分列の中に同じアルファベットが部分列の長さの過半数を占めている部分を抜き出せという問題
ろくに考えもせず解答を見たところ、XXもしくはXYXという部分列が存在しなければアンバランスな文字列は存在しないとのこと
それはそう
過半数を占めればよいので長さ2のうちの2もしくは3のうちの2を同じ文字が占めているところがあればそこを抜けばよいし、なければ無いと返せばよい
別にめちゃんこ長い部分を抜き出す必要はないのでこの程度で十分 もっと頭を使おうね
解けなかった問題
Tenka 1 Programmer Beginner Contest2018:C
ABC:079C
天下一C
数列で、隣り合う数の絶対値の合計を最大化する問題 リストで保持した値をソートし、例えば要素が5個であれば
p1 <= p2 >= p3 <= p4 >= p5
とするのか
p1 >= p2 <= p3 >= p4 <= p5
とするのかを二通り確かめる
さらに、プラスは下の場合、p1+2*p3+p5となるので、p3にはリストで最もでかいのを持ってくるべき
などの工夫を使って解く問題 こんがらがって一生できなかったので次の機会に
ABC079C
与えられた文字列の千の位、百の位、十の位、一の位の数字に対し、足し算もしくは引き算をした後で、答えが7になるような数式を出力しろという問題
cal = N[0]+op1+N[1]+op2+N[2]+op3+N[3]
と置くと(opnは演算子)これはあくまで文字列である
ここで、eval()を使うと、eval()は文字列を計算してくれる つまり
return(eval('1'))
は数字の1が返ってくるし、
return(eval('1+2'))
は数字の3が返ってくる
ここでは、
if eval(cal) == 7:
print(cal+'=7')
とすることで、calという文字列を計算してくれる
(cal+'=7'とすることに注意 calと=7は文字列なので接続する必要がある)
printではN[0]などに値が入る
また、
for i in range(N):
for j in range(N):
みたいな、for文が連なっている時には、breakで抜けようとすると、for文の数だけbreakを書かないといけなくなる
exit()を使うことで、この手間を省き、一番内側のループをexit()で抜ければすべてのfor文のループを抜けることができる