tooh’s diary

半角全角、常体敬体が入り乱れるカオス

復習 3/26, 3/27

atcoder.jp

桁DP的な発想 解説読んでパッと理解できなかった

atcoder.jp

これも桁DP的発想

atcoder.jp

提出した後で「2,8とかの組み合わせの時無理じゃね?」とか気付く。ちゃんと考察をしましょう。

atcoder.jp

グラフの用語を知った。
・直径:一番遠い点間の距離
・二部グラフ:二つのグループに分けられるグラフ。グループAはグループBの頂点としか繋がっておらず、逆も然り。例えば三角形に頂点が並んでいるグラフは二部グラフではないが、四角形に並んでいたら二部グラフ。二部グラフの時、隣接する頂点のグループ番号を偶数、奇数、偶数、奇数……と交互にできる。




atcoder.jp

とにかく桁数がデカけりゃデカいほど強いので、それを目標にしてまずはDPで「マッチ棒ビッタリ使った時に最大何桁作れるか?」を求める。そしてそれが求まったら、dpの最後から遡ってどういう数字を各桁に割り当てればいいかを求める。賢い。

atcoder.jp

結局は高校数学。1<=i<=kのそれぞれのiに対して、(n-k+1_C_i)*(k-1_C_i-1)を求めてあげればいいだけの話。考え方は「最初に赤いボールn-k個を並べて、①その間のi個のどこにボールを入れるか、②その場所に何個のボールを入れるか、の二つをかけたもの」

逆元の求めかたを、例外処理(例えば4C6なんてのは存在しない)も入れて書き直した。

import math
mod = 10**9+7
def comb(p,q):
    if p >= q:
        a = math.factorial(p)%mod
        b = math.factorial(q)%mod
        c = math.factorial(p-q)%mod
        return ((a*pow(b*c, mod-2, mod))%mod)
    else:
        return 0

どうでもいいけどn=10**3くらいだったらpythonの方が早そう


atcoder.jp

二分探索と、「二つの配列の各要素を掛け合わせた時の最大値をできるだけ小さくするにはどう掛けあわせるのが最適?」っていう問題をちゃんと考える。
二分探索で値を見つけるコードを覚えとこう。

n,k = map(int,input().split())
A = list(map(int,input().split()))
F = list(map(int,input().split()))
A.sort()
F.sort()
F.reverse()
t = sum(A)
ok = 10**12
ng = -1
if t <= k:
    print(0)
else:
    while abs(ok-ng) > 1:
        cur = 0
        mid = (ok+ng)//2
        for i in range(n):
            temp = mid/F[i]
            if int(temp) == temp:
                cur += max(0, int(A[i]-temp))
            else:
                if A[i]-temp > 0:
                    cur += int(A[i]-temp)+1
        if cur > k:
            ng = mid
        else:
            ok = mid
    print(ok)

scrapbox.io

(こちらのサイトを参考にさせていただきました。ありがとうございました。)

復習 3/21

atcoder.jp

総和が不変であり、その約数がgcdの候補であることは気づけた。そしてその後に分配するフェーズで余りを横に並べて右側はプラスされる側、左側はマイナスされる側と分けてそれぞれをチェックするところまでは発想できた。
(例)
約数=5で割った余りが1 1 1 1 2 2 3 4
1 1 1 1 2 2 3 / 4 →4はあと1プラスすればmod5=0、左側は全部4に移すので手数が11かかる
1 1 1 1 2 2 / 3 4 →3,4はそれぞれ2,1プラス(合計3)すればmod5 = 0、左は全部移して手数8、よって合計で手数8
1 1 1 1 2 / 2 3 4 →2,3,4 はそれぞれ3,2,1プラス(合計6)すればmod5 = 0、左は全部2,3,4に移して手数6、よって合計で6
1 1 1 1 / 2 2 3 4 →2,2,3,4は手数9、左を移すのは手数4、実際は左を全部2,4に移してmod5=0にして、あとは2を3に移せばいいので手数は6(だが便宜上9にしておく)
みたいなのを最後までやっていき、手数最小になるものがk以下になるものの中で最も大きい約数を出力

答え見てACしちゃったけど割と嘘書いてそうで心配

復習 3/19,3/20

atcoder.jp

数字が「ある」ところを探すんじゃなくて、「ない」ところを探すという発想の転換。難しい。

atcoder.jp

発想の問題じゃなくて、大きな数字を扱うときは注意しましょうねという話。基本的にpythonは大きな数字はメモリの許す限り扱えるけど、例えば

10**100-10
#9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999990

10**100-9
#9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999991

(10**100-9)//2
#4999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999995(これは誤り)

みたいになる。math.floor()とかもそうだけど、大きな数字は割り算(切り上げ切り捨て)の操作に弱いので要注意。


atcoder.jp

0点の人間を除いて、ソートして溢れなかったらK番目にいる人の点数+1、溢れたら0だってさ なんじゃこりゃ

復習 3/16,3/17

atcoder.jp

s = 10**100とかいう良く分からん表現に振り回された感がすごい

やることとしては、いっぱいつなげる方(s)に対し、sのi番目(iは0~len(s)-1、つまりsの各文字)の文字に対して、そこから数えてa,b,c....が次に最短でいつ出てくるかを数える(これをやるときは、sを二つ繋げた文字で考えると良い)。これを前処理として表にしておく。

そして、tの前から見ていって、今見ている文字から次の文字まで何文字あるかな?ってのを、さっき作った表を参考にして調べていく。

言われればははぁんってなるけど思いつかへん......


atcoder.jp

作れない数列の条件(最初が0でない、増加するときに+1でない)はわかったんだけど、数が数えられなかった。

単調増加なら+1、そうでないなら+(要素の値)になる。新規で作るのに要素の値だけの手数が必要になるので、ってことだけどこれ気づかね〜〜〜〜
それっぽいことを考えたけど実装できませんでした。答えは案外シンプルなことが多い。


atcoder.jp

自力ACできたけど、結構ちゃんと条件を押さえないといけなくて教育的だなって思ったので復習

数字iを二進数に直すには、自身より小さい2の累乗の数と&(ビット演算)を取るのが早い(e.g. 24と27は二進数に直すと11000と11011なので、11000&11011は両方のbitが立っている桁のみ1になることから24&27=11000&11011=11000=24となる)
あとNが小さいのでO(2**N)が使える

あとは証言を全部舐めてって矛盾が生じた時点でアウトの処理をすればいいけど、矛盾が出るのは、
①証言者が正直(bitが立っている)かつ、言及先が本当は正直者(bitが立っている)なのに「不親切」と言及している
②証言者が正直(bitが立っている)かつ、言及先が本当は不親切(bitが0)なのに「正直者」と言及している
の2パターンしか存在しないので、この二つを確認すれば良い。

復習 3/15

クッソサボってた しょうがないね

atcoder.jp

s = 'AAA'
s = 'B' + s  #s = 'BAAA'

上の例みたいに、文字列の先頭に新たな文字をくっつけるのは、末尾にくっつけるよりもかなり時間がかかるので注意すべし

atcoder.jp

サイズ付きUF木で一撃 こういうのが普通にできるようにしたい

atcoder.jp

こういう辞書順最小みたいなのは、前回作った奴を再利用するタイプが使える

atcoder.jp

1文字と2文字を扱おうとするからごちゃごちゃになる 2文字を1文字として扱うべし

桁DP

桁DPは、例えば「0以上N以下の数字で、ある条件を満たす数字がいくつあるか」などを数えるのに便利な手法である。

発想が単純なものと、複雑なものの2パターンある。

<単純な方>
例えばこの問題↓
atcoder.jp

?はワイルドカード(0~9のいずれでもいい)の時、?5?という形をしている3桁の数字で、13で割って5余るような数字はいくつ存在するかを数える。

上から順に数字を見ていく。まず、「n桁目を見たところまでで、13で割って5余る数字は何通りか?」を管理するために、「n桁目を見たところまでに13で割ってi余る数字」をdp[i]とする配列dpを考える。

例えば?5?であれば、一番左(最初)の桁が?なので、dp = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0]となる。(?には0~9が入るため、ここまでを13で割った結果がdpになる)
次に、真ん中の桁が5になるので、?5を13で割った余りは、dp = [1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1]となる。(例えば、dp[2]について、25を13で割った余りは12になるので、もともとdp[2]にあった1はdp[12]に移る)
最後に、一番右の桁が?なので、dp = [8, 8, 7, 8, 8, 8, 7, 8, 8, 8, 7, 7, 8]となる。dp[5]は、すべての0~12のiについて、(10*i+j) % 13 == 5となるようなj(つまりワイルドカードの?)を試し、その場合の数を加算してあげればいい。

その他の例
atcoder.jp


<複雑な方>

例えば「N以下で4の入った数字はいくつありますか?」という問いかけで、N=50であれば、十の位を1~9まで全部見ても、十の位で弾けるから簡単だが、N=1234とかだった場合に、千の位が1だった時に、単純にdpを作ろうと思っても「1100」と「1200」で扱いが変わってきたりする。(前者は十の位がなんでもいいけど、後者だと十の位の動きに制限が出る)

そういうのを管理するために、単純なdpではなく、
dp[今見ている桁][Nよりも明らかに小さいか、同じか][すでに4が登場しているか]
という配列で管理するのが良い。これを用いて遷移を場合分けしていけばいいんだけど、かなり面倒。

atcoder.jp

abc007.contest.atcoder.jp

atcoder.jp

復習2/6,2/7

atcoder.jp
<ずる>
O((HW)**2)とは分かったものの一個だけTLEが取れない。全部道である場合のみ特例で除外したら通ったけどこれPythonの正攻法はなんなんやろね。

atcoder.jp
<解説AC>
ロボットアームの動ける範囲の右端でソート→右端が小さい方から順番に、次のアームの左端が範囲に引っかかってたら入れない、大丈夫なら入れる、を繰り返す。右端を常に更新して管理しておくこと。

atcoder.jp
<凡ミス>
発想はあってたのに計算順序をミスったらWAが取れず1時間溶けた。たかが掛け算・割り算の順序と侮ってはいけない。次からはこういうことがないようにする。

atcoder.jp
<解説AC>
問題文の意味が理解できなかった。最初に与えられているのは「全点間の最小距離」である。
一回ワーシャルフロイドっぽいことをしてみて、与えられた全点間の距離のデータより小さくなってしまう(三角不等式において、a+b < cとなってしまうような状況。ここでa,b,cは全て「最短距離」であるはずなので、a+bがc未満になってしまうと都合が悪い)ケースが出てきてしまったら、その時点で調査を打ち切る。
a+b == cとなるケースにおいては、迂回した場合と直接向かった場合の距離が等しい→直接向かうような辺は削除してもオッケー(というか削除するべきで、なぜなら迂回した方が回れる点が多いので)なので削除。
ここで気をつけるべきは、一回削除したら「迂回するケース」の探索を打ち切ること。なぜなら、探索を続けてもう一つでもa+b == cとなるケースが出てきてしまった場合、削除すると決めた辺をもう一度消す事になってしまうから。

チュウニズム 15.75になりました

タイトルの通りです。
f:id:saguh:20200109222600j:plain

NAOKIの神威リミが収録されたのでやってきたら意外に出来たので、その勢いでレートを15.75に乗せてきました
f:id:saguh:20200109222529j:plain
f:id:saguh:20200109222543j:plain
Surrogate Lifeはいい曲


4000クレも突っ込んでました
f:id:saguh:20200109222618j:plain

ベスト枠は以下の通りです
f:id:saguh:20200109222659p:plain
f:id:saguh:20200109222724p:plain

ベ枠が15.74になってからもう2ヶ月が経ち、なかなか既存の13+に歯が立たなくて悔しい思いをしてきました(しかもレートを簡単に盛ることができない)が、ようやっと一つ目標を叶えることができました

思えば15.5になったのも去年の4月なんですね 0.25上げるのに9ヶ月かかったのか......

お金もかかるし時間も足りないので流石にもうウニ引退ですね 12月にボルテに手を出してみて、魔騎士までは取れたんですけどこれもいつまで続くのか 

今年の総括

一年のまとめ


1月

  • まあなんだかんだテストに向けて頑張ってた気がする

2月

  • 小説一作目を販売開始する

3月

  • 金恋カフェに行く
  • 小説二作目を発表

4月

  • ウニのレートが15.5になる

5月

6月

7月

  • オタクを家に泊める メイドインアビスを観る
  • オタクとディズニーに行く ソアリンよかったわね

8月

  • ISに内定する これが終わりの始まりだとは夢にもおもわず……
  • DDRやり始める 結局一ヶ月くらいしか続かなかった
  • 小説三作目を発表 12月までの純利益は6万くらいに


9月

  • 初めてツイッターのオタクとエンカする ブンブク氏いつもありがとう
  • ウニが突然上手くなり13+の鳥がたくさん出る

10月

  • この頃からだんだん授業がヤバいと思い始める。特にハードウェア構成法は全くついていけなくなり、だんだんと学校に行くのが億劫になる。
  • 統計と最適化に無限にヘイトを溜める

f:id:saguh:20191231171441p:plain

  • そのためかウニに逃げるようになる この月はデバステとかグロクラを攻略できてよかったので気持ちよくなる ベ枠が15.7になる 
  • というか周りの人間が授業関連のこととかアカデミックな話をしているのが耳に入るのがとてもストレスになり、だんだん友達を作ろうとしなくなる
  • 数学1Dで周囲の人間が不快に思えてくる 11月から行かなくなる
  • バカデカ台風が来てウケる 翌日は姉の結婚式でした
  • 星乃珈琲店のスフレパンケーキにハマる

11月

  • 創作用の垢を消す また12月に作り直すことになるんですけど
  • 実験が全くわからなくなりさらにうつ病が加速する C言語不可能
  • 無 真剣に転学部を考え始めるがどうせ死ぬならここでいいやと思い諦める

12月

  • 生物情報2もだるくなってくる もう死のうかな
  • ボルテを始める 魔騎士になる
  • 結局ウニは伸びず ベ枠は15.74でした
  • ずっと販売用の小説書いてた

やったこと・達成したこと

  • 理情に内定した
  • 小説で小銭を稼ぐようになった

来年頑張りたいこと

  • 今年よりいい一年にできたらいいな

アルゴリズムとデータ構造 第5章(有向グラフ[最短経路/トポロジカルソート])・第6章(無向グラフ[最小全域木])

第5章

5.1 ダイクストラアルゴリズム

ある1つの頂点から、各頂点に向かう最短経路を求めるアルゴリズム
コストが非負の時のみに動作することに注意。頂点の数をN、辺の数をEとして、O(N**2)とO((N+E)logN)の2つのやり方がある(正直N**2の方は競プロ向けではない)。前者は完全グラフ(頂点の数Nに対し、辺の数がN**2)のような「密なグラフ」に有効。後者は、例えばE=N**2の時O(N**2logN)になり、辺の数が多いと前者よりも時間がかかってしまうデメリットがあるため、「疎なグラフ」(頂点と辺の数がほぼ同じ。この場合O(NlogN)程度になり、O(N**2)より計算量が小さい。)に有効。

O(N**2)の方はわかりやすい実装。全ての頂点について、それを経由して目的の頂点まで行くことがコストの節約につながるかを判定する。頂点を選ぶのにO(N)、それを経由して経路が短くなるかの判定を残りの頂点について確認するのにO(N)(これは内側のループ)なので、O(N**2)かかる。
用意するべきは、頂点i,j間の距離が入った二次元配列cost[i][j]、それに加えて、その頂点を途中で通過するかどうかを判断したか否かを持っておく真理テーブル、そして、最短経路が入るコストテーブルC[i]。
まず、出発点から直接行ける頂点についてコストテーブルを更新し、真理値表のスタートのところを通過済みにしておく。それから、まだ途中の経路として検討していない頂点の中で、コスト最小なものを取り上げ、それを経由した方が果たして距離が短くなるかを、すべての点について走査していく。これを、全ての頂点が途中に通過するかどうかを判定し終えるまで続ける。

O((N+E)logN)の場合もだいたいO(N**2)の時と同じ考え方で、全ての頂点が途中に通る点として考慮されるまでループを回す、というやり方をとる。ただ、頂点の管理にヒープを使うという違いがある。
用意するべきは、i番目の要素に頂点iからjに向かう経路のコストdが入ったリスト[d,j]を、N個の頂点全てについて集めたリストe。それに加えて、その頂点を途中で通過するかどうかを判断したか否かを持っておく真理テーブル、そして、最短経路が入るコストテーブルC[i]、さらに、[頂点Vまでの最短距離,Vの名前]というリストが入ったヒープが必要になる。
まずヒープの最小要素(つまり、最短距離d[V]が最も短いVのリスト[d[V],V])を取り出し、頂点Vが経路として考慮済みであれば(真理値表を見て検討)それを捨てる。そうでなければ、Vを経路として考慮済みにし、e[V]の要素の中で、Vから次に向かう頂点e[1]が経路として未検討であれば、[e[0]+d[v],e[1]]をヒープに加えてe[1]を通過点として検討する候補に入れておく。このヒープが空になるまで操作が続く。
教科書にはコストの更新のところにif文が使われているが、これは取り出して経路として検討済みになった頂点と繋がる頂点に対して比較を行っている。距離で頂点をソートするとかいう不自然なことをしているからこんな風になっているのだが、実際はもっと単純に上記の実装をして、頂点として考慮したところだけ最短距離を更新していけばいい。(計算量自体は変わらないのだが、教科書の方が実装が圧倒的に面倒くさくてなんでこんなのを載せたのかわからない。あと流石にヒープはライブラリ使ってもいいよね......)



練習用問題
D: トレジャーハント - AtCoder Beginner Contest 035 | AtCoder
提出したコード(O(N**2)の方。N=10**2くらいのケースではACもらってますが、流石にN=10**5ではTLEします。32,43行目の不等号にイコールがつくことに注意。あと37,48行目のコストが逆になっていることに注意(一方通行であるため)。)
Submission #8640764 - AtCoder Beginner Contest 035 | AtCoder
提出したコード(O((N+E)logN)の方。こっちは上手に書けばN=10**5でもACがもらえる。ポイントはちゃんとダイクストラのマクロを組むことと、頂点の最短経路更新を一回にすること。)
Submission #8641310 - AtCoder Beginner Contest 035 | AtCoder




5.2 フロイドのアルゴリズム

ワーシャルフロイド。計算量はNの3重ループなのでO(N**3)。ある2頂点の距離を入れたリストを、残りの点を経由して通過した際に距離が節約できるかを確かめてまわるアルゴリズムダイクストラが1対Nの関係を求めるものだったのに対し、こちらはN対Nの全ての頂点間の最短距離が求められる。

練習用問題・提出したコード(Python3だとTLEするのでPypyで)。双方向に連結されているので、最初にcostのリストに国iと国jを結ぶ距離cを代入する際、L[i][j] = L[j][i] = cとするように。
D - joisino's travel
Submission #8640345 - AtCoder Beginner Contest 073

練習問題↓(普通のワーシャルフロイドをやるだけじゃなくて、頂点iからiへの移動コストをちゃんと0に初期化すること、そしてそれが負になったら負の閉路が存在することを判定する。cost[i][i] < 0だけで閉路判定できるの楽だね!)
Aizu Online Judge

v,e = map(int,input().split())
cost = []
for i in range(v):
    T = [float('inf')]*v
    T[i] = 0
    cost.append(T)
for i in range(e):
    a,b,c = map(int,input().split())
    cost[a][b] = c
for k in range(v):
    for i in range(v):
        for j in range(v):
            cost[i][j] = min(cost[i][j], cost[i][k]+cost[k][j])
flag = True
for i in range(v):
    for j in range(v):
        if cost[i][j] == float('inf'):
            cost[i][j] = 'INF'
        elif i == j and cost[i][j] < 0:
            flag = False
            break
if flag:
    for i in range(v):
        print(' '.join(map(str,cost[i])))
else:
    print('NEGATIVE CYCLE')


5.3 有向グラフの探索(トポロジカルソート)

閉路のない有向グラフを、順序関係でとらえなおしたものをトポロジカルソートと呼ぶ。(その順番は一意に定まるわけではない。)
受け売りの説明だが、「例えばある講義A,B,C,D,Eをとるときに、BはAとEを履修していなければならず、AとDはCを履修していなければならず、EはDを履修していなければならないとした時に、どういう順序で講義を履修すればいいか?という関係を考えたもの(ここではC→A→D→E→B)」ということらしい。

まず、それぞれの頂点に入る矢印の本数をカウントするリストins[i]、それから頂点iから向かう矢印の行き先を入れたリストouts[i]を用意する。標準入力でグラフを受け取ると、まずはins[i]==0となる頂点、すなわち入る辺が存在しない頂点から探索を始める。木でとらえ直せば、これが木の根っこということになる。

入る辺が無い頂点を「入次数0の頂点」と呼ぶ。入次数0の頂点はキューに入る。このキューをQと表すと、Q.popleft()で先頭を取り出し、最終的な答えを入れるリストに入れる。この先頭要素から出る辺の行き先に対して、ins[i]をそれぞれ-1する。ins[i]が0になったら、それは入次数が0になったということなので、Qに入れる。これを順次繰り返し、木の根っこの方から(つまりトポロジカルソートの前の方から)調べていき、Qが空になるまでそれを続ける。

練習問題↓
Aizu Online Judge

from collections import deque

v,e = map(int,input().split())
ins = [0]*v
outs = [[] for i in range(v)]
ans = []
for i in range(e):
    a,b = map(int,input().split())
    outs[a].append(b)
    ins[b] += 1
S = deque([])
for i in range(v):
    if ins[i] == 0:
        S.append(i)
while len(S) > 0:
    cur = S.popleft()
    ans.append(cur)
    for e in outs[cur]:
        ins[e] -= 1
        if ins[e] == 0:
            S.append(e)
for i in range(v):
  print(ans[i])

練習問題↓
D - Restore the Tree
答え↓
Submission #8678690 - NIKKEI Programming Contest 2019
参考ページ↓
トポロジカルソートがわからなかったので調べてBFSで実装したのち、AtCoderの問題を解いてみた。 - Qiita


※実は、有向グラフが閉路を持たないことと、トポロジカルソート可能(トポロジカルソートした時に、要素数が元のDAGの要素数と一致する)であることは必要十分条件になっている。
有向グラフの閉路検査の問題↓(トポロジカルソート可能かだけを判定すればよい)
Aizu Online Judge




第6章

6.1 最小木

プリムのアルゴリズム

ほとんどダイクストラと構築が同じ。最小全域木(最短コストで木の各頂点を回れるようにしたもの)を構築するアルゴリズム。辺の長さをヒープで持っておいて、コストが小さい方から最小全域木を構成する辺として採用し、全部の頂点を見終わるまで続ける。
計算量は、素直な実装(n個の頂点を見て、その内側でn個の各頂点に対して、全域木までのコストを更新する)場合はO(N**2)だが、ヒープを使うことでO((N+E)logN)にすることができる。ただ、これもダイクストラと同じように、後者は密なグラフに弱い。

練習問題↓
Aizu Online Judge

import heapq

n = int(input())
ans = 0
cost = []
for i in range(n):
    L = list(map(int,input().split()))
    cost.append(L)
used = [False]*n
used[0] = True #島0から探索を始める。
edge = []
for i in range(n):
    T = []
    edge.append(T)
for i in range(n):
    for j in range(n):
        if L[i][j] != -1:
            T[i].append([L[i][j],j])
P = T[0]
P.sort()
while len(P) != 0:
    cur = heapq.heappop(P)
    if cur[1] == True:
        continue
    cur[1] = True
    cur[0] += ans
    for e in T[cur[1]]:
        heapq.heappush(P,[e[0],e[1]])
print(ans)


クラスカルアルゴリズム

フロイドのアルゴリズムと並んで簡単なんじゃないか?(嘘かも)これもプリム法と同じく全域木を構築するアルゴリズム
UF木と組み合わせると楽なのでそうやって使う。[頂点A,Bを結ぶ辺のコスト,頂点A,頂点B]を要素として持つリストをまずは辺のコストでソートし、辺の短い方から使っていく。もし頂点Aと頂点Bが同じ木に属していなければ、その辺を木の辺として用いる(頂点A,Bを結ぶ)。属していれば、辺を捨てる。これを全ての辺についてやればいい。よって計算量自体は「辺を全部見るO(E)」と「辺をソートするO(ElogE)」と「UF木を構築するO(?)」になるけど、UF木を構築するのはクソ早くできるので、今回は辺のソートのみが問題になり、計算量はO(ElogE)となる。

練習問題↓
D - Built?
答えのコード↓(各頂点をもう一回インデックスつけ直して10**5までで扱えるようにする。張る辺が隣接する頂点どうしのみ考慮すればいいことから、x,yそれぞれでソートして辺の距離を出し、最大で2*(10**5)本くらいの辺に対してクラスカルアルゴリズムをやってあげればいい。(Pythonだと流石にギリギリね)
Submission #8666576 - AtCoder Beginner Contest 065

練習問題↓
Aizu Online Judge

Logisimで遊んだ

Logisimたらいう回路を作って実際にその挙動を確かめられるシミュレータをインスコしたので、これまでのハードウェア構成法の復習(?)も兼ねて遊んでみた。というか挙動をこの目で確かめられてないのでこの際に確かめてみようってワケ。


作ってみたのはこいつら
・ハーフアダー(HA)
・フルアダー(FA)
・3ビットリプルキャリーアダー
・7ビットスライスアダー
・4ビットバイナリカウンタ
・4ビットジョンソンカウンタ
・4ビットリングカウンタ


※GIFにするのがめんどいので静止画です。すんません。

・ハーフアダー
半加算器ともいう。二つのビットの足し算をして、繰り上がりがおこるかどうかの判定をしてる。下の写真は0+1を計算してる様子。上の方が下位ビットを表しており、演算結果が01(十進法では1)なので上が立ってる。1+1なら結果は10になるので下のビットが立つ。
実装は簡単で、下位ビットと上位ビットの導出をそれぞれ分けて行えば良い。(下位ビットはXOR、上位はAND)
f:id:saguh:20191124023126p:plain


・フルアダー
全加算器ともいう。さっきのハーフアダーの拡張みたいな感じで、これは三つのビットの足し算の結果を返す。ハーフアダーを2つ組み合わせて使うとフルアダーになる(というかこれがハーフアダーの名の由来)。下の写真では1+1+1をしている(出力は11(十進法で3になっている)。
f:id:saguh:20191124025931p:plain


・3ビットリプルキャリーアダー
二進法で3桁の数字(つまり0~7)を表す二つの数字の足し算を行う。流れとしては、まず一の位の足し算を行い、その結果を受けて(繰り上がりも含めて)次に二の位、それから四の位と足し算を行う。繰り上がりの結果を持ち越す為にフルアダーを横に並べて使っているところがポイント。下の画像では7+3(つまり111+010。a1,a2,a3はそれぞれ前者の一、二、四の位。b1,b2,b3はそれぞれ後者の一、二、四の位)を行なっている様子。結果として1010(十進法だと10)が計算されてる。
※最初のFAの入力の一つはGroundに接続(つまり0が入っている)されている。
f:id:saguh:20191124030727p:plain


・7ビットスライスアダー
7個のビットの足し算を行い、その結果を0~7を表すビットとして返す。4つのフルアダーで実現される。
三段構成になっていて、一段目(FA2個)で6つのビットを3つ、3つにわけて足し算を行う。
二段目で、一段目の結果の一の位(2つ)と、最初に足されなかったビット1つの足し算をFAで行う。この出力で一の位が確定する。
三段目で、一段目の結果の二の位(2つ)と、二段目の結果の二の位の合計3つをFAで足し合わせて、二の位と四の位を確定させる、という流れでやっている。
下の画像では6つの1の足し算を行なっている様子。結果として110(十進法だと6)が出力されている。
f:id:saguh:20191124031758p:plain


・4ビットバイナリカウンタ
まずはカウンタのお話から。カウンタはその名の通り「数える」ことができる機構であり、それを回路で実現することを考える。
回路は電気信号のやりとりで動いていて、単位時間あたりのやりとりの回数(もしくはやりとり自体)を「クロック」と呼ぶ。
このクロックを「0,1のスイッチ」とみなして、これのオンオフでカウンタを動かしていくことを基本としている。

バイナリカウンタは、「n個の『ラッチ』と呼ばれる機構を用いて、0~2^n-1までを表現できるカウンタ」である。ラッチは「1ビットの状態を保存できる機構」であり、ここで保存された0,1が、表したい数字のビット列を構成している。フリップフロップとも呼ばれる。(某アイドル育成ゲームの曲ではない)
このバイナリカウンタで用いるラッチは「JKラッチ」と呼ばれるもので、このラッチは2つの入力J,Kがどちらも1である場合、出力(保存された状態)をクロックに合わせて変化させることができる。(クロックが1->0->1->0->1->0->.....と変化すると、出力Qが1->0->1->......と変化する感じ)この性質を用いて、クロックの立ち上がり(01の周期のうち、1になる時)ごとに各ラッチのバイナリの状態を変化させていくのが、バイナリカウンタの基本原理である。

[以下はLogisimの使い方であげた2つめのサイトから引用した。]
一番左のSマークがクロックで、このクロックの立ち上がり(電気が通る=1=薄い緑)で、一番左側のJKフリップフロップが動作します。クロックが薄い緑になるたびに、JKフリップフロップの出力Qが、薄い緑(=ON)または濃い緑(=OFF)になります。

出力Qを次のJKフリップフロップのクロック入力に繋げているのがポイントです。出力Qと出力~Q(Qの否定を表す。図中のQの下にある薄い「0」のところ。Qが1なら~Qは0、Qが0なら~Qは1)が交互になるという事は、入力信号に対してQは1/2でしかONにならなくなります。よって右隣りのJKフリップフロップは1/2の速度の動作になっていきます。

                  • -

以下はバイナリカウンタで2を数えている時の状態。2つ目のラッチだけQが0になっていて、そこだけ(~Q=1より)ビットが立ち上がっている。この後、クロックが再び立ち上がると、1つ目のラッチのQが0になり、~Qが1になることで一の位のビットが立つ。よって、0011(つまり3)を表すことになる。
f:id:saguh:20191124035316p:plain

3の次は4になる。以下の画像は3を数えた後の状態で(クロックが立ち上がって、再び0になった)次にクロックが再び立ち上がると、まず1つ目のQ(出力)が反転し、それが2つ目のラッチのクロックとして機能して2つ目のラッチのQ(出力)が反転して1になる。すると、さらに3つ目のラッチに入るクロックが立ち上がることになるので、3つ目のラッチのQも反転する。よって、1,2つ目のラッチの~Qは0になり、3つ目のラッチの~Qは1になる。以上より、0011だったビットが0100に変化し、4を表すことになる。
f:id:saguh:20191124035939p:plain


↓ほらね?
f:id:saguh:20191124040111p:plain


・4ビットジョンソンカウンタ
ジョンソンカウンタは、n個のラッチで2n個の状態を表現する。例えば、4ビットであれば、0000->1000->1100->1110->1111->0111->0011->0001->0000->......という風な変化を経ることで8つの状態を表すことができる。

構造は、Dラッチ(Dフリップフロップ)というラッチをつなげて作る。Dラッチは入力がDとクロックの二つ(ジョンソンカウンタを作る際には三つだが、これは後述する)と、出力Qの一つからなる。Dが1になったら、次のクロックの立ち上がりで出力Qが1に、逆にDが0になったらQは0になるという、DとQが1クロック分遅れた動きをする。(クロックが0の時、D,Qには影響がない)

ジョンソンカウンタは出力Qをそのまま追って見ていけばよく、ラッチの出力Qが後ろにつながるラッチの入力Dになっている(ム○デ人間とか言わない)。ただ、注意するのは最後のラッチの出力Qを先頭に巻き戻すのではなく、~Qの方を先頭の入力Dにするところである。これをしないと例で挙げたぐるっと一周しなくなってしまう。

下の図では、次に動くのは3つ目のラッチのQである。これからクロックが再び立ち上がることで、入力Dが1クロック分遅れてQに伝わり、その結果として出力を4つ並べると1110になる。
f:id:saguh:20191124050543p:plain

上の図では、Dラッチの二つの入力に加えて下から1が入力されている。実はこれがなくても正常に動作するのだが、これがないとこのカウンタがバグった時に元に戻らなくなってしまう。ジョンソンカウンタはn状態のうち、2n状態しか使わず、残りの2^n-2n個の状態は使われない。
もしジョンソンカウンタの内部状態がなにかの拍子でその使われない状態に遷移してしまった場合、本来実現すべき数字表現ができなくなるループに陥ることが考えられる。(例えば、4ビットの場合、0100->1010->1101->0110->1011->0101->0010->1001->0100->......というループになった場合、これは正常な動作ではない)
これを回避するために、もしこのようなまずいループに陥った時に一旦リセットをかける意味で、Dラッチの下から1が入力されている。これが1になる時、ラッチの出力Qは強制的に0になる(つまりジョンソンカウンタの0000に状態がリセットされる)。
※本当はリセットの時だけ1になるべきで、普段は0になっているべきなんですけど、実際に動かしてみたらここが0だと回路が回らなくなってしまったのでなんか間違えてるのかも?


・4ビットリングカウンタ
n個のラッチでn状態を表現するクソ贅沢なカウンタ。各状態では必ずビットが1つだけ立っており、1000->0100->0010->0001->1000->......と状態が遷移する。

ジョンソンカウンタと同じく、前のDラッチの出力Qを後ろのDラッチの入力Dにするようにつなげて使う。最初のラッチの入力Dは、最後以外のラッチの出力QのNORを取ればよい。なぜなら、最後の出力Qが1になる時以外は必ず、最後以外のどこかのラッチの出力Qが1になっているため、NORの出力は0になり、最後が1になる時だけNORが1になり、最初に入力として1を施すという仕組みが構成されるからである。
また、これもジョンソンカウンタと同じように、バグった時用のリセット手段として、Dラッチの下から1を入力しておく。
f:id:saguh:20191124053500p:plain
上の画像は0001の時の様子。NORが働いて最初のラッチの入力に1が入り、次のクロックの立ち上がりで最初のラッチの出力Qが1になり、1000に移行する。




Logisimの使い方↓
論理回路シミュレータ Logisim の使い方
hajimete-program.com



実際にLogisimで回路を書いている人の様子↓
www.youtube.com


回路関連で参考になりそうなページ↓
daisan-y.private.coocan.jp

risc-vでアセンブリ

2つの整数を受けとり、大きいほうを返す関数maxof2をアセンブリで実装せよ。

int maxof2(int x, int y);


とりあえずmainはこんな感じになる(と思われる)

#include <stdio.h>
//main.cに保存

int maxof2(int x, int y);

int main(){
  int x,y;
  scanf("%d%d", &x, &y);
  printf("%d\n",maxof2(x,y));
  return 0;
}

最初のmaxof2という関数を実装するという趣旨の問題っぽい。


以下のどちらでも良い。

    #func.sに保存
    .align	2
    .globl	maxof2
maxof2:
    ble a1, a2, label1
    j label2
    label1:
        mv a0, a2
        ret
    label2:
        mv a0, a1
        ret
.align	2
.globl	maxof2
maxof2:
ble a1, a2, label1
j label2
label1:
  mv a0, a2
label2:
  mv a0, a1
ret

何がどう違うのかわからんけどまあ動いたのでヨシ!!!!!!!!

spike(risc-vのシミュレータ)のインスコ
brew install riscv/riscv/riscv-tools
でできる。

RISC-Vアーキテクチャの環境で利用できるコードを生成するためには、cの場合はただのgccじゃなくてriscv64-unknown-elf-gccコンパイルする(これをクロスコンパイルと言う)。これでRISC-Vアーキテクチャで実行可能なプログラムが生成される。

main.cをアセンブリにかけてそれをファイルにしたい(アセンブリ言語の記述が見たい)ときは、
riscv64-unknown-elf-gcc main.c -S main.c
riscv64-unknown-elf-gcc -S main.c
のどっちでもできる。

で、実行するときは、
$ riscv64-unknown-elf-gcc main.c func.s -o main
$ spike pk main

ってやるとbbl loaderって出てくるので、下に(例えば今回は引数を受け取るので適当に2 3とでも入力すれば)出力が返ってくる(3が表示される)