Atcoder ABC262 振り返り
A - World Cup【AC】
条件を満たすまで+1し続けます．4で割った余りが2が条件なので最大でも3ループで終わることが分かります．
Y = int(input()) while Y%4 != 2: Y += 1 print(Y)
B - Triangle (Easier)【AC】
隣接リストを作ります．辺が存在するかはinで確認します．N<100なのでinでも十分間に合います．
N, M = map(int, input().split()) node = {i+1:[] for i in range(N)} for _ in range(M): u, v = map(int, input().split()) node[u].append(v) node[v].append(u) ans = 0 for a in range(1, N-1): for b in range(a, N): for c in range(b, N+1): if a in node[b] and b in node[c] and c in node[a]: ans += 1 print(ans)
C - Min Max Pair【AC】
i==A[i]の時とそうでないときで処理が変わります．i==A[i]であるようなiの集合は，どの2つを持ってきてもminとmaxの条件を満たします．i
N = int(input()) A = [int(i)-1 for i in input().split()] cou = 0 ans = 0 for i in range(N): if i == A[i]: cou += 1 else: if i == A[A[i]] and i < A[i]: ans += 1 print(ans+(cou*(cou-1))//2)
Atcoder ABC260 振り返り
A - A Unique Letter【AC】
Counter関数を使いました．今回の入力popだとCounter({'p': 2, 'o': 1})が得られます．後は，items()で値を取りだし，要素が1つしか無いものを表示します．
import collections s = list(input()) c = collections.Counter(s) for v, n in c.items(): if n == 1: print(v) break else: print(-1)
B - Better Students Are Needed!【AC】
ソートする際に，受験者の番号を保持しておくため[点数, 受験者の番号]を要素としてソートします．また，点数は高い順に並べたいので，点数にマイナスを掛けておきます．
既に合格済みの生徒はpass_setに入れておきながら，問題文の通りに合格者を決めていきます．
N, X, Y, Z = map(int, input().split()) A = [[-int(v), i+1] for i, v in enumerate(input().split())] B = [[-int(v), i+1] for i, v in enumerate(input().split())] C = [[A[i][0] + B[i][0], i+1] for i in range(N)] A, B, C = sorted(A), sorted(B), sorted(C) pass_list = [] pass_set = set() for i in range(X): pass_set.add(A[i][1]) pass_list.append(A[i][1]) cou = 0 for i in range(N): if cou == Y: break if B[i][1] not in pass_set: pass_set.add(B[i][1]) pass_list.append(B[i][1]) cou += 1 cou = 0 for i in range(N): if cou == Z: break if C[i][1] not in pass_set: pass_set.add(C[i][1]) pass_list.append(C[i][1]) cou += 1 for p in sorted(pass_list): print(p)
C - Changing Jewels【AC】
動的計画法のことは一切頭にないまま実装しました．リストのkey iにレベルiの宝石の個数を入れます．赤い宝石と青い宝石の変換をそれぞれN回行うのが最大なのでN回ループしblue[1]を表示させます．
N, X, Y = map(int, input().split()) red = {i:0 for i in range(1, N+1)} blue = {i:0 for i in range(1, N+1)} red[N] = 1 for n in range(N, 1, -1): red[n-1] += red[n] blue[n] += red[n]*X red[n-1] += blue[n] blue[n-1] += blue[n]*Y print(blue[1])
Atcoder ABC257 振り返り
A - A to Z String 2【AC】
文字と数字を変換するにはordとchrを使います．Aはunicodeで65なのでそれに1ずつ＋していくとBCD...と文字と用意できます．
N, X = map(int, input().split()) ans = "" for i in range(26): ans += chr(65+i)*N print(ans[X-1])
B - 1D Pawn【AC】
Q回全てシミュレーションします．一番右にいたり隣にコマが存在したらcontinueします．
N, K , Q = map(int, input().split()) A = [int(i) for i in input().split()] L = [int(i) for i in input().split()] for i in range(Q): ind = L[i] - 1 if A[ind] == N: continue if ind < K-1 and A[ind] + 1 == A[ind+1]: continue A[ind] += 1 print(*A)
C - Robot Takahashi【AC】
Wはソートしても問題無いことを利用します．ソートするときSの大人か子供かの情報も必要なので辞書を用意し大人と子供の人数を数えます．辞書にしているのは同じ体重が複数人いたときにそれぞれ人数を加算できるようにするためです．
W=sorted(W)として，f(X)のXをX
N = int(input()) S = list(map(int, list(input()))) adult = S.count(1) child = S.count(0) W = [int(i) for i in input().split()] dic = {} for i, w in enumerate(W): dic.setdefault(w, {0:0, 1:0}) dic[w][S[i]] += 1 W = sorted(set(W)) ans = adult a = 0 c = 0 for w in W: c += dic[w][0] a += dic[w][1] ans = max(ans, adult - a + c) print(ans)
Atcoder ABC259 振り返り
A - Growth Record【AC】
X歳後は身長は伸びないのでX<=Mなら身長はそのままT，X歳前は毎年Dcm伸びますが逆に言うと1歳減るごとにDcm縮むということなのでX-M回-Dすれば良いです．
N, M, X, T, D = map(int, input().split()) if X <= M: print(T) else: for i in range(X-M): T -= D print(T)
B - Counterclockwise Rotation【AC】
(a, b)をd度回転させた点(a', b')を求めます．d度回転させるだけなので，原点と(a, b)の距離と原点と(a', b')は同じです．そのため，まず原点と(a, b)の距離disを求めます．
次に原点と(a, b)との角度θを求めます．三角関数を思い出すと，この角度はと表せます．このθを求めるにはtanの逆関数arctanを使えば良いです．
mathモジュールではmath.atan2を使います．math.atan関数もありますが，こちらは引数が1つでmath.atan(b/a)とします．しかしこれではa=0の時にエラーとなってしまうため，そのようなエラーを回避するために引数を2つとるmath.atan2(b, a)を使います．
この返り値は弧度法であることに注意します．dは度数法なのでmath.degreesを使って度数法に変換します．
度数法で原点と(a, b)の角度が分かったら，dを出す事で回転後の角度を求めます．
最後にこの角度から先ほど求めたdis分だけ離れた点を求めます．単位円を想像すると，x座標を求めるにはcos，y座標を求めるにはsinを使えば良いです．単位円なので距離は1です．よってdisだけ掛けてやれば答えを得られます．
import math a, b, d = map(int, input().split()) dis = (a**2+b**2)**(1/2) deg = math.degrees(math.atan2(b, a)) deg += d deg %= 360 aa = dis*math.cos(math.radians(deg)) bb = dis*math.sin(math.radians(deg)) print(aa, bb)
C - XX to XXX【解説AC】
WA2つ取れませんでした……
ランレングス圧縮はitertoolsモジュールのgroupby関数を使います．
itertools.groupby([1,1,2,2,2,3])は1, [1, 1, [2, [2, 2 ,2]], [3, [3]]]が返ってきます．型はリストではないため扱いには注意します．
ここで，WAと引っかかっていたのはaa aabのようなパターンです．コンテスト時はfor文でzip(grS, grT)としていましたが，これだとgrSとgrTの長さが異なるとき，長い方は最後までループされずに抜けてしまいます．この例で言うとgrS = a, [a, a], grT = a, [a, a, [b, [b]]]となりますが，普通のzipだとs=[a, [a, a]], t=[a, [a, a]]でgrSが尽きてしまうのでgrTの[b, [b]]が使われる事なくループを抜けてしまいます．そして，これはNoのはずなのにYesとなってしまいます．
grSとgrTの長さが異なれば必ずNoなのでそのような条件分岐を用意します．今回はitertools.zip_longestという関数を使います．これはその名の通り長さの長い方までループさせる関数です．短い方はNoneになります．よって，sかtのどちらかがNoneになればそれはgrSとgrTの長さが異なると言うことなのでNoとします．
import itertools S = list(input()) T = list(input()) grS = itertools.groupby(S) grT = itertools.groupby(T) for s, t in itertools.zip_longest(grS, grT): if s is None or t is None: print("No") break ss = len(list(s[1])) tt = len(list(t[1])) if s[0] != t[0]: print("No") break if not(ss == tt or (ss<tt and ss>=2)): print("No") break else: print("Yes")
D - Circumferences【AC】
問題をパッと見てunionfindだと分かったのは良かったです．
hirohirohirohiros.hatenablog.com
まず，始点と終点がどの円周上にあるかを調べます．円の方程式は(x-a)^2+(y-b)^2=r^2です．つまりこの方程式が成り立っているならば点が円周上にある事が分かります．
次に2つの円があった時に交わっているかを判定します．円が交わっているならその交点を使ってお互いの円周に移動する事が出来ます．一点で接していようが2点で交わっていようがお互いの円周に移動出来るので接しているか交わっているかは区別する必要ありません．
判定方法は円の中心同士の距離dと円の半径の和を使います．
円が外側で交わっていない場合，この図の通りd>r1+r2が成り立ちます．
これは円の衝突判定でもよく使われますが，今回の問題の場合内側に含まれている場合も互いの円周に移動出来ないので交わっていない判定する必要があります．この場合は図の通りd
このとき, 正しいdを求めるためにとしてはいけません．なぜなら，d=r1+r2やd=r1-r2の時も接しているため交わっている判定にしなくてはいけません．しかし，dにルートを取ってしまってはr1+r2と等しくなることはありません．そのため，dにルートを取るのでは無く，r1+r2やr1-r2を2乗することで判定させます(1WA).
これで2つの円が交わっているかどうか判定できました．
2つの円が交わっていればどちらの円周にも自由に移動出来るので実質1つのグループとして扱うことが出来ます．グループに含まれている1つの円が他のグループのどれかの円に交わっていた場合，2つのグループ間も自由に移動出来ることになるので，グループを結合して1つのグループとして扱うことが出来ます．
この処理はまさにunionfindです．円が交わっていたらunion.uniteで結合します．
最後に始点と終点にある円が同じグループかをunion.sameで判定します．同じグループなら円を伝って終点の円周まで辿り着けます．同じグループでなかったら辿り着けません．これで判定出来ました．
class Unionfind: ... N = int(input()) sx, sy, tx, ty = map(int, input().split()) circle_list = [] un = Unionfind(N) for i in range(N): xyz = [int(i) for i in input().split()] circle_list.append(xyz) if (sx - xyz[0])**2 + (sy - xyz[1])**2 == xyz[2]**2: s = i if (tx - xyz[0])**2 + (ty - xyz[1])**2 == xyz[2]**2: t = i for i in range(N): for j in range(N): if i == j: continue ci = circle_list[i] cj = circle_list[j] dis = ((ci[0] - cj[0])**2 + (ci[1] - cj[1])**2) if (ci[2] - cj[2])**2 <= dis <= (ci[2] + cj[2])**2: un.unite(i, j) if un.same(s, t): print("Yes") else: print("No")
統計学入門 第6章 練習問題 後半 解答まとめ
6.6
i)
\begin{align}
P(X>a+b|X>a) &= \frac{P(X>a+b \cap X>a)}{P(X>a)} \\
&= \frac{P(X>a+b)}{P(X>a)} \\
&= \frac{1-P(X\leq a+b)}{1-P(X\leq a)} \\
&= \frac{1-(1-e^{-λ(a+b)})}{1-(1-e^{-λa})} \\
&= e^{-λb}\\
&= P(X>b)
\end{align}
となる．
第6章で言われているように，指数分布は待ち時間分布の性質を持つ．故障率が一定のシステムの偶発的な故障までの待ち時間はこの分布に従う．
時間aまででシステムが故障してないとする．は，更に時間bが経過してもシステムが故障していない確率という意味になる．それに対し，
は（時間aまででシステムが故障しているいない関わらず）時間bまででシステムが故障していない確率である．つまり，時間bだけ経った後にシステムが故障しているかどうかは，時間aまででシステムが故障しているかどうかに無関係であるという意味になる．
ii)
\begin{align}
λ(x) &= \frac{f(x)}{1-F(x)} \\
&= \frac{λe^{-λx}}{1-(1-e^{-λx})} \\
&= λ
\end{align}
6.7
正規分布表を使います．表の値を見て0.01や0.02に最も近い所を見つけ，その行と列の値が答えcになります．|Z|>cの時，Zは正も負も取るので探す値は÷2します．
6.8
モードとは最も取る値の高い値です．つまりβ分布を微分すれば良いです．β分布は
\begin{align}
f(x) = \frac{x^{α-1}(1-x)^{β-1}}{B(α, β)}
\end{align}
である．ここでB(α, β)はβ関数であり，xは関わらない定数である．よって微分時には定数として扱える．
\begin{align}
f'(x) &= \frac{1}{B(α, β)}(α-1)x^{α-2}(1-x)^{β-1} - (β-1)x^{α-1}(1-x)^{β-2} \\
&= \frac{1}{B(α, β)}((α-1)(1-x) - x(1-β) )x^{α-2}x^{β-2} \\
&= \frac{1}{B(α, β)}((α-1) - x(α+β-2) )x^{α-2}x^{β-2}\\
\end{align}
これを0にするxが答えである．β分布は0<x<1の範囲上であるため答えは
\begin{align}
x = \frac{α-1}{α+β-2}
\end{align}
である．
6.9
ワイブル分布はx>0の時
\begin{align}
f(x) = \frac{bx^{b-1}}{a^b}e^{-(\frac{x}{a})^b}
\end{align}
である．これの累積分布確率は0からxまでを積分すれば求まる．
\begin{align}
F(x) &= \int_0^x f(x) dx \\
&= \int_0^x \frac{bx^{b-1}}{a^b}e^{-(\frac{x}{a})^b} dx \\
\end{align}
ここでと置くと，
となるので，
\begin{align}
F(x) &= \int_0^(\frac{x}{a})^b e^{t} \\
&= [e^t]_0^{(\frac{x}{a})^b} \\
&= 1-e^{(\frac{x}{a})^b}
\end{align}
6.10
尖度はとなる．まず
を求め4回微分し0を代入する．
標準正規分布はであるため，
\begin{align}
M_X(t) &= \int_{\infty}^\infty e^{tx}\frac{1}{\sqrt {2\pi}}e^{-\frac{x^2}{2}} dx \\
&= \frac{1}{\sqrt {2\pi}}\int_{\infty}^\infty e^{tx - \frac{x^2}{2}} dx\\
&= \frac{1}{\sqrt {2\pi}}\int_{\infty}^\infty e^{\frac{2tx - x^2}{2}} dx\\
&= \frac{1}{\sqrt {2\pi}}\int_{\infty}^\infty e^{-\frac{(x-t)^2}{2} + \frac{t^2}{2}} dx \\
&= e^{\frac{t^2}{2}}\int_{\infty}^\infty \frac{1}{\sqrt {2\pi}}e^{-\frac{(x-t)^2}{2}}
\end{align}
ここで，この積分は平均t，分散1の正規分布である事が分かる．それを-∞から∞まで積分しているのでこれは1である．よって
\begin{align}
M_X(t) = e^{\frac{t^2}{2}}
\end{align}
となる．これをマクローリン展開すると
\begin{align}
M_X(t) = 1 + \frac{1}{2}t^2 + \frac{1}{8}t^4 + ...
\end{align}
となるため，4回微分すると，
\begin{align}
\mu_4 = M_X''''(t) = 3
\end{align}
となり，尖度はなので答えは0である．
Atcoder ABC257 振り返り
A - A to Z String 2【AC】
文字と数字を変換するにはordとchrを使います．Aはunicodeで65なのでそれに1ずつ＋していくとBCD...と文字と用意できます．
N, X = map(int, input().split()) ans = "" for i in range(26): ans += chr(65+i)*N print(ans[X-1])
B - 1D Pawn【AC】
Q回全てシミュレーションします．一番右にいたり隣にコマが存在したらcontinueします．
N, K , Q = map(int, input().split()) A = [int(i) for i in input().split()] L = [int(i) for i in input().split()] for i in range(Q): ind = L[i] - 1 if A[ind] == N: continue if ind < K-1 and A[ind] + 1 == A[ind+1]: continue A[ind] += 1 print(*A)
C - Robot Takahashi【AC】
Wはソートしても問題無いことを利用します．ソートするときSの大人か子供かの情報も必要なので辞書を用意し大人と子供の人数を数えます．辞書にしているのは同じ体重が複数人いたときにそれぞれ人数を加算できるようにするためです．
W=sorted(W)として，f(X)のXをX
N = int(input()) S = list(map(int, list(input()))) adult = S.count(1) child = S.count(0) W = [int(i) for i in input().split()] dic = {} for i, w in enumerate(W): dic.setdefault(w, {0:0, 1:0}) dic[w][S[i]] += 1 W = sorted(set(W)) ans = adult a = 0 c = 0 for w in W: c += dic[w][0] a += dic[w][1] ans = max(ans, adult - a + c) print(ans)
シェル・ワンライナー160本ノック week3 問題5~問題11
問題5
まずntp.confを表示します．
$cat ntp.conf # /etc/ntp.conf, configuration for ntpd; see ntp.conf(5) for help driftfile /var/lib/ntp/ntp.drift # Enable this if you want statistics to be logged.
次に1列目がpoolである行のみを出力します．
$ cat ntp.conf | awk '$1=="pool"' pool 0.ubuntu.pool.ntp.org iburst pool 1.ubuntu.pool.ntp.org iburst pool 2.ubuntu.pool.ntp.org iburst pool 3.ubuntu.pool.ntp.org iburst pool ntp.ubuntu.com
これの2列目の値がサーバーの名前らしいので2列目を出力します．awkのprintを使います．
$ cat ntp.conf | awk '$1=="pool"'| awk '{print $2}' 0.ubuntu.pool.ntp.org 1.ubuntu.pool.ntp.org 2.ubuntu.pool.ntp.org 3.ubuntu.pool.ntp.org ntp.ubuntu.com
問題6
man seqしてseqの仕様を見るとseq [OPTION]... FIRST INCREMENT LASTとあるので，seq 5 -1 1とすれば，
seq 5 -1 1 5 4 3 2 1
と逆順で表示されます．これを使えば
$ seq 5 -1 1 | awk '{for(i=1;i<$1;i++){printf " "};print "x"}' x x x x x
となります．（別解4を自力で求められました）
問題7
awk -F
awkにFのオプションを付ける事で列の区切り文字を空白から変更できます．
$ echo "sarasara" | awk -Fr '{print$1, $3}' sa a
sarasaraという文字列をrで区切ることによりsa, asa, aとなり，$1と$3をprintするのでsa aとなります．
NF
NFで列数を表します．
$ echo "sarasara" | awk -Fr '{print NF}' 3
sa, asa, aと区切られるのでNFは3です．これを$()で加工と変数を動的に指定することが出来ます．
$ awk -F: '{print $(NF-2)}' access.log 22 02 14 13 09
別解として，文字列を切り出す方法を調べたので紹介します．
substr
awkにはsubstrという文字列を切り出す関数があります．substr(切り出したい文字列，切り出す位置，切り出す文字の長さ)とします．access.logについて，午後の情報があるのは全て4列目なので，まず4列目を取り出し，時間の情報は全て14文字目からなので
$ cat access.log | awk '{print $4}'|awk '{print substr($1, 14, 2)}' 22 02 14 13 09
となります．その後は解答と同じようにすると
$ cat access.log | awk '{print $4}'|awk '{print substr($1, 14, 2)}'|awk '$1<12{print "gozen"} $1>=12{print "gogo"}'|sort|uniq -c 3 gogo 2 gozen
問題9
seq -n '//p'
seqに -nというオプションを付けると対象の文字列のみ表示するという処理になります．この対象に'/正規表現1/, /正規表現2/p'とすると正規表現1にマッチする行から正規表現2にマッチする行までを抽出するようになります．
今回の問題のように時系列順に並んだファイルなら，時刻を正規表現で表し，時刻aから時刻bまで抜き出すということが出来そうです．
$ cat log_range.log | sed -n '/24\/Dec\/2016 21:..:../, /25\/Dec\/2016 03:..:../p' 192.168.77.248 - - [24/Dec/2016 21:12:20] "GET / HTTP/1.0" 200 4294 192.168.152.143 - - [24/Dec/2016 22:06:19] "GET / HTTP/1.0" 200 7255 192.168.6.132 - - [24/Dec/2016 23:00:42] "GET / HTTP/1.0" 200 4298 192.168.222.3 - - [25/Dec/2016 00:03:23] "GET / HTTP/1.0" 200 8547 192.168.101.95 - - [25/Dec/2016 01:01:40] "GET / HTTP/1.0" 200 8488 192.168.141.18 - - [25/Dec/2016 02:15:52] "GET / HTTP/1.0" 200 4533 192.168.110.169 - - [25/Dec/2016 03:06:54] "GET / HTTP/1.0" 200 3461
問題10
解答の正規表現が複雑なので1つずつ解説します．
^は先頭の文字を表すので，^##は先頭が##の文字となります．+は直前の文字が1個以上ある場合にマッチします．つまり +は空白文字が1個以上存在する文字になります．今回の場合## Aや## Aは対象の文字になり得ますが，A##や##Aは対象の文字にはなりません．
.は任意の文字，*は0回以上繰り返しになります．つまり.*はなんらかの文字(文字がなくても良い)となります．それを()でかこっているので^## +(./)は先頭は##でその直後空白が1つ以上ある文字列で，空白後にある何らかの文字列を参照するとなります．
\1\n---について，まず\1は先ほど()で参照した文字が入ります．そして\nは改行文字です．よって/^## +(.*)/\1\n---は^## +(.*)を(.*)で置き換え，改行し---とする処理になります．
問題11
この問題で難しかったのは改行の削除の仕方と改行の入れ方だと思います．今回は改行を削除するという考え方では無く，発言内容が1行しか無いことを利用して2行ずつ並べて出力するxargs -n2を使います．
改行の入れ方は，文字列を$1，改行を\nとしてseq 's/$/\n/とします'．seqを連続して行うにはパイプを繋げるほかに;を使う方法があります．
$ cat gijiroku.txt | sed 's/すず/鈴木/'| sed 's/さと/佐藤/' | sed 's/やま/山田/'| xargs -n2 | sed 's/ /:/'| sed 's/$/\n/' 鈴木:あばばあばば 佐藤:あばばばばばばば！ 山田:びっくりするほどユートピア！びっくりするほどユートピア！ 鈴木:うひょひょひょｗｗｗｗｗ山田ｗｗやまｗｗｗ 佐藤:ひょおお？ひょおお？？？ 鈴木:それでは会議を終わります
;で繋ぐパターン
$ cat gijiroku.txt | sed 's/すず/鈴木/; s/さと/佐藤/;s/やま/山田/'| xargs -n2 | sed 's/ /:/;s/$/\n/' 鈴木:あばばあばば 佐藤:あばばばばばばば！ 山田:びっくりするほどユートピア！びっくりするほどユートピア！ 鈴木:うひょひょひょｗｗｗｗｗ山田ｗｗやまｗｗｗ 佐藤:ひょおお？ひょおお？？？ 鈴木:それでは会議を終わります
