kb84tkhrのブログ

何を書こうか考え中です あ、あと組織とは関係ないってやつです 個人的なやつ

ALDS1_7_A: Rooted Trees

難しいと感じたら今は飛ばして、実力をつけてから挑戦してみましょう。

ではお言葉に甘えて
でもこの本でこの先にこの問題が解けるようななにかが出てくるのかなあ?

で ALDS1_7_A: Rooted Trees

ふむ
木を作るだけでよさそうだ

でもサンプルデータを見てみるとなんか違和感がある
なんだろう

続きを読む

ALDS1_6_D: Minimum Cost Sort (続きの続き)

総当たりくらいしか思いつかないので総当たりを書いてみた

コストがそれまでの最小コストを上回るか、ソートが成功するまで
あらゆる手を試します
最初の最小コストはそこそこの値をセットしておかないと大変なことになるので
昨日のアルゴリズムで算出した値を使う

続きを読む

ALDS1_6_D: Minimum Cost Sort

ALDS1_5_Dが思考★★★、実装★★☆だったのに対し、今度は思考★★★★☆、実装★★☆
思考の星が1個半多い
これはダメかもしれんね

荷物を重さの順にソートするんだけど、要素の交換のときに重さに応じた
コストがかかり、トータルのコストが最小になるようにソートするというもの

続きを読む

『人生は、運よりも実力よりも「勘違いさせる力」で決まっている』

ひとことで感想を言うと、身も蓋もない本、って感じ 

人生は、運よりも実力よりも「勘違いさせる力」で決まっている

人生は、運よりも実力よりも「勘違いさせる力」で決まっている

 

人間の心理にはいろんな不合理な点がある

続きを読む

ALDS1_5_D: The Number of Inversions (続きの続き)

やっぱり挿入ソートベースじゃダメなのか

じゃあマージソートクイックソートかバケツソートか

バケツソートは値が109あるからありそうにない
なにか別の値に置き換えるっていう技があるかもしれないけど

バブルソートや挿入ソートと見比べてみると、クイックソートのほうが
その場で入れ替えていく分似てるところがあるような気がする
違うのは、バブルソートや挿入ソートが隣同士で入れ替えているのに対し
クイックソートは離れた要素を入れ替えていること

離れた要素を入れ替えるときは要素間の距離を足せばいいかな?
swapで足せばすぐ試せる

・・・

ダメだった
離れた要素を入れ替えるときは、間に挟まれた要素も結果に影響を与えるのに
そこが考慮できてないし影響を判断するやり方も思いつかない

マージソートかなあ
あんまりできる気はしてないけど

そもそも何を数えればいいのやら
右と左が入れ替わる回数かなあ
違う
入れ替えの距離の合計かなあ
違う

このあたりはコンピュータ使わずひたすらノートに数字を並べたり
入れ替えたりしてるわけですが
対応する数字の間に線を引いていると何やら交点の数が気になってきました
交点の数と、反転数っておんなじなんじゃ?
うんおんなじ
これは考えてみると当然

ソート前の列とソート済みの列を並べて、対応する数字の間に線を引いて、
交点の数を調べれば反転数が求まる
問題は、交点の数を求める方法がわからないってことなわけだが

でもマージソートの各段階で交点の数を求めて、それを合計してやると
全体の反転数になるっぽい
なぜ合計でうまくいくのかはよくわからない

そして、交点の数は、右側の数を取り出すときに左側に残ってる数の数を
足していけばよさそうだってのもわかる

紙の上でいくつか試す
数学的じゃない帰納法によってうまくいきそうな気がしてきたので書いてみる
結局イテレータがじゃまになってきたので素のインデックスを使う
あとはinvという変数に交点の数を累積してるだけ

from math import inf

inv = 0

def merge(A, left, mid, right):
    global inv

    L = A[left:mid]
    L.append(inf)
    R = A[mid:right]
    R.append(inf)
    i = j = 0
    for k in range(left, right):
        if L[i] < R[j]:
            A[k] = L[i]
            i += 1
        else:
            inv += len(L) - 1 - i
            A[k] = R[j]
            j += 1

def merge_sort(A, left, right):
    if left + 1 < right:
        mid = (left + right) // 2
        merge_sort(A, left, mid)
        merge_sort(A, mid, right)
        merge(A, left, mid, right)

def main():
    n = int(input())
    A = [int(x) for x in input().split()]
    merge_sort(A, 0, n)
    print(inv)

main()

なんか合わない合わないと思ったらLとRに要素付け足してるの忘れてたりとか
あったけどAC
考え方は合ってたらしい

でも証明してくださいとか言われると困るなー
証明とはいかなくても感覚的にこれは合ってるというところまでも行ってないので
これで漏れなく重複なく数えられてるのかと言うと

このやり方で離れた要素の入れ替えを数えられるなら
クイックソートでも同じ作戦が使えないかな?

ダメか
間に挟まってる数が本来の入れ替えに含まれる場合と含まれない場合があるみたい
それをいちいちチェックするとやっぱりオーダが変わってしまいそう
という観点で見ると、マージソートだと間に挟まってる数が必ず入れ替えに
なる数になっている
というのはあるな
少し確からしさが増した

これくらいで解説を読もう
たぶんマージソートを使うところは合ってると思うので
あとは感覚的に納得できるかどうか

・・・

自分で考えたこと以上の説明はなかった
残念

まあでも解けたのでだいたいさっぱり
次いこ次