書くのはタダだけどネタがないのでなんか書こうと思うんだけど続けられないとアレなので続けられそうなネタと更新頻度を考えた結果タイトル、および家賃を振り込むタイミングで動機づけしようと思います
- 映画
- 海獣の子供
- パフューム ある人殺しの物語
- チョコレートドーナツ
- 本
- アニメシリーズ
- 音楽
- Hans Zimmer
- SAKAMOTO Ryuichi
- Floatin Points
- OSAWA Shinichi
残り30分で4完までいったところで酒を飲んだよね。
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")
ある数列の連続する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)
偶数個の要素をもつ数列を2つに分けるとき、一方の最大値が以下、他方の最小値が以上になるような整数はいくつあるだろうか。
ソートしたら真ん中の二要素の差になるのでそうする。
n = int(input()) arr = list(sorted(list(map(int, input().split())))) print(arr[n//2] - arr[n//2 - 1])
要約が難しいので抽象的にすると、個の赤玉を並べ、そのそれぞれの間(両端含む)に0個以上の個の青玉を並べるときの並び方。
まず青玉を並べられる場所は赤玉の間および両端でありこれが箇所。ここに個の青玉をグループに分けて並べるとして、通りの選択ができる。nCr
の組み合わせの数はググるとアルゴリズムが出てくる。
ここまでわかって、じゃあ残りの、各グループにふりわける個の青玉の組み合わせってどうすんだろ、となってK=5くらいまで書き出してみるとどっかでみたことある分け方だと気づき、適当に「高校数学 グループ分け」みたいなワードでググって 二項係数とかいう単語にぶちあたり、それっぽかったので更に適当に「python 二項定理」でググって最初に出てきたやつをコピペして貼って計算。 毎回10**9+7であまりをだす。pythonなので桁は気にせず最後にやりゃいいだろ(と、ビクビクしながら提出)
# 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)
これは引数にリストで渡したやつの組み合わせを考えるやつ。
前書いたのはたしか1.7系で、そのときのノリで再々々入門をしようとしてモダンな書き方を調べると、modules ?なんですかこれは? 知らない子ですね...?
GOPATH モードからモジュール対応モードへ移行せよ - Qiita
Go Modulesの概要とGo1.12に含まれるModulesに関する変更 #golangjp #go112party - My External Storage
えっGOPATH
ばいばいなの....わーいわーい
当時、学習用にお世話になってたこちらを使い、
中身をそのまんまやっていて、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
あっそう
cd
などは反映されない単純につなげればいけると思ってましたが駄目でした。なお続けて書くやつはこちらを参考にしました
VSCodeでタスク実行時に複数コマンド実行 - Qiita
&&
でいけるらしい結局、こうしました
"command": "cd ${fileDirname} && go run ${fileBasename}"
これだとgo runしたいディレクトリで
cd`で遷移した状態で実行可能になりました。
"command": "cd ${fileDirname} && go run *.go"
総括すると、酒のつまみって感じです(?)(実際酒飲みながら答えた)
直方体の高さ、幅、奥行きが与えられるからその表面積を答える。直方体の展開図書けば分かるように全6面はそれぞれ同じ矩形が2つずつ3種類からなる。表面積はその合計なので与えられた各辺の情報から計算する。
a, b, c = gets.chomp.split.map(&:to_i) puts (a*b*2+a*c*2+b*c*2)
整数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
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ですが、この頃はまだドレミ唱法などというマイナー音名表記を使っていたため日本人にしか解けない問題ですね、知らんけど
「#
の周囲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の問題セットから解いていくシリーズ。界隈ではABC042以降を解けという声がありますが果敢に無視します
数値が与えられるので値で分岐して答える
n = gets.to_i if n<=59 puts "Bad" elsif n<=89 puts "Good" elsif n<=99 puts "Great" else puts "Perfect" end
文字列が与えられるからどの文字が何回出現したかを出力する。文字列は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(' ')
それぞれ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
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