電波ビーチ

☆(ゝω・)v

ABC 039を解いた

総括すると、酒のつまみって感じです(?)(実際酒飲みながら答えた)

A - 高橋直

直方体の高さ、幅、奥行きが与えられるからその表面積を答える。直方体の展開図書けば分かるように全6面はそれぞれ同じ矩形が2つずつ3種類からなる。表面積はその合計なので与えられた各辺の情報から計算する。

a, b, c = gets.chomp.split.map(&:to_i)
puts (a*b*2+a*c*2+b*c*2)

B - エージェント高橋君

整数Xが与えられる。N=X4である。実数Nを答える。題意からNはXの4乗根のうち実数になるやつなので(というか複素数なんて組み込みで対応してる言語じゃない限りめんどくさすぎるわ)、適当にsqrtを二回やってやればいい。だいたいの言語にはsqrtくらい付いてる(と思う多分)はずだが、わかんなかったら1/2乗してやれば平方根が出るよ。1/4乗してやれば一発。さすがに冪乗計算できない言語は....いや知らんけど

sqrtするバージョン

x = gets.chomp.to_i
puts Math.sqrt(Math.sqrt(x).to_i).to_i

1/4乗するバージョン

x = gets.chomp.to_i
puts (x**(1/4.to_f)).to_i

C - ピアニスト高橋君

WBからなる20文字の文字列Sが与えられ、これはWはピアノの白鍵、Bは黒鍵に対応する(左側からの)並びである。Sの先頭Siを白鍵とする。Siのドレミ音階によって答えを分岐して出力する。

答えはドレミ音階の7種類ある。ドから始まる基本の鍵盤の並びはWBWBWWBWBWBWなのでそれがSのどこにあるかで分かる。めんどくさいので鍵盤の並びはループ構造をもつことを利用して、先頭からの12文字がどの状態かで分岐することにした。

s = gets.chomp
doremi = "WBWBWWBWBWBW".chars
case s[0, doremi.size].chars
when doremi
  puts "Do"
when doremi.rotate!(2)
  puts "Re"
when doremi.rotate!(2)
  puts "Mi"
when doremi.rotate!(1)
  puts "Fa"
when doremi.rotate!(2)
  puts "So"
when doremi.rotate!(2)
  puts "La"
when doremi.rotate!(2)
  puts "Si"
end

今でこそ世界にはばたくatcoderですが、この頃はまだドレミ唱法などというマイナー音名表記を使っていたため日本人にしか解けない問題ですね、知らんけど

D - 画像処理高橋君

#の周囲8マスに.があれば#に変える処理」を1回施した、高さH幅Wのテーブルが与えられる。処理を施したもとのテーブルが存在するならばそれを出力する。与えられるのは処理後なのでそれを元に戻してみて、処理を与えたら復元できるかどうかを試す。

処理前に戻すには逆の処理を施す。すなわち処理後の.の周囲を.に変える。変えたものについて#の周囲を#に変えたものが与えられたテーブルと等しくなれば復元可能。

出力用のテーブルと復元用のテーブルを作って処理していく。周囲8マスの処理については迷路探索的な感じでやった。他の提出をみると外側に壁を用意しているものが多かった

# 潰してから復元する方針

h, w = gets.chomp.split.map(&:to_i)
table = []
h.times do
  table << gets.chomp.chars
end

def repaint(map, i, j, mark)
  # map[i][j]とその周囲8マスをmarkに塗り替える
  place = [-1, 0, 1]
  place.each do |y|
    place.each do |x|
      if 0<=i+y && i+y<map.size && 0<=j+x && j+x<map[0].size
        map[i+y][j+x] = mark
      end
    end
  end
end

# tableの「#」を潰す用
pre_table = Array.new(h).map{Array.new(w, "")}
# pre_tableから処理した結果を復元する用
epi_table = Array.new(h).map{Array.new(w, ".")}

(0...h).each do |i|
  (0...w).each do |j|
    if table[i][j] == "."
      # 処理前は"."の周囲は"."であったはず
      repaint(pre_table, i, j, ".")
    end
  end
end

(0...h).each do |i|
  (0...w).each do |j|
    if pre_table[i][j] == ""
      # pre_tableにとって"."で潰せなかった場所から"#"が広まるはず
      pre_table[i][j] = "#"
      # epi_tableはpre_tableの処理後の姿
      repaint(epi_table, i, j, "#")
    end
  end
end

if epi_table == table
  puts "possible"
  pre_table.each do |pt|
    puts pt.join("")
  end
else
  puts "impossible"
end

まとめ

簡単なやつを選んだので簡単だった。そのくせDでは実装をミスってWAを食らった...

ABC 028を解いた

tomerun.github.io

これにあるやつで難易度低そうなABCの問題セットから解いていくシリーズ。界隈ではABC042以降を解けという声がありますが果敢に無視します

A - テスト評価

数値が与えられるので値で分岐して答える

n = gets.to_i
if n<=59
  puts "Bad"
elsif n<=89
  puts "Good"
elsif n<=99
  puts "Great"
else
  puts "Perfect"
end

B - 文字数カウント

文字列が与えられるからどの文字が何回出現したかを出力する。文字列はA~Fで固定なので適当に辞書でも作って数えてやる。rubyだと範囲オブジェクトがアルファベットにも対応しててクソ楽だったけどどうせFまでの6つなので手でやっても変わらん

alphabet = ("A".."F").to_a.zip(Array.new(("A".."F").to_a.size, 0)).to_h
gets.chomp.chars.each{|c| alphabet[c]+=1}
puts alphabet.values.map(&:to_s).join(' ')

C - 数を3つ選ぶマン

それぞれ1以上100以下の異なる数値が5つ与えられるから適当に3つ取った和の3番目に大きい数値を答える。....単純に考えればpermutation,あるいはそんな組み込みライブラリがなくても、それぞれせいぜい100までなので3重for文で全探索しても充分間に合う。

# 全探索する
arr = gets.chomp.split.map(&:to_i)
results = []
arr.size.times do |i|
  for j in (i+1...arr.size) do
    for k in (j+1...arr.size) do
      results << arr[i] + arr[j] + arr[k]
    end
  end
end
results = results.uniq.sort
puts results[-3]

だが、O(1)で分かる方法があり、それが解説として載っていたが、atcoderの解説は解説を読んで分かることは極稀なのでとうぜんこれもわからん。なんかしらんけど通る例はこちら。納得のいく&&理解できる解説がほしい。

# 原理がまったくわからん例
arr = gets.chomp.split.map(&:to_i).reverse
puts [arr[0]+arr[1]+arr[-1], arr[0]+arr[2]+arr[3]].max

D - 乱数生成

0~106まで取り得る整数Nと、N以下の整数Kが与えられるから、Nまでの数値を(重複を許して)3つ取ったときにそれらの中央値がKになるときの確率を答える。総数ではない。

クソ丁寧に解説すると以下のようになる。この問題は(「atcoderの解説は解説を読んで分かることは極稀」としながら)珍しく中学生程度だったら解けなくても読んだら分かるって感じの解説が載っているので、以下は読んでもわからなかったキッズ向け。

中央値ってのはなんか習った気がするが完全に忘れてたのでググると、ソート済の数列の真ん中にくる値のことである。題意では3つ取ったとあるので、その3つの値をソートしたときの配列を[a, b, c](1<=a<=b<=c<=N)とする。

この配列の中央値がKということは、取った順番を無視して、取った値だけソートすると[a, K, b]になればいいということである。まごうかたなく、真ん中の値はKになっているので。

a!=K かつ b!=Kとすると、K以外の残りのa, bの選び方の組み合わせの総数がKがひとつだけ出たときの数である。a<K かつ K<b、すなわちKが一回しか登場しない場合は、aの取り得る値はa<Kと1<=aより、K-1であり、bの取り得る値はK<bとb<=Nより、N-K個である。そして3回の試行中、取り方は、[a, K, b], [a, b, K], [b, a, K], [b, K, a], [K, a, b], [K, b, a]の6通りある。

a==Kかつb!=K または a!=Kかつb==Kとすると、Kは二回取る。3回のうち2回がKなので題意を満たすには残り1枠は(Kは二回までなので、)Kを除くどんな数字でもいいので、残る数値をxとすると、[x,K, K], [K, x, K], [K, K, x]の3通りある。xはNまでのうちKを除く値なのでこれはN-1個の候補がある。

a==Kかつb==Kとすると、K を三回取ることを意味し、これはすべてのうちで1種類しかない。自明だが[K, K, K]の並べ方は1通りであるからだ。

以上で中央値がKになる組み合わせの総数が求まる。求めるのはその確率なので、全事象の数で割る。全事象ってのは当然、試行が独立した、取り得る値がN種類である操作、を、3回繰り返す、ってことである。


というのを落ち着いて数学脳で見ればなんとなく分かる。というか逆に愚直解ってどうするんだ...?

n, k = gets.chomp.split.map(&:to_i)
puts ((n-k)*(k-1)*6+(n-1)*3+1)/(n*n*n).to_f

ABC 030を解いた

ウデマエがクソなので日々の鍛錬として。

A 勝率計算

試合数と勝利数が2チーム分与えられるからそれぞれの勝率を比較しその結果によって出力を分岐する。勝率は当然勝利数 / 試合数で求まるのでそのまま計算する。intではなくfloatとして数値計算する。

a, b, c, d = gets.chomp.split.map(&:to_f)
if b/a < d/c
  puts "AOKI"
elsif d/c < b/a
  puts "TAKAHASHI"
else
  puts "DRAW"
end

B 時計盤

アナログ時計n時m分としてn, mが与えられるからnとmのなす角のうち小さいほうを求める問題。三角関数以前。長針は60分で360度回るので1分だと6度、短針は12時間=720分で360度回るので1分だと0.5度進む。1時間だと30度。これを利用して計算する。短針と長針のなす角度のうち小さい方を読み飛ばしていて、というか考慮することすら頭になくてWAを食らったがみんなは真似しちゃだめだぞ

n, m = gets.chomp.split.map(&:to_f)
n = (n%12)*30+(m*0.5)
m = m*6
puts [(m-n).abs, 360-(m-n).abs].min

C 飛行機乗り

ABC030で最も難しい(個人の感想)。普通に解説読んだ。次に乗れる便を探すのに二分探索を使う(N5、M5とかででかいので愚直にやると間に合わない)。よくある最大値のうちの最小値を読み替えたxを越える最初の数ではなくx『以上』となる最初の数を求めるようにカスタマイズする。あと『往復の回数』である点に注意してカウントする

n, m = gets.chomp.split.map(&:to_i)
x, y = gets.chomp.split.map(&:to_i)
a_lis = gets.chomp.split.map(&:to_i)
b_lis = gets.chomp.split.map(&:to_i)
ans = 0
now = 0
def lower_bound(arr, x)
  # arrのうちx以上となる最小の値
  l, r = -1, arr.size
  loop do
    mid = (r + l)/2
    return mid if r - l < 1
    if x <= arr[mid]  # ここで大なりイコールしているので、x以上、が保たれる
      r = mid
    else
      l = mid + 1
    end
  end
end
 
loop do
  # aからbに向かうことにする
  lb = lower_bound(a_lis, now)
  if lb == -1 # n - 1の場合 泥臭い
    lb = 0
  end
  break if lb >= n
  now = x + a_lis[lb]
  # bからaに向かうことにする
  lb = lower_bound(b_lis, now)
  if lb == -1
    lb = 0
  end
  break if lb >= m
  now = y + b_lis[lb]
  ans += 1
end
 
puts ans

D へんてこ辞書

小学生向けの問題でアルゴリズムとか知らなくても剰余がわかっていれば解ける(戒め)。少なくともCよりは簡単だと思う。試行回数Kに対して配列の数Nが圧倒的に小さいのと、1≦bi≦Nの制約により、K(≦N)回の試行中に必ず既に一度参照済みの数値に向かう機会がある。一度参照した数値からはまた同じように参照済みの数値へと向かうことになり、これは無限に循環する。これを利用して、循環する配列を抽出して、その時点での残り試行回数を配列の長さで割った余りを求めてやる。循環する配列は、とりあえず最初から数値を積んでいき、既に存在する数値を確認したらそれ以前の要素は省くことで抽出した。

n, a = gets.chomp.split.map(&:to_i)
k = gets.to_i
arr = gets.chomp.split.map(&:to_i)
# 循環に入ったらそこまでの回数を引いたものを循環の長さで割って余りを求め、循環の配列から値を求める
cnt = 0
circular = []
while k > cnt
  cnt += 1
  if circular.include?(a)
    circular = circular[circular.index(a)..-1]
    idx = (k-cnt) % circular.size
    a = arr[circular[idx]-1]
    break
  else
    circular << a
  end
  a = arr[a-1]
end
puts a

重みつきUnion-Find木を解説

これを解こうとしてできなかったのでまとめた。

judge.u-aizu.ac.jp

重み付きUnion-Find

英語名はよくわかんなくてweighted union-find とか weighted union heuristic、weighted disjoint set dataみたいに言われてるっぽい。Union-Find木に「あるノードから別のノードへのコスト」を加えたもの。Union-Find木自体の説明についてはAtcoderのTypical ContestかAOJのDSLに基本問題と解説があるのでチェケラ

atc001.contest.atcoder.jp

judge.u-aizu.ac.jp

ググった

ありがとうございます。

qiita.com

at274.hatenablog.com

喜び勇んで読んだが、いまいちなにをやっているのかわからんので整理する。

経路圧縮

f:id:or3:20190110004529j:plain - 木の葉を直接根にくっつけちまえ、という発想。これにより再帰的に遡ると最悪O(n)だったのがO(logn)となる(計算の理屈は知らん)。 - よくみかける「根を遡る処理の過程で親を根に直接つなぎかえる」メソッドだと、そのメソッドが呼ばれたあとに併合すると高さが増える。よくみかける実装だとその次のクエリでメソッドを呼ぶ際につなぎかえる

ランク付け

f:id:or3:20190110004804j:plain

  • 根に木の高さの情報をもたせておく。「各ノード」じゃなくて根のノードだけにもたせるのは木の根同士だけを比較すれば充分だから、と思っている。実装が楽だし
  • 併合の際に低いほうの根の親を木の高いほうの根にすることで、計算の前後で木の高さを保つことができる
    • 木の高さが低いとその分再帰が浅くなるので計算が早くなる
  • これもO(logn)らしいが計算方法など知る由もない

この二つはUnion-Findの高速化としていろいろな場所で書かれているが、なぜか重み付きUnon-Findはこれらのテクニックを二つとも使った実装しか見当たらない。どうせ「Union-Findくらいみんなライブラリにもってて当然のように圧縮もランク付けも実装してるんだろうし、それらを流用するのが前提で説明してやんよ」ということなのだろう。余計なお世話だ。

重み

さきほどggった資料のうちqiitaのほうにこのような記述がある。

最初の

w += weight(x); w -= weight(y);

と補正するところが少しわかりにくいかもしれません。merge(x, y) 操作では、元々の x と y との間に辺を繋ぐのではなく、root(x) と root(y) の間をつなぐので、つなぐべき辺の重みは w ではなく修正が必要になります。

これを105回くらい読んでも式の意味がわからなかったので書いた。

まず、各ノードにもたせるコスト(重さ)とはなんなのか。これはノードと、そのノードと直上の親とのコストの差分である。

f:id:or3:20190108221254j:plain

併合のクエリx y wとは、ノードxからノードyへのコストがwということである。 f:id:or3:20190108222336j:plain したがって上図で5から4までのコストは、通るパスの重さをすべて足し合わせたもので、6+3 = 9ということになる。

xからyへのコストがwということは、逆を言えばyからxへのコストが-wということなので、 f:id:or3:20190108223153j:plain したがって、たとえばx=8, y=5のコストを求めると、

8から4のノードのコスト  + 4から2のノードのコスト + 2から5のノードのコスト
= (-3) + (-3) + (-6)
= -12

になる。

よくある実装ではこれを併合のときに計算していて、異なる木に属する2つのノードどうしを結ぶとき、

w = (xからxの根までのコスト) + (xの根からyの根までのコスト) + (yの根からyまでのコスト)

とやっている。図で示すとこんな感じ f:id:or3:20190108225754j:plain

求めるのは新しくエッジを貼った「xの根からyの根までのコスト」なので、先程の式は

(xの根からyの根までのコスト) = w - (xからxの根までのコスト + yの根からyまでのコスト)

であり、

yの根からyへのコスト = - (yからyの根へのコスト)

なので、結局

(xの根からyの根までのコスト) = w - (xからxの根までのコスト - yからyの根までのコスト)

というわけ。ランク付けを使うと高さの低い木の根から高い木の根にエッジを貼るので、

木xのほうが低い場合:
x -> xの根 -> xの根からyの根 -> yの根からy
木yのほうが低い場合:
y -> yの根 -> yの根からxの根 -> xの根からx

となり、後者の累積和は単純に前者の符号を反転したものになる。なのでランクの大小の比較でそれを判定しているわけ。


これで骨子は分かったと思うので適当に実装していけばいいです。

高速化なしの実装

提出先はAOJのDSL。通らないのは知っててやる。世のサンプルコードすべてが正しくAC通るものと思うなよ(自戒)。「私はわざとジャッジサーバを無駄に回しました」という札を首から下げながら提出。

import sys
sys.setrecursionlimit(10**9)

class WeightedUnionFindTree:
  def __init__(self, n):
    self.par = list(range(n))
    self.weight = [0 for _ in range(n)]
  
  def root(self, t):
    if t == self.par[t]:
      return t
    # 根を遡るので自分の親を返す
    return self.root(self.par[t])
  
  def rec_weight(self, t):
    # 根までの重さの累積和
    if t == self.par[t]:
      return 0
    return self.weight[t] + self.rec_weight(self.par[t])
  
  def same(self, x, y):
    return self.root(x) == self.root(y)
    
  def unite(self, x, y, w):
    rootx = self.root(x)
    rooty = self.root(y)
    if rootx != rooty:
      self.weight[rootx] += w - self.rec_weight(x)
      self.par[rootx] = y

  def diff(self, x, y):
    if self.same(x, y):
      # xからxの根への重さ - (yからyの根への重さ)
      return self.rec_weight(x) - self.rec_weight(y)
    else:
      return "?"
      
n, q = list(map(int, input().split()))
wuft = WeightedUnionFindTree(n)
for _ in range(q):
  query = list(map(int, input().split()))
  if query[0] == 0:
    x, y, w = query[1], query[2], query[3]
    wuft.unite(x, y, w)
  elif query[0] == 1:
    x, y = query[1], query[2]
    print(wuft.diff(x, y))
    

でこれが当然のようにTLEとなる。ので、高速化テクニックのいずれかを実装する。世のサンプルが両方とも使っているのしか見つからなかったことはさきほど述べたが、天の邪鬼なのとちゃんと動くのかのテストもかねて、経路圧縮だけを実装する。

重みつきUnion-Find(path compression)

root()と、併合処理の場合分けをしただけ。

import sys
sys.setrecursionlimit(10**9)
"""
重み付きで経路圧縮
ランクでの比較は考えず、圧縮だけする
"""
class WeightedUnionFindTree:
  def __init__(self, n):
    self.par = list(range(n))
    self.weight = [0 for _ in range(n)]
  
  def root(self, t):
    if t == self.par[t]:
      return t
    # 経路圧縮してみる
    r = self.root(self.par[t])
    self.weight[t] += self.weight[self.par[t]]
    self.par[t] = r
    return r
  
  def rec_weight(self, t):
    if t == self.par[t]:
      return 0
    return self.weight[t] + self.rec_weight(self.par[t])
  
  def same(self, x, y):
    return self.root(x) == self.root(y)
    
  def unite(self, x, y, w):
    rootx = self.root(x)
    rooty = self.root(y)
    if rootx != rooty:
      if y != rooty:
        # 直接yにつなげる
        self.weight[rootx] = w - self.rec_weight(x)
      else:
        # 根につなげる
        self.weight[rootx] = w - (self.weight[x] - self.weight[y])
      self.par[rootx] = y

  def diff(self, x, y):
    if self.same(x, y):
      # xからxの根への重さ - (yからyの根への重さ)
      return self.rec_weight(x) - self.rec_weight(y)
    else:
      return "?"
      
n, q = list(map(int, input().split()))
wuft = WeightedUnionFindTree(n)
for _ in range(q):
  query = list(map(int, input().split()))
  if query[0] == 0:
    x, y, w = query[1], query[2], query[3]
    wuft.unite(x, y, w)
  elif query[0] == 1:
    x, y = query[1], query[2]
    print(wuft.diff(x, y))
    

併合するときにyが葉かどうかで処理を分けているのは、葉だと

w = xからxの根までのコスト + xの根からyの根までのコスト
xの根からyの根までのコスト =  w - xからxの根までのコスト

でyの木のコストを考えずにつなげればいいだけなので。葉以外だと↑で既にあげている感じでいい。

例題 ABC087 D - People on a Line

ということでqiitaのほうの参考でも挙げられていたこれをやる。めんどくさいのでクラスで管理はせず、配列だけでやった。

n, m = list(map(int, input().split()))
par = list(range(n+1))
dis = [0] * (n+1)

def root(x):
  if x == par[x]:
    return x
  r = root(par[x])
  dis[x] += dis[par[x]]
  par[x] = r
  return r

def cost(x):
  # xからxの根までのコスト
  if x == par[x]:
    return 0
  return dis[x] + cost(par[x])

for _ in range(m):
  l, r, d = list(map(int, input().split()))
  # 根が違ってればマージ
  # 同じなら入力されたdistanceがこれまでの入力データからなる
  # 現在の木の構造から計算した数値とあっているか判断
  rootl, rootr = root(l), root(r)
  if rootl != rootr:
    if r != rootr:
      # 直接yにつなげる
      dis[rootl] = d - cost(l)
    else:
      # 根につなげる
      dis[rootl] = d - (cost(l) - cost(r))  # d - (dis[l] - dis[r])
    # ここで親を更新
    par[rootl] = r
  else:
    if d != cost(l) - cost(r):
      print("No")
      exit()

print("Yes")

はい。よくできました。

macで画面キャプチャするときメインディスプレイ以外を撮りたい人のためのAppleScript・Automater

tumblrtwitterで洋画字幕のおもしろキャプチャとか流れてくるのが面白いので真似っこしてストックしている。PC・macで動画を見るときは21インチモニタにつないで観ているのだが、ここぞという場面で画面を止めて⌘+shift+3するとすべてのスクリーンでキャプチャされる。

f:id:or3:20181229171248p:plain
さすがに恥ずかしいので劣化させた
デフォルトだとデスクトップに溜まっていくが、当然メイン(mac本体側)のディスプレイのキャプチャは不必要なのでちまちま消すことになる。⌘+shift+4だとウインドウを選択するのが面倒だ。 タブレットで観るとNetflix on iOSではキャプチャ対応されててクソ。プライムビデオもDLしたものじゃないと撮れなくてクソ

f:id:or3:20181229140039p:plain
google photosにアルバム作って放り込んでいる
そういえばmacにはAppleScriptとかいうのがあってmac上の操作をスクリプト制御できると聞いたことがあるので初めて触ってみた。

スクリプト

ドキュメントすら読んでないしチュートリアルも触ってない、ただのコピペマンです。なので特に説明するべき知識もないのでそのまま書いちゃう。ご覧の通りひどい有様ですが動けばいいんだよ動けば

github.com

Automator

完全に知識がなくて、AppleScriptで完結すると思ったら違くて、ショートカットキーに割り当てるにはAutomaterを使うのが常套手段らしい。これも初めて触る(そもそもmacで日常的なルーチン作業なんて無いし知らんかった)が2,3ググりくらいでなんとかした

Automaterを起動してライブラリ -> AppleScriptを実行 で上記のスクリプトをコピペする。てっきりapplescriptファイルを指定するのかと思ったらふつうにエディタに書き込むタイプだった。管理できなくね?f:id:or3:20181229135257p:plain 適当に名前を決めて保存。

ショートカットキー割当

ふだんまったくキーバインドをいじらないのでこれも初めてだった。システム環境設定 -> キーボード -> ショートカットから↑で保存したAutomaterがあるはずなので選択する。画像の一番下のScreenShotSubmonitorとかいうやつです。そんで適当に(ユニークな)ショートカットキーをつけておく。なんとなくうまくいっていればうまくいく f:id:or3:20181229140342p:plain

よかったね〜〜

以下はただのメモです。おつかれさまでした。良いお年を。

screencaptureコマンド

terminalからscreencaptureコマンドでスクショできる。これに-R<x,y,w,h>オプションで(x, y)を原点として幅w高さhの矩形範囲をキャプチャできるらしいのでやってみたが、認識されているディスプレイの解像度が異なっているとうまく動作しないのか計算方法が違っているのか、ピンポイントでサブモニタだけを撮るのがめんどくさかった。なので仕方なくすべてのディスプレイをキャプチャしてメインディスプレイだけあとで消す、という回りくどいことをしている。試してないけど↑のスクリプトだとメイン除いて4画面までは撮れると思う

"亡霊を残さないために数秒待つ"

とかスクリプト内で書いてますがまあ単に実ファイルは削除したけど参照が残ってるみたいな感じで消そうとするとこういうメッセージが f:id:or3:20181229141545p:plain 出るってやつ。screencaptureコマンドしたあとすぐにゴミ箱ポイーするとこうなるのでちょっとだけディレイかませただけです。亡霊ってなんだよ(正式名称知らない)

Automaterでほかのやり方

なんかAutomaterにはシェルスクリプトも実行できるぽいのでふつうにそれでもイケたと思われる。シェルスクリプトからpythonなりを呼び出してもいい。めんどくさいので別解は書かない(書けない) あとappも起動したりできるし、AppleScriptはapp書き出しができる(って初めて知ったんですがめちゃくちゃ便利じゃん)のでそれでもいい(かもしれない。試してない)

AOJ ALDS1_6_C Quick Sort

ソートアルゴリズムの実装自体やったことないぜ!!!!!!!!!メリークリスマスイヴ!!!!!!!!!

n 枚のカードの列を整列します。1枚のカードは絵柄(S, H, C, またはD)と数字のペアで構成されています。これらを以下の疑似コードに基づくクイックソートで数字に関して昇順に整列するプログラムを作成してください。partition は ALDS1_6_B の疑似コードに基づくものとします。

また、与えられた入力に対して安定な出力を行っているかを報告してください。ここでは、同じ数字を持つカードが複数ある場合、それらが入力で与えられた順序であらわれる出力を「安定な出力」とします。

安定な出力かどうか とは

クイックソートは与えられた配列の要素同士を交換するので安定でない配列ということらしい。安定な出力をするソートにはマージソートがある。

クイックソートマージソートを実装してそれぞれに配列を投げて得られた結果が同じならば安定、異なれば非安定ということにする。

マージソート

分割統治してソートする感じ。半分ずつに分割する部分とそれを統合(merge)する部分がある

  • 半分ずつに分ける
  • 分けたうちの左側と右側を比較
    • 先頭から比較していって小さい方を選択
  • 比較してできた結果からさらに大きい単位で比較

ソート済のLとRをみたときにそれぞれ上の処理をやるとできた結果Aは全体でソートされている。これを小さい単位(2数の比較)から大きくしていく感じ

def merge(a, l, m, r)
  l_arr = a[l, m-l] << 10000000000000000000
  l_i = 0
  r_arr = a[m, r-m] << 10000000000000000000
  r_i = 0

  (l...r).each do |idx|
    # 小さい方から入れていく
    if l_arr[l_i] <= r_arr[r_i]
      a[idx] = l_arr[l_i]
      l_i+=1
    else
      a[idx] = r_arr[r_i]
      r_i+=1
    end
  end
end

def merge_sort(a, left, right)
  if 1 < right-left
    mid = (right+left)/2
    merge_sort(a, left, mid)
    merge_sort(a, mid, right)
    merge(a, left, mid, right)
  end
end

これのmergeメソッドのとこが統合に当たる。あるいは配列ごと作ってぶちこむ手もある。LLならこっちのが簡単そう*1。どっちもやってるこたぁおんなじ

def merge(left, right)
  ret = []
  loop do
    break if left.size.zero? && right.size.zero?
    # 先頭の小さい方から入れていく
    if left.empty? || (!right.empty? && right.first <= left.first)
      ret << right.shift
    elsif right.empty? || (!left.empty? && left.first < right.first)
      ret << left.shift
    else
      p "fuck"
      exit
    end
  end 
  ret
end

def merge_sort(a)
  return a if a.size == 1
  mid = a.size/2
  left = a[0, mid]
  right = a[mid, mid+1]
  left = merge_sort(left)
  right = merge_sort(right)
  return merge(left, right)
end

クイックソート

これも分割統治。配列から適当なpivotを決めて、pivotより左側に「pivotより小さい要素」、右側に「pivotより大きい要素」がくるようにする。この操作をpartitionと呼ばうらしい。partitionによって配列の更新と、更新後のpivotのインデックスを返すようにすれば、pivotより小さい部分の配列と大きい部分の配列に分割できるのでそれらに対して同じように処理していくのだ。partitionの部分はなんか説明しにくいので見てくれ

def partition(a, l, r)
  pivot = a[r-1]
  j = l-1
  (l...r).each do |i|
    if a[i] <= pivot
      j+=1
      a[j], a[i] = a[i], a[j]
    end
  end
  return j
end

def quick_sort(a, l, r)
  if 1 < r-l
    q = partition(a, l, r)
    quick_sort(a, l, q)
    quick_sort(a, q+1, r)
  end
end

だいたいの言語のsort関数なんかはサイズが小さいときはマージソートで大きいときはクイックソート使うらしいみたいなのを聞いたことがある。知らんけど

実装

入力される要素に合わせて上で書いたやつを書き換えたりなんかしたり

def partition(a, l, r)
  pivot = a[r-1][1]
  j = l-1
  (l...r).each do |i|
    if a[i][1] <= pivot
      j+=1
      a[j], a[i] = a[i], a[j]
    end
  end
  return j
end

def quick_sort(a, l, r)
  if 1 < r-l
    q = partition(a, l, r)
    quick_sort(a, l, q)
    quick_sort(a, q+1, r)
  end
end


def merge(a, l, m, r)
  l_arr = a[l, m-l] << ['', 10000000000000000000]
  l_i = 0
  r_arr = a[m, r-m] << ['', 10000000000000000000]
  r_i = 0
  
  (l...r).each do |idx|
    # 小さい方から入れていく
    if l_arr[l_i][1] <= r_arr[r_i][1]
      a[idx] = l_arr[l_i]
      l_i+=1
    else
      a[idx] = r_arr[r_i]
      r_i+=1
    end
  end
end

def merge_sort(a, left, right)
  if 1 < right-left
    mid = (right+left)/2
    merge_sort(a, left, mid)
    merge_sort(a, mid, right)
    merge(a, left, mid, right)
  end
end

n = gets.to_i
a = []
n.times do
  a << gets.chomp.split.map{|x| x.match?(/\d/) ? x.to_i : x}
end
b = a.clone
quick_sort(a, 0, n)
merge_sort(b, 0, n)

puts a == b ? "Stable" : "Not stable"
a.each do |av|
  puts "#{av[0]} #{av[1]}"
end

はい よくできました えらいね。クリスマスプレゼントは職がいいです

*1:LLなら軽率に配列を作ったりぶっ壊すのが楽という雑魚認識