電波ビーチ

☆（ゝω・）v

消費したコンテンツ8月2019

life

8月です。就職しました。

  • 映画
  • ドラマ
    • 全裸監督
    • Life Below Zero（邦題：氷点下で生きるということ）
  • 本
    • 三体（一巻）
    • はじめてのPHPプロフェッショナル開発
  • アニメ
  • 配信
    • 花譜1stLIVE『不可解』

就職したせいで可処分時間が激減し、各コンテンツの消費量が軒並み減ってしまい、QOLも減った。飲酒量は増えた。労働は健康に悪い。

続きを読む

WSL（ubuntu）でanacondaを使ってみる

windows WSL python Linux

setup WSL

WSLを入れる。

  • アプリと機能
  • プログラムと機能
  • Windowsの機能の有効化または無効化
  • Windows Subsystem for Linuxにチェックを入れる

次に開発者モードにて有効化。

  • 更新とセキュリティ
  • 開発者向け
  • 開発者モード

そしてストアにてUbuntuをインストールした。

install anaconda

wget https://repo.continuum.io/archive/Anaconda3-2019.07-Linux-x86_64.sh
bash https://repo.continuum.io/archive/Anaconda3-2019.07-Linux-x86_64.sh

どっかで設定を見逃したのか、起動時に自動的にconda環境にならなくなってしまった。以下を打ち込むと起動するので

eval "$(/home/<your wsl username>/anaconda3/bin/conda shell.bash hook)"

こいつを~/.profileに加えてやるといける。ubuntuだと.bash_profileじゃないんですね。初めて知った。

消費したコンテンツ7月2019

life

書くのはタダだけどネタがないのでなんか書こうと思うんだけど続けられないとアレなので続けられそうなネタと更新頻度を考えた結果タイトル、および家賃を振り込むタイミングで動機づけしようと思います

続きを読む

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

競プロ ruby AtCoder

残り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要素 p_{i-1}, p_{i}, p_{i+1} のうちp_{i}が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つに分けるとき、一方の最大値がK以下、他方の最小値がK以上になるような整数Kはいくつあるだろうか。

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

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

D - Blue and Red Balls

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

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

ここまでわかって、じゃあ残りの、各グループにふりわけるK個の青玉の組み合わせってどうすんだろ、となって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については後日〜

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

Algorithm python 競プロ

たとえば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 vscode

すげぇ久しぶりに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を解いた

AtCoder

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

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 - ピアニスト高橋君

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を食らった...