AtCoder Beginner Contest 172 振り返り
C - Tsundoku
注意：numpyの dtype = int は 10 ** 9 以上だとオーバーフロー
通常のintは10**18まで大丈夫なのでこれで計算してappendする方がいい
D - Sum of Divisors
Nまでの約数の個数×数字の和を求めよ．
for i =1, ....N:
for j = 1, ....N:
if i % j == 0 then ans += 1
print ans
で解ける．これを，「正定数jに対し，jの倍数であってN以下の数の総和をg(j)としたとき，g(j)の和」
と読み替えることができる。これは等差数列の和なので元の数列より早く解ける．
計算時間はpythonで1.8s
E - NEQ
長さNの数列 {A}, {B} について，
・{A}, {B}の内部の要素はすべて異なる
・Ai ≠ Bi
を満たすA,Bの数を10**9 + 7で割ったあまりを求めよ
解法：
Aの選び方が SA = M*(M-1)* ... * (M-N+1) 通り
重複しないようにBを選ぶには，次の数列dを解く．
数列 d について，
d[0] = 1, d[1] = M-N,
d[k +1] = d[k] *( M-N+k) + d[k-1] * k
SA * d[N] が答え
Submission #14794920 - AtCoder Beginner Contest 172
F - Unfair Nim
Nimというゲームを行う．
N個の石の山があり，自分の手番に1つの山を選び1からN個の石を回収する．回収できなかったら敗北．
今回は最初に1番目の山から石をいくつか2番目の山に移すことで，後攻必勝にすることを目的とする．できない場合は-1を出力．
解説：
Nimの解き方は
A1⊕A2．．．⊕AN＝0であれば後手が必勝法，そうでなければ先手が必勝法．
A1+A2=S，X = A3⊕A4．．．⊕ANとしたとき，この問題は
a+b = S, a⊕b = X, a≦A1であるような(a,b)が存在するか判定し，存在する場合は最大のaを返せばよい．
「A1以下の非負整数aであってa+(a⊕X) = S を満たすものを求める」ともいえる．
a+b = a⊕b + 2 * (a&b) であることを利用すると（同じ桁の部分と繰り上がり部分），
a&b = (S-X)/2 = D
Dが非負整数でない，あるいはDとXで共通しているビットがあると不成立．
a≦A1をいったん無視して，Xのビットを二分割したものをY,Z （Y&Z = 0, Y⊕Z = X）とすると，
a = D⊕Y, b= D⊕Z は条件を満たす．
a≦A1を満たす最大のaが答え．
最小のaはY=0の時のa=D，これが満たさないのであれば「解なし」．
まずY=0として，Xのビットを降順に取り上げ，「これを入れてもa = D⊕Y ≦A1が成立するか？」がYesであれば入れる貪欲法が有効．
AtCoder Beginner Contest 173 振り返り
B - Judge Status Summary
正）AC x 10
誤）AC × 10
良い子のみんなはちゃんと文字を確認しような！
そもそもデフォルトの掛け算記号は＊なのだから気づくべき
C - H and V
H×Wの行列がある．列あるいは行を選んで塗りつぶすことで，#の数をK個にする．
方針：
最大でも2^6*2^6の4096通りなので，itertools.combinationsで気軽に全探索
ans = 0
for i in range(H+1):
for j in range(W+1):
for n in itertools.combinations(list(range(H)),i):
for m in itertools.combinations(list(range(W)),j):
count = 0
for a in n:
for b in m:
if(C[a][b] == "#"): count +=1
if(count == K):
ans += 1
Submission #14998600 - AtCoder Beginner Contest 173
E - Multiplication 4
N個の数からK個の数を選び，その積を求める．
もっとも大きい積を10^9 +7で割ったあまりを求めよ．
解法：非負の状態を保ちながら積を最大化
正の数を二個，負の数を二個加えれば，非負の状態を保つことができる．
流れとして，Aを読み込みsort() したのち，
①a. Kが奇数の場合かつ最大値が負の場合
右から順にかけることで絶対値最小の解が出る
①b. Kが奇数の場合かつ最大値が正の場合
最大値をかける．以降，K-1については偶数と同じように扱える
②Kが偶数の場合
並べ替えられたAについて，右側2つと左側2つの積を比べ，大きいほうをかける．
これを K//2 回分行うことで，K個選んだ際の最大の積が求まる．
Submission #15061788 - AtCoder Beginner Contest 173
別解：最後に符号を合わせる
絶対値の順にソートして，大きい順にかけた後，負であれば
・正の数を一つ除き，負の数を一つ加える
・負の数を一つ除き，正の数を一つ加える
取り除く要素はなるべく小さく，加える数はなるべく大きいほうが良い．
片方の操作しかできない場合に注意．
F - Intervals on Tree
N頂点からなる木を描き，1≦L≦R≦Nとする
L以上R以下の頂点からなるSについて，部分グラフがいくつあるかを f(L,R)とする．
これをすべてのL, Rについて足し上げる．
解法：各辺が何回数えられるかを考えれば良い．
選び方は最大で N * (N+1) * (N+2) // 6
各辺（u,v） (u < v) が選ばれるごとに，u以下のLとv以上のRに影響
1回ごとに，u*(N - v+1)を引けばよい
Submission #15090381 - AtCoder Beginner Contest 173
AtCoder Beginner Contest 168 振り返り
D - .. (Double Dots)
N本の部屋，M本の通路を持つ洞窟
洞窟内の各部屋から外に出るための最短ルートを進む際，次に向かうべき部屋を出力
達成できない部屋がある場合は"No"を出力
graph = [ for _ in range(N+1)]
graph[a].append(b)
graph[b].append(a)
これによって各部屋がどの部屋に繋がっているか書ける
入力1でのgraphは
[, [2], [1, 3, 4], [2, 4], [3, 2]]
幅優先探索の実装
queue = deque([1])
signposts = [0] * (N+1)
signposts[1] = 1
while queue:
u = queue.popleft()
for v in graph[u]:
if not signposts[v]:
signposts[v] = u
queue.append(v)
（入力１の処理例）
部屋1について
…
部屋2について
2からは1,3,4に移動できる
1については既出
3について，signpost = 2
4について，signpost = 2
queueには[3,4]が格納される
…
部屋3について，部屋4について…
全ての部屋に入っているかどうかは
if all(signposts[2:]):
print("Yes")
print("\n".join(map(str,signposts[2:])))
で確かめられる
・参考
Submission #13358850 - AtCoder Beginner Contest 168
E - ∙ (Bullet)
N匹のイワシについて，それぞれステータスA,Bが設定されている
この中から，Ai・Aj + Bi・Bj ＝ 0を満たす組み合わせが存在しないように，イワシを選ぶ方法は何通りあるか？
この問題で重要なのは，
イワシの「傾き」Ai/Biについて，A,Bのパラメーターの範囲が広く精度が足りないこと，
である
そこで行うこととして，まず「傾き」を既約分数の有理数で表す（具体的にはA,Bのgcdで割り，a,bで表現）ここでの出現回数をCounterで数え上げる．
例): Counter({(1, 2): 1, (1, -1): 1, (2, -1): 1})
最初に(0,0)を別物として扱う．
①「直交」している部分については，直交するところが一緒にならないように選ぶ
各要素 (a, b, v個) について，「直交」(b,-a)しているものがw個あったら -1 + 2^v + 2^w 通り
(それぞれ片方のみを選ぶ場合から一つも選ばないパターンを引く)
②それ以外の部分については 2^(直交していない要素の数和)
ここから誰も選ばなかった場合1通りを引き，
またこれにA,Bが（0,0）の場合の通りを足す（個数分だけ足す）
Submission #13414936 - AtCoder Beginner Contest 168
F - . (Single Dot)
草原に柵がおいてあり，この中で牛が動ける範囲を求める
方針：
線分のある座標だけ残し，圧縮座標に変換
壁の座標も考慮して2倍のグリッドを作成することで，DFSで解きやすくなる
DFSの例
while q:
x, y = q.pop()
if not x or not y:
print("INF")
sys.exit()
ans += (X[x + 1] - X[x]) * (Y[y + 1] - Y[y])
if x and not wallx[x][y] and not cow[x - 1][y]:
cow[x - 1][y] = True
q.append*1
if y and not wally[x][y] and not cow[x][y - 1]:
cow[x][y - 1] = True
q.append*2
if x + 1 < n and not wallx[x + 1][y] and not cow[x + 1][y]:
cow[x + 1][y] = True
q.append*3
if y + 1 < m and not wally[x][y + 1] and not cow[x][y + 1]:
cow[x][y + 1] = True
q.append*4
圧縮座標の面積を足した後，上下左右方向に進む
x,yのどちらかが見つからない（つまりどちらかの次元で開いている）なら，答えは無限大
参考：
セルフお悩み相談コーナー① ～年齢と能力編～
大して成長していないのに周囲に指摘されなくなっていくのがつらい。
子供のころは周囲がああしろ，こうしろとうるさかった。失敗したらこってり絞られた。今思えば期待の裏返しであったと思う。
今はというと，失敗してもどうにも甘い。「まあしょうがないよね」「頑張ったんだからいいじゃん」とか。
おそらく自分が年齢を重ねた以外にも社会のが変化していったことによる理由があって，大きく分けると二つほど理由があると思う。
・「成功」の多様化とともに「失敗」の定義が難しくなった
サービス業が大きく発展したことにより，20年前は存在しなかった仕事が次々生み出されている。「そんなの上手くいかない」と断言できる根拠が減っている。
・広く浅く繋がるのが容易な時代になり，特定の他人への興味が薄れた
たとえ今の人間関係が悪かろうと，別の場所への移動が楽な時代になった。SNSなどで自分と同じような趣味を持つ人を見つけるのも楽になった。
総じてみると選択肢が増えたことによって引き起こされている。選択肢は多いほうが良いというのは揺らがないが，選択肢が少なかった時代と比べると迷うことも増えるのだろうね。
さて，自分が成長してないのに指摘されない，見限られている気がする気持ちに対する解決法は，自分自身を評価してやることだろうか。
特に主観的な評価ではなく，数字として残るような相対的な結果を残していこう。成果物があるとなおよいね。
今すぐやりたいものがなくても，比較的得意なこと，やったあとに後悔しないこと，忌避間がないことで結果が残ることを探そう。
この年齢になったらもっといろんなことができるようになっていると思っていた。
驚くべきことに，昨日と今日は地続きである。
ある朝目が覚めたら異能力に目覚めることもなく，空から女の子が降ってくることもない。
だから君が今，思っていたほどできないのは，過去の君がそれらのことに注力してこなかったからである。
これは責めるわけではなく，ただ事実を述べているだけである。
君は未来の自分の姿の想像をして期待報酬だけ受け取り，しっかりとした計画や，絶え間ない努力についてはおろそかにしていたのではないか？
今から言えることは一つ。「1番を目指せ」。ナンバーワンはすなわちオンリーワンだ。2位以下に価値はない。
このままだと言葉がきつすぎるので誤解なきように補足すると，特定の一分野のみを指しているわけではない。○○だけでは1番になれなくても，××との合計なら誰にも負けないとか。自分自身の上位互換と勝負したら，当然上位互換が選ばれる。だから，差別化を図って自分自身を売り込め。合わせ技を駆使して，自分が一番になれる分野の掛け合わせを探せ。ライバルがいない分野を探すのもいいだろう。
「あれもこれも」はできなかったかもしれないが，「この分野ならできる」というものに時間をかけよう。
今から何かを始めるにしても，年を取りすぎている。
君は今が一番若い。今始めれば，10年後の君は経験年数10年だ。10年前に何かを始めた君に感謝するよ。
最年少記録みたいなRTAには間に合わないかもしれないけど，歴史に名を残すくらいであれば全然可能性はあるよ。
どうにも書いていると「出典」「根拠」「参考文献」が欲しくなるな。
AtCoder Beginner Contest 167 振り返り
C - Skill Up
N冊の本でM個のスキルをX以上にするための最小コストを求めたい
実装：深さ優先探索
def func(cost,a,i):
if min(a) >= X:
return cost
elif i == N:
return MAX
total_A = [x+y for (x,y) in zip(a,A[i])]
return min(func(cost + C[i],total_A,i+1),func(cost,a,i+1))
全部足し，コストを計算
行き止まりのMAXじゃないほうが選ばれる
Submission #13218188 - AtCoder Beginner Contest 167
F - Bracket Sequencing
N個の文字列Sを連結して括弧列を作成する
括弧列以外の部分を記録し，
")" の数と"("の数，どちらが多いかで2グループに分ける
先に"("が多いグループを，")"が少ない順に並べ，
その後に")"が多いグループを，"("が多い順に並べる
途中で")"に対応できるほどの"("が並べられなくなったら"No"，括弧の数が異なっていても"No"
それ以外を"Yes"とすればよい
AtCoder Beginner Contest 171 振り返り
F - Strivore
「好きな英小文字 文字を好きな位置に挿入する」という操作を文字列 にちょうど 回繰り返してできる文字列は何通りあるでしょう？
答えは非常に大きくなる可能性があるので、 で割ったあまりを出力してください。
- は 以上 以下の整数
- は英小文字からなる長さ 以上 以下の文字列
解法： 冒頭から，文字列の内最初のものが含まれるところを探す
Snが i+1番目にあるとすると，
S1 ~ S(n-1) までの位置の決め方 iC(n-1)
それ以外の文字の決め方
25^(i-n+1) * 26^(|S| + K - i -1)
これをi = n-1 ~ |S| + K - 1まで足す
「別解」
M = |S| + K 個に文字を割り振ることを考える
25^K * MCK
ただしこれはSnの右側に Snの文字と同じものが入る場合を考慮していない
・1個の場合
・同様に，K個の場合までを足し合わせる
Submission #14574647 - AtCoder Beginner Contest 171
・参考
AtCoderでNumbaが使えるようになり，計算の高速化ができるようになった（計算速度上位は皆使ってる）
AtCoder Beginner Contest 170 振り返り
D - Not Divisible
数列の中で，他の数に割られない数の個数を求める
全探索だとTLE
・解法
サイズ Amax の 配列 dpを作成，0で初期化
dp[Ai] = 0 の時，dp[Ai] += 1
Aiより大きいAiの倍数yについて，dp[y] = 2 にする
これによりdp[Ai] == 1である数は一回のみ登場かつ他の数の倍数でもないので，これを満たすものを数えれば答え
このように同じ値について処理を複数回行わないようにすることで，O(Amax log Amax + N log N) で解ける
E - Smart Infants
N人の幼児がレートAを持っていて，幼稚園Bに所属
この状態でQ回転園を繰り返した際，各幼稚園の最高レートの内，最低レートを出力する
解法：
以下のデータを管理
① 園児が所属する幼稚園の番号
② 各幼稚園のレートの順序つき多重集合（幼稚園一つにつき一つ）
③ 各最強園児のレートの順序つき多重集合（全体で一つ）
各ステップでは，
③について
・最強園児のレート集合から，転園する園児のレートを削除
→転園した園児が所属していた幼稚園の最強園児のレートを挿入
・園児が転園した先の幼稚園の最強園児のレートも同様
②について
・転園する園児の元の幼稚園から転園する園児のレートを削除 ＆ 転園した先に挿入
①について
・転園する園児の所属する幼稚園の番号を更新
この状態で，③のもっとも小さい値を出力すればOK
計算量O(NlogN)
実装：
集合を扱うset() と優先度付きキューを扱うheapqを利用する
F - Pond Skater
/ 
アメンボが池を1~Kマス，スケートする
出発点から目標点まで何回分の操作でたどり着けるか？
現座標と深さをキューにまとめ，以下の操作を行う
・各座標から上下左右4方向について，行き止まりor重複 or Kマス進むまで盤面を探索，リストに座標一覧をまとめる
・盤面の上記座標位置の点をdepthで更新，探索した座標すべてに対応するキューも更新
（この時ゴールについたらそれを出力）
上記の操作で一回分，これをキューが尽きる（たどり着ける点すべて到達する）までやり，届かないなら-1を出力
実装：
盤面は囲むと便利
board = [['@']*(W+2)]
for i in range(H):
board.append(['@'] + list(input())+['@'])
board.append(['@']*(W+2))
board[ys][xs] = '#'
キューを使用する際はdeque（両端キュー）を使うと良い
from collections import deque
Dequeとリストの使い分けについて
dequeは両端へのアクセスが高速，一方中央付近へのアクセスは遅い
参考
