HaskellのConcurrentについて調べてまとめる (MVar編)
どうもこんにちは.
前回(HaskellのConcurrentについて調べてまとめる (IORef編) - プログラミングのメモ帳➚)の続きです.
今回はスレッド間協調のためにMVarを使う方法について調べたので, まとめたいと思います.
MVar
Haskellにかかわらず, 最近の並行処理はメッセージパッシングでやれみたいなのが流行ってますね (ScalaのAkkaやgolangのchanなど).
MVarはHaskellにおける, 容量1のメッセージボックスのようなものです. MVarを使うことで, スレッド間でメッセージのやり取りを協調的に行うことができます.
複数のスレッドが１つのMVarに対して, メッセージを入れたり取り出したりすることでスレッド間協調を行います.
基本となるAPIはこのような感じ
newEmptyMVar :: IO (MVar a) newMVar :: a -> IO (MVar a) takeMVar :: MVar a -> IO a putMVar :: MVar a -> a -> IO () readMVar :: MVar a -> IO a
型を見ればなんとなく使い方もわかる気がしますね.
MVarを作るにはnewEmptyMVarかnewMVarを使用します. newEmptyMVarは空のメッセージボックスを作り, newMVarは第一引数を初期値としてもつメッセージボックスを作ります.
MVarにメッセージを格納するには, putMVarを使います. putMVar mvar msg で, msgをmvarに格納します.
この際, もしMVarにすでにメッセージが格納されている場合, MVarは容量1のボックスなので, putMVarがブロックされます. 他のスレッドがMVarからメッセージを取り出して空にするまで待ってから, メッセージを格納します.
一方, MVarからメッセージを読み取るには, takeMVarかreadMVarを使用します.
takeMVarはメッセージを読み取り, そのMVarを空にします. readMVarはメッセージを読み取りますが, MVarの中のメッセージはそのまま残します.
ここで, putの時と同様に, takeMVarもreadMVarもMVarにメッセージが格納されていなかった場合, 他のスレッドがMVarにメッセージを格納するまでブロックします.
というわけで簡単なサンプルコード
module Main where
import Control.Concurrent (forkIO, threadDelay)
import Control.Concurrent.MVar
main :: IO ()
main = do
mvar <- newEmptyMVar
forkIO $ do
msg <- takeMVar mvar
putStrLn $ "recv: " ++ msg
threadDelay $ 1 * 10 ^ 6
putMVar mvar "B"
putStrLn "sleep 1"
threadDelay $ 1 * 10 ^ 6
putStrLn "wake up"
putMVar mvar "A"
takeMVar mvar >>= print
実行結果
sleep 1 wake up recv: A "B"
確かにメッセージが格納されるまで takeMVarがブロックしていることがわかります
共有変数としてのMVar
さて, MVarにはもうひとつの使い方があります. 共有変数としてのMVarです.
MVarの特徴として, 誰かがtakeしてからputするまでの間は, 他のスレッドはだれもMVarの中身に触れないという点が挙げられます.
main = do
mvar <- newMVar 0
forkIO $ do
val <- takeMVar mvar
-- 他のスレッドはMVarの中身に触れない
putMVar mvar $ val + 1
...
この特徴はまさにロックの特徴といえます. ロックを取得し解放するまでは, 他のスレッドは同じロックで保護された区間にははいれません.
というわけでMVarは型レベルでロックがついた共有変数とみなすことができますね！(このへんはRustのMutexに似た空気を感じます. どちらも型レベルでロックとそれが保護する中身がつながっています)
型レベルでロックがくっついているので, 中身にアクセスするには必ずロックをとる(takeMVar)必要があり, ロックの取得忘れがありません.
さらに, Haskellは基本的に破壊的操作があまり登場しない言語であることもこのMVarロックにプラスに働きます.
例えば, 連想配列をスレッド間で共有することを考えます. また, ここでは連想配列の実装として, hashtableではなくData.Mapを使用するとします(Data.Mapはimmutableな構造になっていて, lookupはO(log n)ですが, immutableなのでHaskell上で扱いやすいというメリットがあります).
Data.Mapはimmutableなので, 一度MVarから取得してしまえばそれ以降変更される可能性もないため, ロックを保持し続ける必要がありません. そこで, 単なる読み込みの場合は, takeMVarしてすぐにputMVarで戻すだとか, readMVarで読み込むだけにすることで, ロックの粒度を小さくできます.
MVarの中身を書き換えたい場合は, 単純にロックを取得し, 書き換え後の値をputMVarします.
module Main where
import Control.Concurrent (forkIO, threadDelay)
import Control.Concurrent.MVar
import qualified Data.Map.Strict as M
main :: IO ()
main = do
mvar <- newMVar M.empty
forkIO $ do
table <- takeMVar mvar
putMVar mvar table
-- tableを使用する操作
forkIO $ do
table <- readMVar mvar
-- tableを使用する操作
forkIO $ do
table <- takeMVar mvar
-- tableを変更する操作
let newTable = ...
putMVar mvar newTable
このようにMVarとimmutableなデータ構造を組み合わせることで, 粒度の小さいロックを実現することができます.
一方, MVarとmutableなデータ構造(IORefなど)を組み合わせる場合は, たとえ読み込みしかしない場合であっても操作が終わるまではロックを保持しておく必要があることに注意しなければなりません (IORefには前回紹介したようにatomicModifyIORefがあるのでなかなかこういう状況は起こりませんね)
また, RustのMutexと違い, MVarによるロックの模倣(?)はロックの解放を自動的には行いません. したがって例外が送出された場合にロックを開放し忘れるケースがあるので, 注意が必要です.
一旦まとめ
というわけで今回はMVarについて紹介しました. MVarでロックを実現する方に関しては, 散々言われているロックの問題点をそのまま持ってきてしまうのであまり使えないかもしれませんね...
MVarは容量1のメッセージボックスでしたが, HaskellにはChanというものもあります. こちらはgolangのchanにかなり近いもので, 容量の制限がないキューのように働かせることができます. Chanのよみとり専用のスレッドを１つ立てておき, 他の複数のスレッドがタスクをChanに書き込んでいくといったユースケースが考えられますね. こっちのほうが便利そうな気がしてきました.
ロックはいろいろ厄介で, デッドロックとか解放忘れとかの問題がついて回ります. それを解決する１つの方法としてSTMがあるようなので, 次はそれについて調べてみようと思います.
HaskellのConcurrentについて調べてまとめる (IORef編)
こんばんは. Haskell(GHC)で並行処理を必要とするアプリケーションを書いてみようと思ったのですが, 並列処理に関するいろいろについてよくわかっていない部分が多かったので, 調べたついでにまとめておこうと思います.
もし間違い等ありましたらコメントいただけるとありがたいです
Concurrent v.s. Parallel
Concurrentは並行, Parallelは並列と訳されます.
Concurrentは論理的に同時に実行されることで, 実際に複数のタスクが物理的に同時に実行している必要はありません. 実際どうであれ, 同時に実行しているように見えればOKで, 複数のタスクでCPUを細かく交代で使用しながら実行していくといった実行モデルもConcurrentであるといえます.
Parallelは物理的に同時に実行されることです. 必然的に複数のCPUが必要になります. 物理的に同時に実行されているタスクは, 論理的にも同時に実行しているとみなせるので, ParallelであればConcurrentです.
この記事ではConcurrentについて言及しているつもりです.
Haskellのスレッド
Haskellは処理系実装の軽量スレッドを持ちます. OSが提供するネイティブスレッドと違い, コンテキストスイッチ(スレッドの切り替え)のオーバーヘッドが少なく, より気軽に扱えるスレッドのようです. 軽量スレッドといえば Erlang や Golang が思い浮かびますね.(Erlangは軽量プロセスっていうんでしたっけ)
実際にHaskellで軽量スレッドを立ち上げてみます.
まずはスレッドを立ち上げない場合です. (threadDelayは指定したマイクロ秒分スレッドをスリープします)
module Main where
import Control.Concurrent (threadDelay)
sleepN :: Int -> IO ()
sleepN n = do
putStrLn $ "sleep " ++ show n
threadDelay $ n * 10 ^ 6
putStrLn $ "wake up " ++ show n
main :: IO ()
main = do
sleepN 3
threadDelay $ 2 * 10 ^ 6
putStrLn "sleep 2 and wakeup"
threadDelay $ 2 * 10 ^ 6
putStrLn "end"
実行結果
sleep 3 wake up 3 sleep 2 and wakeup end
全体として, 3秒->2秒->2秒とスリープするので7秒ほどの実行時間になります.
つぎにスレッドを立ち上げる場合です
Haskellでスレッドを立ち上げるには forkIO :: IO () -> IO ThreadId を使用します. IO ()を渡すと, それを新しく立ち上げたスレッド上で実行してくれます.
(forkOS :: IO () -> IO ThreadId というものもありますが, こちらはHaskellの軽量スレッドではなく, ネイティブスレッドを立ち上げます)
module Main where
import Control.Concurrent (forkIO, threadDelay)
sleepN :: Int -> IO ()
sleepN n = do
putStrLn $ "sleep " ++ show n
threadDelay $ n * 10 ^ 6
putStrLn $ "wake up " ++ show n
main :: IO ()
main = do
forkIO $ sleepN 3
threadDelay $ 2 * 10 ^ 6
putStrLn "sleep 2 and wakeup"
threadDelay $ 2 * 10 ^ 6
putStrLn "end"
実行結果
sleep 3 sleep 2 and wakeup wake up 3 end
１つのスレッドが3秒スリープしている間に, もう一つのスレッドのスリープが始まるので, 全体で4秒ほどの実行時間になります.
共有変数
複数スレッドによる並行実行を扱うと, どうしても共有変数的なものが欲しくなる場合があります. Haskellでスレッド間共有をしたい場合はいくつかの方法があるようです.
もっとも直感的(手続きプログラミング出身者にとって)で馴染みやすいのは Data.IORef かと思います. IO の世界の内側でのみ読み書きができる"変数"です.
まずは単一スレッドで実際に使ってみます.(以後import などは省略します)
add1 :: IORef Int -> IO ()
add1 v = do
modifyIORef v (+1)
main :: IO ()
main = do
ref <- newIORef 0
v <- readIORef ref
print v
add1 ref
v' <- readIORef ref
print v'
実行結果
0 1
このように変数として中身を書き換えることができます.
これは変数なので, ひとつのスレッドで行った書き換えが他のスレッドにも影響を及ぼします.(Stateモナドのように変数を模倣しているだけではこれはできない)
add1 :: IORef Int -> IO ()
add1 v = modifyIORef v (+1)
spawn :: IORef Int -> IO ()
spawn ref = do
forkIO $ add1 ref
return ()
main :: IO ()
main = do
ref <- newIORef 0
spawn ref
spawn ref
spawn ref
threadDelay 1000000
v <- readIORef ref
print v
データ競合
一方これを複数スレッドで並列に動かすことを考えます. modifyIORef はアトミックではないので,
v の中身を読む
v の中身 + 1 を計算する
v にその結果を入れる
というそれぞれの計算の間に別のスレッドでの計算が割り込まれる可能性がある.
上の例で, spawn ref >> spawn ref >> spawn ref という部分は複数スレッドから一つの変数を同時に変更しようとしている. そのため, 変更が競合し意図しない動作になる可能性がある.
IORefで競合を防ぐ方法としては atomicModifyIORef :: IORef a -> (a -> (a, b)) -> IO b を使用する方法がある.
atomicModifyIORef の第2引数は a -> (a, b) である. これは IORef の中身を引数にとって, (変更後の値, atomicModifyIORefの返り値にしたい値) を返す関数である.
inc :: IORef Int -> IO Int
inc ref = atomicModifyIORef ref (\n -> (n + 1, n))
main :: IO ()
main = do
ref <- newIORef 0
res <- inc ref
v <- readIORef ref
print res
print v
inc はC言語のi++;のような動きをする. 加算する前の値を返し, 変数をインクリメントする.
atomicModifyIORef は名前の通り atomic な操作であり, 分割不可能になるため他のスレッドと処理が競合することがなくなる.
一旦まとめ
長くなってきた & 疲れてきたので一旦きります.
今回はスレッド間共有変数のために IORef を使用し, その変更に atomicModifyIORef を使用することでデータ競合を防ぐ方法を紹介した.
MVar や STM を使用する方法もあり, そっちのほうが良い場合もあるっぽいのでそっちについてもまとめたいと思います.
yukicoder 2015/05/08
yukicoderさんのコンテストに出てきましたー
★から★★★までの四問ということでもしかしたら完答いけるんじゃないかとか甘いことを考えていたのですが...ｗｗ
結果
3完で19位でしたー4問目はTLEの連発で...解法全く思いつけませんでしたねー
ただ前よりはちょっとは力ついてきたのかななんて思ってますｗｗ（甘いかな
復習
No.203 ゴールデン・ウィーク(1) - yukicoder
与えられた2週間の中で最長の連休を求めよという問題ですね！
2週間の情報の与え方が
oxoooxx xxoxxoo
のように一週間ごとにわかれているのでそのまま素直に一週間ごとに入力受け付けるとハマる気がしますｗ
単純に14要素の配列を用意してそこに入れていけば単なる最長の連続区間を求める問題ですね！！
No.204 ゴールデン・ウィーク(2) - yukicoder
いやーやられまくりましたねｗｗランキングを見るとわかるのですが、めちゃくちゃ罠問題という感じでしたｗ
submit回数がすごいことになってましたね全体的に
問題は、先ほどのゴールデンウィークの問題とほぼ一緒なのですが、今回は有給を使うことが出来ます！！幸せっぽいですね
これだけならまあ簡単なのですが...
引っ掛けポイントはこの二週間以外の部分です！
2週間分の平日(x)と休日(o)が分かるカレンダーが与えられます。 この2週間の期間以外は、平日とします。
この文を読み飛ばしているとWAまみれになります。というかなりました...
これさえ見逃さなければ素直にガリガリ数えていくだけですので、実装としてはそこまで難しくはないと思います。
もっときれいな実装や解法があるんでしょうけど、それは追々...
No.205 マージして辞書順最小 - yukicoder
与えられた文字列群の先頭から一文字ずつ選んで組み上げられる文字列のうち、辞書順最小になるものを求めよという問題。
すべての文字列の先頭文字のうち、最小のものを選んでいけばよいっぽいのですが、ひっかかりポイントとして、
az za
というような問題があります。
この場合、a が最小なので
z za
となります。
次の一文字を決定する際に、何も考えずに辞書順最小の文字を考えると
(空) za
となります。
そして出来上がる文字列は azza となります。
正しい答えは azaz ですよね。ここがハマリポイントぽいです。
今回はこのコーナーケースがサンプルにあったので発見しやすかったですね。なかったらはまってたと思います。
No.206 数の積集合を求めるクエリ - yukicoder
わかんなかったー！くそー...
とりあえずナイーブな実装で multiset でAの各要素 - Bの各要素の集合を作り、 0の数が Q = 0の時の解, 1 の数が Q = 1 の時の解, ... というようにしてみました。 解はあっているっぽかったのですが、案の定 TLE ...
此の実装だと O(L * M) かな？ L, M は10 ^ 5 までいくのでこれじゃダメダメですねー...
で、解答見たのですが、解答読んでもよくわからない...ちょっと考えてみます...
まとめ
前よりはまし！すこしだけ！
yukicoder 2015/05/03
今週は土日共に予定があってAtCoderさんもyukicoderさんも出場したかったのですが出来ず...
AtCoder - ARC
今週のAtCoderさんはABCはなかった？ぽくて, ARCに挑むにはまだちょっと力不足かなと思うので, 一旦保留します
yukicoder
というわけでyukicoderさんの方の最初の2問についてだけコンテスト後ですが挑戦してみましたー
No.201 yukicoderじゃんけん - yukicoder
ゆるふわなじゃんけんですね。じゃんけんといいつつ、手は全く関係ないただの数値比較ですｗｗ
ただし、注意しなければならないのが数値の範囲です。10 ^ 1000 までという非常に大きな数字を扱う必要があるので、単純に実装すると落ちます。
今まであんまりこういった入力数値の範囲について注視していなかったのですが、今回ばっちりひっかかって落ちたので今度からはちゃんと見ないとダメですねｗｗ
あ、あと今回はC++を使用してみましたー競技プログラミングとは別件で最近C++をよく利用しているので、その流れでDから一旦変えてみましたー
非常に大きな数値を扱う場合、rubyやpythonであれば自動的にBigDecimalのようなクラスを使用してくれるので素直に実装すればそのまま通ってしまいますが、今回はC++なので文字列として受け取って桁数を比較する方法で実装しました。
#include <iostream> #include <string> #include <vector> #include <functional> #include <algorithm> #define REP(i,n) for(int i;i<(n);i++) using namespace std; int main() { cin.tie(0); ios::sync_with_stdio(false); string a, ap, b, bp, g; cin >> a >> ap >> g >> b >> bp >> g; if (ap.length() > bp.length()) cout << a; else if (ap.length() < bp.length()) cout << b; else { if (ap > bp) cout << a; else if (ap < bp) cout << b; else cout << -1; } cout << endl; return 0; }
C++にもBigInt的なものはあるんですかね？あんまりC++も詳しくないのでわかりませんが多分あるでしょう。どっちがはやいんだろうなー
No.202 1円玉投げ - yukicoder
1円玉を1つずつ投げていって重なったら取り除く、を繰り返した時最後に何枚残っているか、という問題ですね。
最初にとりあえず書いてみた解答がこちら。
#include <iostream> #include <string> #include <vector> #include <functional> #include <algorithm> #include <cmath> #define REP(i,n) for(int i=0;i<(n);i++) using namespace std; bool is_on(pair<int,int> &a, pair<int, int> &b) { double dist = (a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second); dist = sqrt(dist); return dist < 20; } int main() { cin.tie(0); ios::sync_with_stdio(false); int N; cin >> N; int x, y; cin >> x >> y; N--; vector<pair<int, int> > coins; coins.emplace_back(x, y); REP(i, N) { cin >> x >> y; auto p = pair<int,int>(x, y); if (!any_of(coins.begin(), coins.end(), [&p](pair<int, int> &a) { return is_on(a, p); })) { coins.push_back(move(p)); } } cout << coins.size() << endl; return 0; }
投げるたびに、今までのコイン達と重なっているかどうかをチェックし、どれとも重なっていなかった場合は追加する、というナイーブな実装です。これだと答えは合うのですが、TLEになってしまいました。
はじめはx軸方向にソートして、x軸方向で20より離れていればチェックの必要がないので、チェックの必要がある部分を二分探索で求めるという方法を考えたのですが、なんかあんまりうまい方法に思えなくて詰まりまくりました。
0 <= x, y <= 20000 というフィールドを 10 × 10 の細かいフィールドに区切ってチェックするという方法がスタンダードみたいですね！なるほど！
というわけで実装してみたのがこちら
#include <iostream> #include <string> #include <vector> #include <functional> #include <algorithm> #include <cmath> #include <array> #define REP(i, n) for(int i=0;i<(n);i++) using namespace std; typedef pair<int, int> P; const int MAX_N = 100000; array<array<vector<P>, 2000>, 20000 / 10> fields; bool is_on(pair<int, int> &a, pair<int, int> &b) { double dist = (a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second); dist = sqrt(dist); return dist < 20; } int main() { cin.tie(0); ios::sync_with_stdio(false); int N; cin >> N; int x, y; cin >> x >> y; N--; fields[x / 20][y / 20].emplace_back(x, y); int ans = 1; REP(k, N) { cin >> x >> y; P current(x, y); int fx = x / 20, fy = y / 20; bool flg = true; for (int i = -1; i <= 1 && flg; ++i) { for (int j = -1; j <= 1 && flg; ++j) { if (fx + i < 0 || fx + i >= 2000 || fy + j < 0 || fy + j >= 2000) continue; for (auto p: fields[fx + i][fy + j]) { if (is_on(p, current)) { flg = false; break; } } } } if (flg) { fields[fx][fy].push_back(current); ans++; } } cout << ans << endl; return 0; }
10 × 10 のマスに区切って、コインが重なる可能性のある部分(つまり隣接するマス)についてのみチェックをするという実装です。
今思ったのですが、10 × 10 のマスに区切ったらその中に存在できるコインの数って多分1子だけですよね？そしたら array< array<P, 2000>, 2000> でもよかったかもですね！(あ、でもそれだとコインが存在しないときの値がよくわからなくなるなーoption型とか欲しくなる)
まとめ
やっぱり出場したかったなーあのコンテストの感じがないと集中しきれないというかｗｗ
コンテストだと出来ない時にすごく悔しくて次回への勉強のモチベーションがあがるんですよね！だから今後極力出場していこうと思います！
学びとしては、きちんと問題の対象範囲をよく読むことと、検索の範囲を狭めることで解決できる問題の場合はフィールドをマス目状に区切る方法があるということですね！次回に活かします！
【yukicoder】yukicoder open 2015 small - 3完
yukicoder open 2015 small に挑戦してきました！
yukicoderさん主催のコンテストに初挑戦してきました！
人生二回目のコンテストということで昨日よりは緊張もなく楽しめたかな？
言い訳になりますがちょっと同時並行でやらなきゃいけないことがあったので最初の方が変に時間食ってます...
結果
3完で44位でしたー
追記
yukicoderさんのチャレンジなる仕様によって順位が繰り上がりましたｗｗ41位という結果になりましたー
追記ここまで
3問目で変にはまってしまったので辛かった...
けどまぁ解けなきゃいけない問題は解いたかなーという感じ
復習
191
これは一旦全部足して1/10のスレッショルドを求めてから、超えていないものの数を数えるだけですねー
ちゃんとスタートと同時にはじめられて入ればこれはすぐ解けたのになー実際の記録は12分とかかかってますｗｗ
192
合成数を求める問題です！正の約数を持っていさえすればいいので偶数にしちゃうのが一番簡単ですかねー
僕は奇数だったら1足して出力、偶数だったらそのまま出力としました！
想定解はおしゃれでしたねー 整数型 x に対して x / 2 * 2 を計算すると切り捨てのお陰で必ず偶数になります！
N の制約の関係上、偶数の中で唯一合成数でない2のことを考える必要はありません！
193
チャレンジによって eval を使用していたLL勢の多くがWAになっていましたー
Leading Zero を eval すると八進数扱いになったりしてしまうようですね！
僕はなんか冗長な気もしたけどうまい方法が他に思いつかなかったので手書きでパースしてたので助かりましたね
D言語を使っていて助かった感がありますｗｗ
入力 S を2つつなげた string l = S ~ S; を定義してウィンドウを横にずらしながらひたすら計算していくという解答にしましたー
そしたらなぜか途中からWAになってしまい原因がわからなかったのでウィンドウの作り方を変えてみたり int を long にしてみたりしました
結局は考えられる最大値が負になる場合を考慮していなかったのが原因でしたー
194
ここから先は全然わかりませんでしたー194に関してはゴリ押しで小さい数字なら求められたのですが、計算量的に全然間に合わないので手が止まってしまいました...
yukicoder : No.194 フィボナッチ数列の理解(1) - kmjp's blogで解説してくださっています！
これは思いつくのは無理ｗｗｗ
みなさんこれを普通に解いていて驚きますねー...
195, 196
この2問は問題文すらろくに見られていないのでまた後日復習したいと思います！
【AtCoder】ABC022 - 競技プログラミング初挑戦！
AtCoder ABC022に挑戦！
人生で初めて競技プログラミングのコンテスト(オンライン)に出場してみました！
使用言語はC++にしようかと思ったのですが、どっちかというとD言語のほうがすきだし、Dlangも十分競技プログラミングに向いているっぽかったのでD言語で出場しました。
結果
2完で121位でした
いやー惨敗でしたねｗｗ
A問題がなんか変に時間食っちゃって、焦りました。そしてB問題がするっと出来て、「おっ！」と思ったら案の定C以降にても足も出ませんでした...
C問題に関してはそもそも問題文を勘違いしていました（勘違いに気がついても結局できなかったｗｗ）
復習
解説放送も聞いてきましたー
A問題
普通にたしていった。一回全部入力受けてから計算始めてたけど無駄だったなー受け取りながら計算すればもっと早くなってたはず。
今回は簡単な問題だったのでよかったけど、こういうのでTLEになる場合もあるんだろうな
B問題
N - (花の種類)というおしゃれ解法もある様子(ただしやることは結局同じで、今まで訪れた花の種類を覚えながら舐める)
ここまでは完答
C問題
頂点1に隣接する頂点はちょうど2つなので、その2つをつなぐ最短経路を求めればいい！！
発想はなんとなくあってたなー
僕が考えていたのは、頂点1から道が伸びてる頂点Xについて、 1 - X間の道を除いたグラフを考えて、X - 1の最短経路をダイクストラで求めるやり方でした
結局実装力不足で死にましたが...(´・ω・`)
ダイクストラだとO(N2) * O(N2) = O(N4)になっちゃうけど、ワーシャルフロイドを使えばO(N3)ですむとのこと。たしかに。
ワーシャルフロイトは実装らくちんだもんなー
なるほどだなー悔しいなこれ。あとちょっとだった。
D問題
C問題でつまづきまくってしまい心が折れてたので全然まともに挑んでいないです...
解説きいたあとだから言いたい放題なんだけど、これ部分点までならとれた気がするｗｗ
いろいろ解法がある様子。とにかく、回転移動や平行移動に惑わされない値に注目してあげれば、相似比は簡単に求まるよねーというお話。
ぱっと思いついたのは最遠点だったけど、それだとO(NlogN)で部分点らしい。
最も初心者向けなのは重心からの最遠点までの距離っぽいです。
感想などなど
初めて競技プログラミングのコンテストに出場しましたがめちゃくちゃ楽しいですねこれ！
AtCoderさんの解説放送のおかげでわからなかった問題の理解もできたし、はまりそう.
もともとコンテスト外の問題は練習で少しだけ解いたことがあったのですが、全然別物の面白さでしたー
とりあえずダイクストラとかの基本アルゴリズムに関してはすらすら実装できるようになりたいなー
明日はyukicoderさんのコンテストがある？のかな？
出場してみたいと思います！
では模範解答を写経して寝ます！
