ABC132に参加した（WIP Dまで）

残り30分で4完までいったところで酒を飲んだよね。

A - Fifty-Fifty

4文字からなる文字列が2種類の文字それぞれ2文字ずつから成るかどうか判定させられる。

無限に実装のバージョンがあるので好きなやつを使う（解説になってない)。

s = sorted(input())
if s[0] == s[1] and s[2] == s[3] and len(set(s)) == 2:
    print("Yes")
else:
    print("No")

B - Ordinary Number

ある数列の連続する3要素 のうちが2番目に小さいところになる箇所の数を求める。

なにげに 二番目に小さい が罠で、3数なので 二番目に大きい とも言えることに注意して、1からn-1までiの前後をみてやる

n = int(input())
arr = list(map(int, input().split()))
count = 0
for i in range(1, n - 1):
    if arr[i - 1] < arr[i] < arr[i + 1] or arr[i - 1] > arr[i] > arr[i + 1]:
        count += 1

print(count)

C - Divide the Problems

偶数個の要素をもつ数列を2つに分けるとき、一方の最大値が以下、他方の最小値が以上になるような整数はいくつあるだろうか。

ソートしたら真ん中の二要素の差になるのでそうする。

n = int(input())
arr = list(sorted(list(map(int, input().split()))))
print(arr[n//2] - arr[n//2 - 1])

D - Blue and Red Balls

要約が難しいので抽象的にすると、個の赤玉を並べ、そのそれぞれの間（両端含む）に0個以上の個の青玉を並べるときの並び方。

まず青玉を並べられる場所は赤玉の間および両端でありこれが箇所。ここに個の青玉をグループに分けて並べるとして、通りの選択ができる。nCrの組み合わせの数はググるとアルゴリズムが出てくる。

ここまでわかって、じゃあ残りの、各グループにふりわける個の青玉の組み合わせってどうすんだろ、となってK=5くらいまで書き出してみるとどっかでみたことある分け方だと気づき、適当に「高校数学 グループ分け」みたいなワードでググって 二項係数とかいう単語にぶちあたり、それっぽかったので更に適当に「python 二項定理」でググって最初に出てきたやつをコピペして貼って計算。 毎回10**9+7であまりをだす。pythonなので桁は気にせず最後にやりゃいいだろ（と、ビクビクしながら提出）

二項定理をpythonで計算する - Qiita

# ncrをうまく使う感じ
# 二項定理はググった https://qiita.com/r_u__r_u/items/5e5baeb0194854cbf156

from math import factorial

n, k = map(int, input().split())
nn = n - k + 1  # 使える箇所


def ncr(n, r):
    res = 1
    for i in range(1, r+1):
        res = res * (n-i+1)//i
    return res


def calc(k):
    return [factorial(k)//(factorial(i)*factorial(k-i)) for i in range(k+1)]


nikouteiri = calc(k-1)

for i in range(1, k + 1):
    # 使える箇所からi個とり、kをi個のグループに分けたやつをかける
    print((ncr(nn, i) * nikouteiri[i-1]) % (10**9+7))

本番中解けなかったE, Fについては後日〜

ジェネレータで再帰的に組み合わせを返す

たとえば0 1からなるビット列の配列がほしいみたいなとき。組み合わせが少なければ愚直にやってもいいが、多いとき、ビット演算でやると文字列の扱いになって変換処理が時間的にボトルネックになり、リストで管理するとメモリ的にボトルネックになる。

ジェネレータで毎回帰ってきた値を処理できれば嬉しいと思うのでそうする。これですべての組み合わせみたいなよくあるパターンも処理できるわけ。next_permutation的なこともできるんじゃないの。しらんけど

def f(arr, limit):
    if len(arr) == limit:
        yield arr
    else:
        for i in [0, 1]:
            next_arr= arr[:]
            next_arr.append(i)
            for j in f(next_arr, limit):
                yield j

g = f([], 10)
count = 0
for x in g:
    print(x)
    count += 1
print("count: {}".format(count))  # 1024

nCr的な組み合わせ列挙ならこうやるねぼかぁ

def nCr(i, cur, rest, target):
    if rest == 0:
        yield cur
    elif len(target) - i == rest:
        # 今回のやつを取るしかない
        nex = cur[:]
        nex.append(target[i])
        for ncr in nCr(i+1, nex, rest-1, target):
            yield ncr
    else:
        # 含めるか含めないか
        nex = cur[:]
        nex.append(target[i])
        for ncr in nCr(i+1, nex, rest-1, target):
            yield ncr
        for ncr in nCr(i+1, cur[:], rest, target):
            yield ncr
        

arr = list(range(8))
g = nCr(0, [], 5, arr)
for x in g:
    print(x)

参考っぽいの

これは引数にリストで渡したやつの組み合わせを考えるやつ。

再帰とジェネレータ

俺はtask buildでGo modulesのgoコードを走らせたいだけなんだ

すげぇ久しぶりにGo書こうとしたら

前書いたのはたしか1.7系で、そのときのノリで再々々入門をしようとしてモダンな書き方を調べると、modules ?なんですかこれは？ 知らない子ですね...？

GOPATH モードからモジュール対応モードへ移行せよ - Qiita

Go Modules - Qiita

Go Modulesの概要とGo1.12に含まれるModulesに関する変更 #golangjp #go112party - My External Storage

えっGOPATHばいばいなの....わーいわーい

すげぇ久しぶりにGo書いたら

当時、学習用にお世話になってたこちらを使い、

www.shoeisha.co.jp

中身をそのまんまやっていて、vscodeでやっていくことにして、starting_go/から、

.
├── README.md
├── chap1
│   ├── go.mod
│   └── tekitou.go
├── chap2
│   └── zoo
│       ├── animals
│       │   └── elephant.go
│       ├── go.mod
│       └── main.go
├── chap3

chap2をgo buildしようとしたわけ。

各ファイルは、

// go.mod
module m

go 1.12

// animals/elephant.go
package animals

func ElephantFeed() string {
    return "GRASS"
}

// main.go
package main

import (
    "fmt"
    "m/animals"
)

func main() {
    fmt.Println(animals.ElephantFeed())
}

みたいなノリで適当に

  "tasks": [
    {
      "label": "run",
      "type": "shell",
      "command": "go",
      "args": [
        "run",
        "${file}"
      ],
    }

的なtasks.jsonでやったら怒られるわけです。

> Executing task: go run /Users/this/is/fullpath/for/workspace/starting_go/chap2/zoo3/main.go <

build command-line-arguments: cannot load m/animals: cannot find module providing package m/animals

あっそう

tasks.jsonでコマンドを続けて書いても、cdなどは反映されない

単純につなげればいけると思ってましたが駄目でした。なお続けて書くやつはこちらを参考にしました

VSCodeでタスク実行時に複数コマンド実行 - Qiita

&&でいけるらしい

結局、こうしました

"command": "cd ${fileDirname} && go run ${fileBasename}"

これだとgo runしたいディレクトリでcd`で遷移した状態で実行可能になりました。

main.goで他のパッケージを呼んでいる場合

 "command": "cd ${fileDirname} && go run *.go"

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=X⁴である。実数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 - ピアニスト高橋君

W、Bからなる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~10⁶まで取り得る整数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

2018年の段階で知らないことを呼んで知らないことのごく一端を知った気になった

元ネタ

overreacted.io

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で最も難しい（個人の感想）。普通に解説読んだ。次に乗れる便を探すのに二分探索を使う（N⁵、M⁵とかででかいので愚直にやると間に合わない）。よくある最大値のうちの最小値を読み替えた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