情報自炊

情報を血肉にしたい

選択ソート

最小のものを探して交換していくソート。実行時間はO(n^2)。「xxソート」という言葉と、その言葉が意味するアルゴリズムが紐付かないことがあるのでしっかり覚えるようにする。

# 選択ソート
arr = gets.chomp.split(" ").map(&:to_i)
puts "before: #{arr}"

(0..(arr.length-2)).each do |i|
  min = arr[i]
  min_j = i
  # 最小を見つける
  ((i+1)..(arr.length-1)).each do |j|
    if arr[j] < min then
      min = arr[j]
      min_j = j
    end
  end
  # arr[i]とarr[min_j]を交換
  tmp = arr[i]
  arr[i] = min
  arr[min_j] = tmp
  puts "#{i}: #{arr}"
end

puts "after: #{arr}"

実行例
標準入力:3 5 4 2 1

before: [3, 5, 4, 2, 1]
0: [1, 5, 4, 2, 3]
1: [1, 2, 4, 5, 3]
2: [1, 2, 3, 5, 4]
3: [1, 2, 3, 4, 5]
after: [1, 2, 3, 4, 5]

挿入ソート

アルゴリズムイントロダクション 第3版 総合版:世界標準MIT教科書

アルゴリズムイントロダクション 第3版 総合版:世界標準MIT教科書

アルゴリズムに強くなってAtCoderのレートを上げたいので基礎から勉強中。

本書には擬似コードが載っているが、せっかくなのでrubyで実装。

# 挿入ソート
arr = gets.chomp.split(" ").map(&:to_i)
puts "before: #{arr}"

(1..(arr.length-1)).each do |j|
  key = arr[j]
  puts "j=#{j}, key=#{key}"
  # keyをソート済みの列に挿入
  i = j - 1
  while i >= 0 && arr[i] > key do
    puts "i=#{i}, arr[#{i + 1}]=#{arr[i + 1]}, arr[#{i}]=#{arr[i]}"
    arr[i + 1] = arr[i]
    i -= 1
  end
  arr[i + 1] = key
  puts "#{arr}"
  puts "------"
end

puts "after: #{arr}"

実行例 標準入力:3 2 1 4 5

before: [3, 2, 1, 4, 5]
j=1, key=2
i=0, arr[1]=2, arr[0]=3
[2, 3, 1, 4, 5]
------
j=2, key=1
i=1, arr[2]=1, arr[1]=3
i=0, arr[1]=3, arr[0]=2
[1, 2, 3, 4, 5]
------
j=3, key=4
[1, 2, 3, 4, 5]
------
j=4, key=5
[1, 2, 3, 4, 5]
------
after: [1, 2, 3, 4, 5]

diverta 2019 Programming ContestのA〜D問題振り返り

結果はA, B, CがACで、DがTLEでした。初めて400点問題を正解できたので嬉しい。D問題もあと一歩でACだったので惜しかった。

A問題

atcoder.jp

提出

n,k=gets.chomp.split(" ").map(&:to_i)

puts n - k + 1

本当にこれで良いのか少し緊張した。

B問題

atcoder.jp

提出

r,g,b,n=gets.chomp.split(" ").map(&:to_i)

count = 0

(0..3000).each do |r_i|
  (0..3000).each do |g_i|
    tmp = n - r * r_i - g * g_i
    if tmp >= 0 && tmp % b == 0 then
      count += 1
    end
  end
end

puts count

r個とg個が定まれば、b個が求まるので3重ループしなくて良い。過去問から学んだ知識。

C問題

atcoder.jp

提出

n = gets.chomp.to_i

a_flag_count = 0
b_flag_count = 0
a_b_flag_count = 0
count = 0
n.times do |t|
  str = gets.chomp
  count += str.scan(/AB/).size
  a_flag = str[-1] == "A"
  b_flag = str[0] == "B"
  if a_flag && b_flag then
    a_b_flag_count += 1
  elsif a_flag then
    a_flag_count += 1
  elsif b_flag then
    b_flag_count += 1
  end
end

if a_b_flag_count > 0 then
  count += (a_b_flag_count - 1)
  if a_flag_count > 0 then
    count += 1
    a_flag_count -= 1
  end
  if b_flag_count > 0 then
    count += 1
    b_flag_count -= 1
  end
  count += [a_flag_count, b_flag_count].min
else
  count += [a_flag_count, b_flag_count].min
end

puts count

公式解説と若干アプローチが違う…のか?私なりの解説を少し入れてみる。

  1. BXA(先頭がB, 末尾がA)
  2. BXX(先頭がB, 末尾がAでない)
  3. XXA(先頭がBでない, 末尾がA)

この3通りを数える。ここは同じ。

1の個数が0の場合、ここも同じ。

1の個数が0でない場合、ここが違うかも。

このときに私は1の文字列を連続で横に並べるようにした。

BXA|BXA|...|BXA|BXA
※見やすいように間に"|"を入れている。

横並びにすればABの部分文字列が(1個数 - 1)個できる。

その後、2に該当する文字列が存在すれば上の文字列の末尾に1個つけるように、3に該当する文字列が存在すれば上の文字列の先頭に1個つけるようにした。

XXA|BXA|BXA|...|BXA|BXA|BXX

それぞれ存在するときに限りABの文字列が1個ずつ増える。

そして余った2, 3の文字列同士をくっつけてさらにABの文字列を増やした(これは1の個数が0の場合と同じ計算式)。

D問題

atcoder.jp

提出(TLE)

n = gets.chomp.to_i

result = 0

(1..n).each do |r|
  next if n % r != 0
  p = n / r - 1
  if r >= p then
    break
  else
    result += p
  end
end

puts result

なぜかmをpとして書いている。

商がq, 余りがrとしてN = m * q + r (0 <= r < m), q = rだから、式変形してm = N / r - 1。rは1からNまで取りうるのでループ…としたけどこのループがまずかった。

Nの約数を見つけると考えればO(sqrt(n))で済むのだ。

提出

n = gets.chomp.to_i

result = 0

(1..Math.sqrt(n)).each do |r|
  next if n % r != 0

  m = n / r - 1
  result += m if r < m

  r2 = n / r
  m2 = n / r2 - 1
 result += m2 if r2 < m2
end

puts result

0 <= r < mという関係でrが0以上であることはループの対象から自明なので、r < mというチェックを入れている。

本当はrとr2が等しいときに二重で計上してしまうおそれがあるからスキップした方が良いと思ったけど、今回の問題ではACが出たのでこれで。

ニコニコのランキングで、新着動画のみを表示するブックマークレット

小ネタ。いわゆる「急上昇」「HOT」な動画のみを表示する方法。

左がbefore, 右がafter。

f:id:hoshitostar:20190510121412p:plainf:id:hoshitostar:20190510121524p:plain

カテゴリ合算だと「24時間:100→42」「毎時:100→45」に動画が減った。 バーチャルだと「24時間:100→28」「毎時:100→36」だ。

ブックマークレットを読みやすいように整形したのがこちら。

$('html').animate({scrollTop: $(document).height()}, function () {
  setTimeout(function () {
    $(".itemTime:not(.new)").closest(".item.videoRanking").hide();
    $(window).scrollTop(0);
  }, 500)
});

スクロールバーを一番下まで移動して、スタイルをいじって、スクロールバーを一番上まで移動するという手順だ。スクロールバーを移動する理由は、サムネイル画像が遅延ロードされているためである。

ランキングを毎日チェックする場合、常連動画を気にせず新着動画のみに注目できるので、ある程度時短になったり、見逃しが無くなると思う。

情報の自炊が上手くなるのを目指す

TL;DR

  • ブログの方針が固まりました
  • 世の中情報が溢れすぎていてやばい、疲れる
  • このブログを通じて情報の処理が上手くなれるよう目指す

情報オーバーロードって知ってる?

ja.wikipedia.org

私は知りませんでした。

私は昔から情報を集めたり眺めたりすることが好きで、情報通になりたいと思っていました。よくゲームの裏技集(広技苑とかありましたよね)とか見て、こんな隠れた情報があるのだと…!?と悦に入っていたことを覚えています。

情報インフラが発達し、サービスが発達し、いまやググっただけで…むしろググらなくてもTL眺めているだけで情報が手に入るような時代になってきました。

しかし上のWikipediaにあるようにいまや情報過多の時代。SNS疲れとはまた系統の違った疲れが私を襲っておいます。例えば毎日寝る前にはてなブックマークでトレンドを追わなきゃ、サイトを巡回しなきゃ…という強迫観念に似たようなものに駆られるわけです。おそらくそんなに必死にならなくてもいいのですが、知りたがりが災いしてしまい情報を探してしまう。結果寝不足になるわけです。

情報が流れるプロセス

大まかにこのようなプロセスで流れると思います。

  • 得る
    • ネットや本、ニュースなどで情報を知る
  • 蓄積する
    • あとでよむに突っ込むとか、切り抜きをするとか、本棚に並べる
  • 使う
    • 知識として定着させる
    • 実践する
  • 出す
    • ブログ書く

このプロセスひとつひとつに課題があると思っていて、まずはそこから整理するところから始めないとなと思っているところです。「情報が多すぎる」とか「蓄積した情報を見直すタイミングを逃す」とか「1回使った情報が使い捨てになってしまう」とか…。

それら課題についてITのパワーに使って解決する。課題を通じて勉強できてスキルも上がれば一石二鳥!とか実践前の私は思っているわけです。

情報中毒になっているかもしれない

長期ベストセラーの本書。私も過去にやったことがあり、課金して34個全ての結果も見ています。

私の結果。

f:id:hoshitostar:20190509001943p:plain

赤:戦略的思考力、紫:実行力、黄:影響力、藍:人間関係構築力

1〜5位は納得な結果でした。集めて、考えたり勉強したりして、考察するのが好き。逆に6位〜10位は少し意外。戦略的思考力と人間関係構築力が上位2つで固まっていて、実行力と影響力が控えめという分かりやすい能力だと思っています。陰キャって感じがする

そういうことでおそらく他の人よりは多く情報を集めようとしているのだと思います。結果、情報を浴びすぎて疲れる…中毒的なものになっているのでしょう。

食材は適切な量を買って冷蔵庫に保管。痛む前に調理して美味しくいただいて健康な体を作っていきましょう。これの情報版をやっていきたいです。

AGC033 A問題をRubyで解いた際の反省点

これまで300点問題を一回も解いたことがなかったので、解けることを目標に挑んだ。 atcoder.jp

結果はTLE。今回もアルゴリズム的にダメだったのか、と思って解説や他の方のコードを見てみたところ…あれアルゴリズムは合ってる?

ダメだったところは値の持ち方、アクセスの仕方だった。いろいろ試してみて、最低限直すべきところが分かったのでここにまとめる。

修正前(TLE)

h,w = gets.chomp.split(" ").map(&:to_i)

arr = []
hash = {}
count = 0
result = 0
h.times do |h_i|
  tmp_arr = gets.chomp.split("")
  tmp_arr.each_with_index do |a, w_i|
    if a == "#" then
      hash[[h_i, w_i]] = 0
      count += 1
    end
  end
  arr << tmp_arr
end

while count < h * w do
  keys = hash.keys
  hash = {}
  result += 1
  keys.each do |(h_i, w_i)|
    if h_i - 1 >= 0 && arr[h_i - 1][w_i] == "." then
      hash[[h_i - 1, w_i]] = result
      arr[h_i - 1][w_i] = "#"
      count += 1
    end
    if h_i + 1 < h && arr[h_i + 1][w_i] == "." then
      hash[[h_i + 1, w_i]] = result
      arr[h_i + 1][w_i] = "#"
      count += 1
    end
    if w_i - 1 >= 0 && arr[h_i][w_i - 1] == "." then
      hash[[h_i, w_i - 1]] = result
      arr[h_i][w_i - 1] = "#"
      count += 1
    end
    if w_i + 1 < w && arr[h_i][w_i + 1] == "." then
      hash[[h_i, w_i + 1]] = result
      arr[h_i][w_i + 1] = "#"
      count += 1
    end
  end
end

puts result

ダメだった点は以下の3点

  1. "."や"#"と文字列のまま扱おうとしている
    • arrの中身が"."や"#"であり、whileの中身で== "."と文字列比較をしている
  2. gets.chomp.split("")
    • 配列を作成しているのが無駄。文字列のままでもインデックスを用いてn番目の文字へのアクセスが可能
  3. keys = hash.keys
    • hashのkeyでループして配列を作成する処理が無駄

他にも無駄になりそうな処理はあったが(番兵を用いてarrの外側へアクセスしないための条件分岐を減らすとか)対応しなくても大丈夫だった。上記3つは対応しないとTLEになってしまう。

特に1番目はこれで遅くなるとは微塵も思っていなかったのでとても勉強になった(コンテスト終了後の検証でもまさかこれが遅くなっている原因とは知らず驚いた)。

今回はコードを書く前にじっくり考えることができたので、最初からこのアルゴリズム自体で挑もうと思っていた。処理時間もO(HW)だから大丈夫だろうと思った矢先のTLEだったのでどうしたものかと困ったが、コンテスト後にこうして検証して原因まで分かったのでよしとする。

Rubyで最初解いていてTLEもらっていた人が、同じアルゴリズムC++で組み直してACをもらっていたのも見かけたので、やっぱりC++有利なのかなあとは思った。でも私は何がなんでもコンテストを勝ち抜くのが目的ではなく頭の体操が目的なので、このままRubyで突き進もうと思う。速くなるテクニックが見つかれば普段のコードでも意識できると思うし。

修正後

h,w = gets.chomp.split(" ").map(&:to_i)

arr = []
keys = []
count = 0
result = 0
h.times do |h_i|
  tmp_arr = []
  str = gets.chomp
  w.times do |w_i|
    if str[w_i] == "#" then
      keys << [h_i, w_i]
      count += 1
      tmp_arr << 1
    else
      tmp_arr << 0
    end
  end
  arr << tmp_arr
end

while count < h * w do
  tmp_keys = keys
  keys = []
  result += 1
  tmp_keys.each do |(h_i, w_i)|
    if h_i - 1 >= 0 && arr[h_i - 1][w_i] == 0 then
      keys << [h_i - 1, w_i]
      arr[h_i - 1][w_i] = 1
      count += 1
    end
    if h_i + 1 < h && arr[h_i + 1][w_i] == 0 then
      keys << [h_i + 1, w_i]
      arr[h_i + 1][w_i] = 1
      count += 1
    end
    if w_i - 1 >= 0 && arr[h_i][w_i - 1] == 0 then
      keys << [h_i, w_i - 1]
      arr[h_i][w_i - 1] = 1
      count += 1
    end
    if w_i + 1 < w && arr[h_i][w_i + 1] == 0 then
      keys << [h_i, w_i + 1]
      arr[h_i][w_i + 1] = 1
      count += 1
    end
  end
end

puts result

「入門 起業の科学」を読みました

入門 起業の科学

入門 起業の科学

起業に少しでも興味がある人にとっては良い教科書だと思う。そうでない人でも自分が起業家に向いているかどうかを知るために読んでみるといいかもしれない。前著「起業の科学 スタートアップサイエンス」はかなり本格的に書かれていたので、本書を読んで興味と情熱が続くようであればこちらも読んでみるべし。

「誰が聞いても良いアイデア」はスタートアップに適していません。

本書の中でも好きなフレーズ。「科学」と題しているだけあって、なぜそうなるのかが詳しく書かれている。

「スタートアップ」と「スモールビジネス」。一見似ていますし、いずれも「起業」することには変わりませんが、両者は全く異なるものです。

かなり序盤のお話なのだが、この話が一番興味深っかた。この違いを読めば読むほど、もし2択なのであれば、自分はスタートアップよりもスモールビジネスの方が向いていると感じた。なのでここから先は何かフィクションを覗いているかのように読み進めていった。「こういう世界もあるんだなあ」と。

適材適所という言葉があるように、スタートアップに属することが正解とかそういうことでは無いと思う。

読後に検索して読んだ記事たち。

note.mu

dennou-kurage.hatenablog.com

0→1か1→10かと聞かれたら私は後者なのであろう。1→10か10→100かと問われたら…ちょっと分からないけど直感的には1→10なのかなあ。

しかし現在、私の身が置かれているのは0→1のスタートアップ企業。以前から感じていたモヤモヤの正体のひとつがこのギャップにあるのかなと思った。「今」をベースにより良くしていくところに快を感じるか、「今」を再定義して全く違うものにしていくとろに快を感じるか。やっぱり人によるか。