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

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

当然ですが
したらば掲示板サービスの禁止事項に触れるような内容の雑談は禁止です
詳しくはガイドラインをお読みください
http://rentalbbs.shitaraba.com/rule/guideline.html
2：名無しさん：2016/07/06(水) 05:03:04 ID:4oqQOFFI: おはよう
3：名無しさん：2016/07/06(水) 21:04:25 ID:4oqQOFFI: おやすみ
4：名無しさん：2016/07/07(木) 20:02:10 ID:4oqQOFFI: こんにちわ
5：名無しさん：2016/07/22(金) 19:27:46 ID:L2ceMYK.: 書き込みのたびにトップに戻されてきつい
6：名無しさん：2016/07/26(火) 05:28:55 ID:k0aROTyU: cwwって人
あの資金力からして30代半ばくらいかな？
訊いてみたいけどそれより上だったら怖いので訊けないな
7：名無しさん：2016/07/28(木) 05:06:21 ID:2rMHy.aA: 大人になると熟女の良さが分かるようになるらしい
熟女競プロerを探せ
8：名無しさん：2016/07/30(土) 02:51:02 ID:MRoNnatA: ヒマしてそうな専業主婦層に普及させればいいのかな
9：名無しさん：2016/08/09(火) 16:34:08 ID:U9Ob0ijk: 若い女性競プロerもたくさん集まる
オンサイトの競プロイベントってないのかなー（ない）
10：名無しさん：2016/08/10(水) 01:33:32 ID:U9Ob0ijk: 競プロ合宿の募集みたいなのたまにTwitter上などで見かけるけど
女の子は参加してないよなー
11：名無しさん：2016/08/27(土) 18:46:43 ID:rVEiIHlE: 21:00 天下一プログラマーコンテスト2016 予選B
22:05 Codeforces Round #369 (Div. 2)
23:00 [CodeChef] August Lunchtime 2016

div2勢ですしレーティング戦のコドフォ一択ですかね
12：名無しさん：2016/08/27(土) 18:48:46 ID:rVEiIHlE: 天下一は上位勢だけが通過ですし(div1勢)
CodeChefはIOI対策ですからやはり強い人が出るでしょうし
コドフォしかないですね
13：名無しさん：2016/08/27(土) 18:51:59 ID:rVEiIHlE: Codeforces Round #369 (Div. 2) - Codeforces
http://codeforces.com/blog/entry/46781

レーティング戦かどうか書いてないすね・・・
14：名無しさん：2016/08/27(土) 18:53:36 ID:rVEiIHlE: ちょ待て
コドフォの２日後に延期してるやん・・・
15：名無しさん：2016/08/27(土) 18:55:21 ID:rVEiIHlE: 21:00 天下一プログラマーコンテスト2016 予選B
23:00 [CodeChef] August Lunchtime 2016

日本語だし天下一のほうに出ますかね・・・
16：名無しさん：2016/08/29(月) 16:25:53 ID:B322nhb6: 16:00 [HackerRank] Machine Learning CodeSprint
21:05 Codeforces Round #369 (Div. 2)

今日は２つか
17：名無しさん：2016/08/29(月) 16:26:27 ID:B322nhb6: マシンラーニングって機械学習？
よく分からないからパスでいいや
18：名無しさん：2016/08/29(月) 16:31:26 ID:B322nhb6: HackerRank's Machine Learning CodeSprint
https://www.hackerrank.com/machine-learning-codesprint

August 29th, 2016 - September 4th, 2016

1週間か、長い
19：名無しさん：2016/08/29(月) 16:33:05 ID:B322nhb6: HackerRank - Wikipedia, the free encyclopedia
https://en.wikipedia.org/wiki/HackerRank
> •Machine Learning: use predictive modeling and analysis to solve challenges.

よく分からないけど難しそう
20：名無しさん：2016/08/29(月) 16:33:48 ID:B322nhb6: コドフォだけでいいかな
21：名無しさん：2016/08/29(月) 18:25:48 ID:B322nhb6: PowerShell慣れないと使いづらいかも
コマンドプロンプトとともUnixシェルとも違って独特な感じで
ちょっとしんどい
22：名無しさん：2016/08/29(月) 18:27:49 ID:B322nhb6: 一連の処理をまとめたバッチファイルやシェルスクリプトみたいなファイルも
PowerShellだと署名をつけなきゃダメらしいし多少の安心感は上がっても気軽さお手軽さを感じられない
23：名無しさん：2016/08/30(火) 02:42:19 ID:B322nhb6: したらば不安定すぎ
24：名無しさん：2016/08/30(火) 23:08:03 ID:B322nhb6: 週末のAGCまで予定なし
25：名無しさん：2016/08/30(火) 23:18:45 ID:B322nhb6: いい機会だから最近の流行らしいunion-findというのを覚えようかな
26：名無しさん：2016/08/31(水) 00:26:35 ID:B322nhb6: PowerShellのセキュリティゆるすぎ
powershell.exe -ExcutionPolicy RemoteSigned -File hoge.ps1
で確認プロンプトもなしにスクリプト実行できるでやんの
デフォルトでRestrictedになってるとか全く意味ねー
27：名無しさん：2016/08/31(水) 00:32:32 ID:B322nhb6: powershell上からSet-ExecutionPolicyで設定変えるときは確認メッセージ出すのに
powershellのコマンド引数で指定だと確認メッセージすら出さんとはイカレてる
28：名無しさん：2016/08/31(水) 00:51:27 ID:B322nhb6: ファッ！？
PowerShellから.batのバッチファイル普通に実行できた
29：名無しさん：2016/08/31(水) 00:56:38 ID:B322nhb6: バッチファイルはPowerShell内の環境で実行されるんじゃなくて
コマンドプロンプト上で実行されるのか
普通のプログラム実行と同じ扱いか
30：名無しさん：2016/08/31(水) 01:00:17 ID:B322nhb6: 独り言だけならツイッターのほうがいいか
でもツイッター会員登録面倒だし
古いツイート探しにくいし
どうせこの掲示板人いないし
ここで問題ないよね
31：名無しさん：2016/08/31(水) 01:20:30 ID:B322nhb6: Powershell上で.net frameworkの呼び出し実行できた

[system.console]::writeline("hoge")

大文字小文字は区別しないらしい
32：名無しさん：2016/08/31(水) 01:21:22 ID:B322nhb6: PowerShellはオープンソース化されたし
Bashが競プロにあるならPowerShellも競プロのくる日がいずれあるかも
33：名無しさん：2016/08/31(水) 01:42:53 ID:B322nhb6: うお
PowerShellのリダイレクト書き込みはUCS-2というエンコーディングだわ
パイプでOut-Fileでエンコーディング指定しないとダメらしい(sjis無いけど)

echo 'abc 1234' > hoge.txt
echo '987 xyz' >> hoge.txt

echo 'abc 1234' | Out-File hoge.txt -Encoding ascii
echo '987 xyz' | Out-File hoge.txt -Encoding ascii -Append
34：名無しさん：2016/08/31(水) 01:44:06 ID:B322nhb6: 競プロで使うならasciiじゃなくてutf8にすべきか
35：名無しさん：2016/08/31(水) 01:58:10 ID:B322nhb6: PowerShellの関数呼び出し
functin hoge($x) { echo "arg is $x" }

hoge 'aiueo'
が正しい

hoge('aiueo')
は
hoge ('aiueo')
と解釈され()内をコマンドとして実行した結果をhogeの引数に渡す

これ危ない
36：名無しさん：2016/08/31(水) 02:21:39 ID:B322nhb6: function red($x) { $input | Out-File -FilePath "$x" -Encoding utf8 }
function redp($x) { $input | Out-File -FilePath "$x" -Encoding utf8 -Append }

echo 'abc 1234' | red hoge.txt
echo '987 xyz' | redp hoge.txt

リダイレクト作ってみた
37：名無しさん：2016/08/31(水) 02:23:05 ID:B322nhb6: yukicoderあたりでPowerShell導入しないかなあ
38：名無しさん：2016/08/31(水) 03:39:11 ID:B322nhb6: 今気づいたけど競プロでリダイレクト使わないよな普通・・・
変な出力するやつを/dev/nullに送るとかするけど
それ以外で使うことないよなあ /dev/stdout に出す意味もないし
39：名無しさん：2016/08/31(水) 03:41:20 ID:B322nhb6: Powershellで気づいたこと
Out-Fileのエンコーディング指定で OEMってやればpowershellの現在のコードページと同じエンコーディングしてくれるらしい、OEMでsjisいけた
あとリダイレクトとOut-FileでのUCS2やUTF8はBOM付きになる・・・
40：名無しさん：2016/08/31(水) 16:29:17 ID:B322nhb6: B: Union Find - AtCoder Typical Contest 001 | AtCoder
http://atc001.contest.atcoder.jp/tasks/unionfind_a

さて
お勉強するか
41：名無しさん：2016/08/31(水) 16:36:08 ID:B322nhb6: Union find(素集合データ構造)
http://www.slideshare.net/chokudai/union-find-49066733/1

このslideshareってたぶん本来はパワポみたいな感じのプレゼンテーション的なスライド出来るんだろうけど
完全におま環なんだけどスライドとして見れたことがない
42：名無しさん：2016/08/31(水) 16:37:48 ID:B322nhb6: 『おま環を解決出来ない奴はプログラマとして完全に終わっている！』
43：名無しさん：2016/08/31(水) 16:39:42 ID:B322nhb6: お、prestoエンジンの旧オペラで見たらスライドした
44：名無しさん：2016/08/31(水) 16:40:37 ID:B322nhb6: アンインストールしなくてよかったprestoオペラ
45：名無しさん：2016/08/31(水) 16:45:01 ID:B322nhb6: うーん、どうもunion findはそうとは知らずに１度か２度ほど使ったことあるぞ…
それでもunion findの問題に全然対応できてないから頭の中で定式化出来てないせいだから
ちゃんと仕組み覚えないと
46：名無しさん：2016/08/31(水) 16:50:56 ID:B322nhb6: たしかラベリング処理の融合にこれっぽい処理を使った
ラベリングについて書いてあった本に書いてあったわけではない
47：名無しさん：2016/08/31(水) 16:55:08 ID:B322nhb6: うう、スライドに書いてあるやりかた
俺がやってたのとほとんど同じやり方だ・・・
つまり結論としては
俺の中ではラベリング処理の中の融合処理部という認識からunion findという正式な名前があることを知ったというだけか

そもそもやり方知っててunion findの問題を全然解けないってのは
また別のとこに不足があるんだろうな
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
競プロのアンケートらしい