雑談スレ - 1467740989 - したらば掲示板

1：名無しさん：2016/07/06(水) 02:49:49 ID:QjAtSIeQ: プロコン・競プロ・ハッカソン・CTF・オンラインジャッジなどをされる方々の雑談の場としたいです
雑談ですのでプロコン・競プロ・ハッカソン・CTF・オンラインジャッジなどに関係しない内容でも構いません。

当然ですが
したらば掲示板サービスの禁止事項に触れるような内容の雑談は禁止です
詳しくはガイドラインをお読みください
http://rentalbbs.shitaraba.com/rule/guideline.html
48：名無しさん：2016/08/31(水) 16:58:14 ID:B322nhb6: >>42
まぁ究極で言えば『問題の生じないＰＣを買えば解決』だから
プログラマってわけじゃないよな
49：名無しさん：2016/08/31(水) 16:58:59 ID:B322nhb6: 『解決できない問題など存在しないのだ』
50：名無しさん：2016/08/31(水) 17:00:47 ID:B322nhb6: なんか9月4日にGeeksForGeeksで大会あるみたいだけど
全く注目されないのはレーティング戦ではないってとことと
スポンサー企業の採用面接（？）のチャンスがある感じの大会だからか
賞金とＴシャツはあるみたいだけど
51：名無しさん：2016/08/31(水) 17:02:41 ID:B322nhb6: GeeksForGeeksってたしかインドだったっけ？
日本から出てインドで働くのはなあ・・・色々覚悟いるよなあ・・・
52：名無しさん：2016/08/31(水) 17:07:43 ID:B322nhb6: union findで何か拍子抜けしたけど
仕組みわかってても
union findの問題自体に慣れないとunion findの使いどころは見抜けない
ひたすら過去問するきゃないか
53：名無しさん：2016/09/02(金) 19:14:09 ID:7/.JCEwo: Twitter認証で登録できる競プロサイト少なっ
54：名無しさん：2016/09/07(水) 22:31:20 ID:sz3.obKE: ttp://oi68.tinypic.com/2je63qx.jpg
ttp://oi66.tinypic.com/2e2f8f9.jpg

Haskellが数学界で流行るわけだ
55：名無しさん：2016/09/07(水) 22:33:24 ID:sz3.obKE: 漸化式さえ分かればHaskellで一発というわけだな
漸化式さえ分かれば…な
56：名無しさん：2016/09/07(水) 23:15:50 ID:XDSoSiaA: TLEで死
57：名無しさん：2016/09/11(日) 18:06:19 ID:.peqoGOU: PlusCALやTLA+という謎言語を見つけた
58：名無しさん：2016/09/11(日) 18:13:36 ID:.peqoGOU: PlusCALとTLA+は日本語圏での情報少ねーな

The PlusCal Algorithm Language
http://research.microsoft.com/en-us/um/people/lamport/tla/pluscal.html
59：名無しさん：2016/09/11(日) 18:17:40 ID:.peqoGOU: TLA+でのハノイの塔

Examples/specifications/tower_of_hanoi at master ・ tlaplus/Examples ・ GitHub
https://github.com/tlaplus/Examples/tree/master/specifications/tower_of_hanoi

パッと見、関数型プログラミング言語に近いのか？
60：名無しさん：2016/09/11(日) 18:20:04 ID:.peqoGOU: アルゴリズム言語という割には競プロでは使えなさそう
61：名無しさん：2016/09/11(日) 18:27:59 ID:.peqoGOU: PlusCALはTLA+で作られてるぽさげ？

http://research.microsoft.com/en-us/um/people/lamport/tla/PlusCal.tla
62：名無しさん：2016/09/11(日) 18:32:51 ID:.peqoGOU: TLA+ - Wikipedia, the free encyclopedia
https://en.wikipedia.org/wiki/TLA%2B

面白そうな言語なのに日本語資料が少ないことが悔やまれる
63：名無しさん：2016/09/11(日) 18:38:37 ID:.peqoGOU: 専門用語系は英語と日本語の対応がちゃんとしてなかったりして調べにくいな
PlusCALやTLA+は少なくともプログラミング言語にジャンル分けされないようだからこれでの競プロは無さそうだな
64：名無しさん：2016/09/11(日) 20:22:51 ID:.peqoGOU: 時相論理に関係あるらしいけどyouwakarann
65：名無しさん：2016/09/13(火) 18:09:40 ID:.peqoGOU: Petr Mitrichev - Wikipedia, the free encyclopedia
https://en.wikipedia.org/wiki/Petr_Mitrichev

競プロのめっちゃ強い人がウィキペディアに記事あった
66：名無しさん：2016/09/25(日) 18:19:17 ID:0qa0equ.: 計算量という概念やっぱ難しい
メジャーなアルゴリズムの計算量の導出とか色んな人が書いてるけど
どれ読んでも理解不能
何言ってるのかワケワカメ
67：名無しさん：2016/09/25(日) 18:21:53 ID:0qa0equ.: 基本的なソート系とかアルゴリズムの本にも書いてある基礎中の基礎だが
時間計算量の導出もやはりどれも解説されていはいるけど
その解説が理解不能
やっぱ頭脳レベルが低いと競プロは永遠に下層かもしれん
68：名無しさん：2016/09/25(日) 18:27:31 ID:0qa0equ.: 努力でどうにかなるって気がしない
つか何を努力すれば理解に結びつくのか皆目検討が付かない
69：名無しさん：2016/09/25(日) 18:30:54 ID:0qa0equ.: 俺が読んできた解説がことごとく説明下手な人間によって書かれていたとかいうなら
説明上手い人に出会うことを目標に計算量理解してる人らと交流持つとかそんな感じ？

> 俺が読んできた解説がことごとく説明下手な人間によって書かれていた

この前提が正しいかどうかも分からん
その説明が易しいのか難しいのかすら見当つかないわけだし

どうすりゃいいんだよ！
70：名無しさん：2016/11/20(日) 00:49:40 ID:eU5cIYDI: https://twitter.com/chokudai/status/798565962127589376

ローリングハッシュが何なのか思い出せず
71：名無しさん：2017/02/15(水) 23:42:08 ID:KHIvLZmI: 競プロ本、地元の図書館に現在ないけど
要望出したら入荷してくれるかなあ・・・？
72：名無しさん：2017/02/16(木) 22:51:44 ID:KHIvLZmI: 蟻本って一部だけならグーグルの書籍検索でも読めるんだね
2chのスレでワーシャルフロイドの話あってちょろっと見てみた
中々簡潔に書かれてて読むの大変そう
73：名無しさん：2017/02/16(木) 22:56:44 ID:KHIvLZmI: なるほどdp[k][i][j]の頂点0～kのk+1個の頂点を使った場合のiとjの最短経路をあらわすのか
74：名無しさん：2017/02/16(木) 23:00:21 ID:KHIvLZmI: dp[k-1][i][j]は頂点0～(k-1)のk個の頂点だけを使ったときのiとjの最短経路か
そこに頂点kを加えたときのiとjの最短経路dp[k][i][j]を求めるってこととか
頂点(k-1)までを使った最短経路は求まっているのだから頂点kを経由する経路についてだけ新たに考えればよいと
75：名無しさん：2017/02/16(木) 23:04:06 ID:KHIvLZmI: dp[k-1][i][k]+dp[k-1][k][j]は
iとkのどこも経由しない直通と
kとjのどこも経由しない直通との和になってるはず(ここまでのDPでは頂点kについては考慮してないはずだから)
76：名無しさん：2017/02/16(木) 23:08:27 ID:KHIvLZmI: min(dp[k-1][i][j],dp[k-1][i][k]+dp[k-1][k][j])は
頂点kを一切経由しない最短経路と
頂点kのみを経由する経路とで
最小のほうを選択して頂点0～k個使う場合のiとjの最短経路を求めている・・・
77：名無しさん：2017/02/16(木) 23:13:35 ID:KHIvLZmI: dp[k-1][i][j]は
i -> j の可能性もあるし
i -> a -> b -> j の可能性もある
その中での最短経路、そこに頂点kを加える
i -> k -> j と比較するわけだけど
例えば i -> a -> k -> j のほうが短くなったりしないのだろうか
78：名無しさん：2017/02/16(木) 23:17:46 ID:KHIvLZmI: そうか、本にあるコードは(k-1)を省略した2次元のほうのコードだから
それをそのままdp[k-1][i][j]の3次元のコードとして捉えちゃダメなんだな
使用する頂点の数を考慮する場合は本のとは違うコードにならなければならないのか
79：名無しさん：2017/02/16(木) 23:21:43 ID:KHIvLZmI: これ2次元版と3次元版のコードでは大掛かりな変形が必要な感じがする
80：名無しさん：2017/02/16(木) 23:28:17 ID:KHIvLZmI: これ3次元版から2次元版に落とし込むための理屈はかなり複雑になる気がする
81：名無しさん：2017/02/16(木) 23:33:11 ID:KHIvLZmI: 3次元版のときは最初に頂点kを始点あるいは終点とした最短経路を求めてから頂点kを経由する最短経路を求める必要があるのかな？
82：名無しさん：2017/02/16(木) 23:45:42 ID:KHIvLZmI: もし>>81の考え方が合ってるなら蟻本の説明が不適切なん気がするよ・・・
83：名無しさん：2017/02/16(木) 23:47:57 ID:KHIvLZmI: まぁでもワーシャルフロイド法って蟻本でなくても学習できることだし
メジャーなアルゴリズムの説明ならもっと分かりやすく説明してる本やサイトを探すのが解決には早そう
84：名無しさん：2017/02/16(木) 23:50:01 ID:KHIvLZmI: 人によって説明の仕方が違うから
一人の人の説明だけに頼らず色んな人の説明を参考にしたほうが
多少時間や手間がかかっても理解には直結しやすいと思うけど
85：名無しさん：2017/02/17(金) 00:19:28 ID:KHIvLZmI: 2次元版のは
全ての頂点(0～V)においてiからjまでの頂点0～(k-1)を経由する可能性のある最短経路に対して
頂点kをi,jにおいてそれぞれの頂点0～(k-1)を経由する可能性のある最短経路で経由させた場合に新たなiとjの最短経路になるかっていう感じ
86：名無しさん：2017/02/17(金) 00:26:38 ID:KHIvLZmI: あ、そうか、>>85を考えると>>81は間違いだわ
蟻本の「使う」の言葉の意味の解釈の問題だわ
87：名無しさん：2017/02/17(金) 00:33:01 ID:KHIvLZmI: 蟻本の「頂点0～kのみを使う」というのは「最短経路の経由点として使う」という意味なのか
>>73での間違い解釈はi,jに関しては0～(k-1)を使うと思ってたけどそうではなく0～Vを使う
「頂点0～kとi,jのみを使う」って一文、何か不自然さを感じてたけど、「と」による区切れがi,jは0～Vを使うという意味が含まれてたのか
88：名無しさん：2017/02/17(金) 00:37:12 ID:KHIvLZmI: >>73-81までの解釈は完全に間違いだということを理解した
89：名無しさん：2017/02/17(金) 00:44:12 ID:KHIvLZmI: つまり3次元版のdp[k][i][j]は頂点0～kを経由する可能性のあるi間j(頂点0～V)の最短経路を表す
90：名無しさん：2017/02/17(金) 00:54:20 ID:KHIvLZmI: >>73も>>89も間違いがあって
dp[k+1][i][j]が頂点0～kの範囲で
dp[k][i][j]は頂点0～(k-1)だった
91：名無しさん：2017/02/17(金) 01:25:59 ID:KHIvLZmI: 3次元を2次元に落とし込める理由は

入力側の頂点(k-1)を1度経由させる経路は
dp[k-1][i][k-1]もdp[k-1][k-1][j]もどちらも頂点(k-1)以降を経由しない(頂点0～(k-2)を経由する可能性のある)最短経路が保証され
2次元のdp[i][k-1]もdp[k-1][j]も同様のことが言える

更新される側の
2次元の場合、dp[i][j]が更新されていくわけで入力側に何らかの影響がありそうな雰囲気を感じることがあるのかもしれないけど
入力に影響がありそうに見えるのはこのiかjがどちらかが(k-1)だった場合、
つまり始点か終点が頂点(k-1)であり、それの最短経路の経由点に頂点(k-1)を含むことはないので入力に全く影響を与えない
3次元で言うと
dp[k][i][k-1]=min(dp[k-1][i][k-1],dp[k-1][i][k-1]+dp[k-1][k-1][k-1])これは常にdp[k][i][k-1]=dp[k-1][i][k-1] (どう見ても自明)
同様にdp[k][k-1][j]についてもいえる
i!=k-1かつj!=k-1のときはdp[k-1][][]からdp[k][][]への計算に再利用はされないから
3次元の最初の次元である使用する頂点の数というのを分けて考える必要ないから2次元に落とし込める

だめだ、俺も日本語下手だわ
92：名無しさん：2017/02/17(金) 01:37:47 ID:KHIvLZmI: >>72-91をもってワーシャルフロイド法の学習修了
競プロ本番ではこれを使う問題に遭遇する機会が少なそうだから
たぶん実際に出題されたタイミングではワーシャルフロイド法のことド忘れしてそう
93：名無しさん：2017/02/18(土) 03:06:30 ID:KHIvLZmI: ワーシャルフロイドでツイッター検索かけると競プロerばかりで競プロでしか使われないのかと思った
94：名無しさん：2017/02/20(月) 08:01:04 ID:KK.J3/1w: 雑談じゃなくて独り言になってんじゃねーか
Twitterでやれ
95：名無しさん：2017/02/21(火) 00:47:25 ID:1jQKvRXA: この使い方だとツイッターよりSlackのほうが向いてる
96：名無しさん：2017/02/21(火) 00:49:32 ID:1jQKvRXA: Slackでアルゴリズム勉強チャンネルというのを作って
そのチャンネルでさらにアルゴリズムごとにスレッドを作ればよい
97：名無しさん：2017/07/02(日) 19:08:51 ID:VSKAyqS.: http://medaka.2ch.net/test/read.cgi/prog/1493085730/804
競プロのアンケートらしい