競技プログラミングにハマるプログラマのスレ 11 [無断転載禁止]©2ch.net

**仕様書無しさん** · 2017/06/22(木) 22:18:06.15

プログラミングコンテスト(プロコン)やオンラインジャッジや競技プログラミング(競プロ)やCTFなどを楽しんでる競技プログラマ(競プロer)の雑談スレ
競プロイベントや競プロ問題や有名競プロerや競プロでよく使うアルゴリズム等について語りあったり、競プロ関連の質問相談なんでもおｋ
競プロ初心者でググっても解説読んでも分からないことがあったらスレの競プロの先輩方に訊いてみるのも手だよ(分かりやすい解説サイトとか書籍とか教えてくれるかもしれないよ)
次スレは>>950

# オンラインジャッジ・コンテストサイト
## 日本語
yukicoder https://yukicoder.me/
AtCoder https://atcoder.jp/
AIZU ONLINE JUDGE (AOJ) http://judge.u-aizu.ac.jp/onlinejudge/
## 英語
TopCoder
Single Round Match (SRM) 関係リンク集 http://codeforces.com/blog/entry/21879
Marathon Match (MM) https://community.topcoder.com/longcontest/?module=ViewPractice
※TopCoderは初参加までの手順が煩雑です。まずはググってみて、それでも分からなかったらスレで聞こう！
Codeforces http://codeforces.com/
CS Academy https://csacademy.com/
Project Euler https://projecteuler.net/ 和訳 http://odz.sakura\.ne.jp/projecteuler/

>>2にテンプレ続く

**仕様書無しさん** · 2017/08/05(土) 18:44:41.85

ちなみにPFNのスピンアウト元のPFIは、tanakhがその設立時メンバーの一人だった
というのは田中ファンなら知っておかなきゃならないうろ覚え知識

**仕様書無しさん** · 2017/08/05(土) 18:57:16.61

>689
同感。
解説読んで、解き方が分かった気になっても、いざ実装しようとすると、詰まってしまうことがある。
まだ、たくさん書いて実装力をつけるフェーズなのかな。

**仕様書無しさん** · 2017/08/05(土) 22:44:07.01

ARC忘れてた！
と思ったら今回は日曜か

**仕様書無しさん** · 2017/08/06(日) 22:41:07.10

1問しかできなかった｡ﾟ( ﾟஇωஇﾟ)ﾟ｡

**仕様書無しさん** · 2017/08/06(日) 22:41:33.85

E１時間考えて１行もコード書けなかった・・・・

**仕様書無しさん** · 2017/08/06(日) 22:47:26.08

D見分からなくて飛ばしたけど解説見て笑った

**仕様書無しさん** · 2017/08/06(日) 22:55:13.70

Eの解説と同じ解法思いついて間に合わなかったんだけど実装重すぎじゃないか
はい練習不足ですねすみません

**仕様書無しさん** · 2017/08/06(日) 22:58:59.89

レーティング下がった｡ﾟ( ﾟஇωஇﾟ)ﾟ｡

**仕様書無しさん** · 2017/08/06(日) 23:23:28.86

Cが解けないな(´・ω・｀)

**仕様書無しさん** · 2017/08/06(日) 23:30:29.60

>>697
それも含めてこの配点なんだろうな

**仕様書無しさん** · 2017/08/06(日) 23:58:38.26

いつもDが解けないからABC出てるんだけど今日はC以上に考察もなんもなくて拍子抜けした

**仕様書無しさん** · 2017/08/07(月) 16:42:56.72

今回のE問題みたいにセグメント木を使う場合の実装ってどうしてるの？
蟻本写経？

**仕様書無しさん** · 2017/08/07(月) 19:34:25.43

アルゴリズムイントロダクションにsegmentTreeが乗ってないだと・・・

**仕様書無しさん** · 2017/08/07(月) 19:55:33.08

>>702
自前の実装を用意しておいてコピペするのが普通だと思うぞ
ちな蟻本は電子版を達人で買うとコピペ可能

**仕様書無しさん** · 2017/08/07(月) 22:44:22.90

>703
segment tree を解説しているアルゴリズムの教科書って、あまりないのかもね。

以下の本には載ってなかった。

CLRS（アルゴリズムイントロダクション）（再掲）、
Sedgewick の Algorithms 第4版、
Skiena の The Algorithm Design Manual 第二版、
AOJ本（プロコン攻略のためのアルゴリズムとデータ構造）、
最強最速アルゴリズマー養成講座、
オライリーのアルゴリズムクイックリファレンス、

こうして見ると、やっぱり蟻本は凄いと思う。
あのコンパクトな本の中に、あれだけのアルゴリズムやデータ構造が詰め込まれているのだから。

**仕様書無しさん** · 2017/08/08(火) 07:55:23.72

一般の教科書に載ってないのはsegment treeが競技以外で需要が少ないからじゃないのか
適当言ってるが

**仕様書無しさん** · 2017/08/08(火) 10:13:26.59

セグメントツリーの利点ってデータが動的に変更されても再計算が早いってことでしょ
シミュレーション系のゲームAI向き、というか人工知能全般向けな気はする

**仕様書無しさん** · 2017/08/08(火) 23:27:12.55

>>707
ゲームAIは評価値最高以外に興味ないことが多いからヒープでいいし、
人工知能は規模的にメモリに乗らないからディスクに分割して保存できるB木の亜種(普通は内部なんて考えないが)が普通じゃないのか？

**仕様書無しさん** · 2017/08/10(木) 02:47:34.88

プログラミング問題正解でアマギフと最高級松坂牛を813名（総額81万3千円）にプレゼント｜怪盗paizaからの挑戦状 #8月13日はpaizaの日 https://paiza.jp/poh/phantom_thief
そこそこ面白いミニマラソンって感じかな

**仕様書無しさん** · 2017/08/10(木) 07:55:13.40

ほとんどが独身男性だろうに生肉貰っても仕方がないぞｗ

**仕様書無しさん** · 2017/08/10(木) 08:28:44.29

牛肉に毒混ぜたらpaizaにとって邪魔な競プロ勢を一掃できるな

**仕様書無しさん** · 2017/08/10(木) 11:19:36.90

唐突に何を言い出すのだ

**仕様書無しさん** · 2017/08/10(木) 16:48:08.37

競プロ初心者なんですけどチーター本と螺旋本ではどちらがはじめに取り組む書籍としてふさわしいでしょうか？

皆さんの意見を教えろください。

**仕様書無しさん** · 2017/08/10(木) 18:42:21.73

チーター本って一目不正マニュアルかと思った

**仕様書無しさん** · 2017/08/10(木) 19:28:03.77

チーター本よりも、螺旋本の方がいいと思う。
螺旋本の方が体系的、網羅的にデータ構造やアルゴリズムの解説がしてある。
ただし、何故そのアルゴリズムで正しい答えが得られるのかの説明は螺旋本でも不十分な印象。

**仕様書無しさん** · 2017/08/11(金) 07:55:12.35

螺旋本に取り組んでみます。

**仕様書無しさん** · 2017/08/11(金) 12:46:11.33

螺旋本の目次に書いてあるアルゴリズムは一通り知っていて、Dまでコンスタントに解けるけど、
なんか細かい知識が抜けてるかと思って興味ある。

**仕様書無しさん** · 2017/08/11(金) 19:13:47.37

DCJ終わったのか
ってかGCJファイナル今晩か

**仕様書無しさん** · 2017/08/11(金) 22:18:06.83

yukicoder はじまるよー

**仕様書無しさん** · 2017/08/12(土) 12:14:40.30

Google Code Jam 2017 Final
Results https://code.google.com/codejam/contest/6314486/scoreboard#

**仕様書無しさん** · 2017/08/12(土) 18:47:42.38

ロシア人強スギィ！

**仕様書無しさん** · 2017/08/12(土) 19:24:56.81

１位はやっぱりtouristなのか

**仕様書無しさん** · 2017/08/12(土) 20:53:08.51

23時半からコードフォースィズですね！

**仕様書無しさん** · 2017/08/12(土) 20:59:33.86

まずは景気づけにABC全完

**仕様書無しさん** · 2017/08/12(土) 21:12:20.84

やべえARC忘れてた
今うんこしてるからちょっと待って

**仕様書無しさん** · 2017/08/12(土) 21:21:35.09

ああABCだけだったか
まいいややるべ

**仕様書無しさん** · 2017/08/12(土) 21:49:50.17

新あっとこーだー、一番下のルール、用語集、よくある質問のリンクが404になっちゃってる
chokudaiさん見てたら直してくれると嬉しいです

**仕様書無しさん** · 2017/08/12(土) 22:56:26.91

C,オーバーフロー対策で１時間以上格闘して、撃沈した・・・

**仕様書無しさん** · 2017/08/12(土) 23:19:06.59

>>728
1 long long型にする
2 aとbのgcdをcとおいて、
　a * b / c → (a / c) * (b / c)
で俺は解決した

**仕様書無しさん** · 2017/08/12(土) 23:42:42.06

a / __gcd(a, b) * bでもいける

**仕様書無しさん** · 2017/08/12(土) 23:49:37.36

>>729
のcは平方根？

>>730
でやったけど、pythonで通らなかった。

**仕様書無しさん** · 2017/08/12(土) 23:51:55.20

pythonはそもそも多倍長整数だからオーバーフローしないはずだけど

**仕様書無しさん** · 2017/08/12(土) 23:58:12.87

いや10**18レベルだと流石にしてるっぽかったので、
LCMの中身を場合分けしたりして塞いでました。

**仕様書無しさん** · 2017/08/13(日) 00:10:26.05

んなわけないと思って調べたらpython2のintは多倍長じゃないのか、python3だと思ってた

**仕様書無しさん** · 2017/08/13(日) 00:19:00.50

a = T[1]
for iが2からNまで
b = T[i]
a = lcm(a, b)
で普通にいけた

**仕様書無しさん** · 2017/08/13(日) 16:29:49.61

>>734
python2はint自体は固定長だけど溢れたら勝手にlongに変換されるとかじゃなかったっけ
通ってるコード見ても特に変わったことが必要になっているようには見えない

**仕様書無しさん** · 2017/08/13(日) 18:03:34.87

731多分別のところでミスってたんだろ

**731** · 2017/08/13(日) 18:33:58.71

python3で

def gcd(m,n):
if n==0:
return m
return gcd(n,m%n)

def lcm(m,n):
g=gcd(m,n)
return (m/g)*n

a=1000000000000000123600000
b=100000000000000012367890
int(lcm(a,b))

で、casioのサイトと比較しても違う（多分桁が足りない）。gcdは合ってる。
何故かnumpyのlog10もデカすぎるのか不機嫌になってる（floatにすればOK)。

**仕様書無しさん** · 2017/08/13(日) 18:58:12.48

>>738
python3の整数除算は//
これだと一旦floatになってそこで丸められちゃってるということではないかな

python2ならそのままでもいけるかと（intの変換は要らないが）

**731** · 2017/08/13(日) 19:30:07.56

>>739
//だとピッタリあった。
切り捨てだと合わないと思ったけど・・・orz

**仕様書無しさん** · 2017/08/13(日) 19:58:15.19

確かに切り捨てだけど実際はgはmとnの最大公約数なのでm//gはちゃんと割りきれるよ

**仕様書無しさん** · 2017/08/13(日) 21:07:19.57

>>741
ども、激しく頭働いてなかったorz

**仕様書無しさん** · 2017/08/13(日) 22:06:21.38

>738
今更で問題の核心とも違うけど、pythonならgcdが標準ライブラリにあるよ。
3.5以降は、import math して、math.gcd
それ以前は、import fractions して、fractions.gcd
パージョン違いでコンパイルエラーになったりするから、自作gcdを使うというのも、賢い判断だと思う。

**仕様書無しさん** · 2017/08/15(火) 01:30:23.68

10:00 からSRMです

**仕様書無しさん** · 2017/08/16(水) 18:52:35.25

深夜０時からCSAだぞ

**仕様書無しさん** · 2017/08/17(木) 01:07:57.47

10:00 からMM94です

**仕様書無しさん** · 2017/08/17(木) 16:27:07.12

散々悩みに悩んで長々書いてようやく動いた嬉しいって思ってたら他の人が遥かに洗練されたコードを書いてたときの徒労感
これは俺が初心者だから起こる事例？それとも上手くなってきてもあること？

**仕様書無しさん** · 2017/08/17(木) 17:21:48.64

そこは、『やった！もっと高みに登れる！ありがとう洗練コーダーさん！』でしょ

**仕様書無しさん** · 2017/08/17(木) 17:52:28.28

プログラマによって生産性がn倍違ってくるってのは競プロでもありえる

**仕様書無しさん** · 2017/08/17(木) 18:21:52.73

洗練されていることが理解できるならそのレベルまではあとちょっとよ

**仕様書無しさん** · 2017/08/17(木) 20:33:45.88

何やってるのかわからん、何でそれで解けるのかわからん、の壁は超えてるってワケよ

**仕様書無しさん** · 2017/08/18(金) 12:21:31.52

目の前の壁は高く感じる(´・ω・｀)

**仕様書無しさん** · 2017/08/18(金) 18:56:31.45

https://community.topcoder.com/longcontest/?module=ViewStandings&;rd=16958

今回のマラソンマッチは日本人だらけですね
日本人が多いのはchokudaiさんの影響ですかね

**仕様書無しさん** · 2017/08/18(金) 20:52:38.51

RCO presents 日本橋ハーフマラソンでマラソンerが増えた

**仕様書無しさん** · 2017/08/18(金) 21:04:03.09

競プロ、マラソン、Kaggle、将棋AI、CTF
競プロerいろんなジャンルに進撃

**仕様書無しさん** · 2017/08/18(金) 23:31:59.52

深夜０時からCFだぞ

**仕様書無しさん** · 2017/08/18(金) 23:55:34.64

よこしーなー

**仕様書無しさん** · 2017/08/19(土) 00:03:40.09

>>753
standingsの順位ついてる32人中25人が日本人…
日本人以外はこの7人だけ…
gorbunov wleite u_seem_surprsd LLI_E_P_JI_O_K kishore_g84 lg5293 id

**仕様書無しさん** · 2017/08/19(土) 00:43:39.57

pray to unrated

**仕様書無しさん** · 2017/08/19(土) 02:18:45.10

訂正数ｗｗｗｗｗｗ

**仕様書無しさん** · 2017/08/19(土) 09:26:22.65

【非婚】３億円以下の低生涯収入SEは辞めろ【離婚】
偽装請負多重派遣業界搾取SE結婚相手の犠牲対策
巨額搾取させて結婚妨害するな！
無能残業して共働き妨害するな！
・IT社長に贅沢資金を搾取させるな
・客先経営資金削減の犠牲になるな
・平均年齢40歳未満の会社は辞めろ
・6時間/日以上PC使用の会社は辞めろ
・1,000万円/年以下報酬の会社は辞めろ
・100万円/月以下報酬の契約は辞めろ
・100万円/月以下報酬のプログラムは作るな
・実態派遣プログラムを作るな
・プログラムの料金以上に作るな
・プログラムの利益を搾取させるな
・プログラムの報酬を搾取させるな
・プログラムを客先に渡すな
・不利益な依頼は断れ
・知的財産を渡するな
・客先指示に従うな
・生産利益を上げろ
・生産効率を上げろ
・契約外作業期日に従うな
・時間外労働違反は止めろ
・多重契約は止めろ
・残業見積りは止めろ
・残業しないで学習しろ
・残業しないで副業しろ
・残業しないで家事やれ
・偽装請負多重派遣は通報しろ
・損害賠償訴訟を怠るな
エンジニアの78%は“結婚待ち”
https://next.rikunabi.com/tech/docs/ct_s03600.jsp?p=002356

**仕様書無しさん** · 2017/08/20(日) 10:35:35.51

https://ja.wikipedia.org/wiki/%E5%90%88%E6%B0%97%E9%81%93#cite_note-52

この基礎をしっかりと固めろって話
数学や競プロにも通じるものがある気がする

**仕様書無しさん** · 2017/08/20(日) 12:02:48.95

歴史も古くないし合気道って一番雑魚の部類の格闘技でしょう

**仕様書無しさん** · 2017/08/20(日) 14:04:58.19

プログラミングをベースにしながらも、理念としては、正答数とその速さによって勝ち負けを争うことを肯定し、プログラミングの技を通して無理難題への諦観を解消し、
自然宇宙の「深層」「森羅万象」を理解するような境地に至ることを理想としている。
主流会派である競プロ会がレーティング番付に肯定的であるのもこの理念による。「プログラミングの武道」「争うプログラミング」「愛のプログラミング（Hack）」などとも形容され、欧米では「動く数学」とも評される。

**仕様書無しさん** · 2017/08/20(日) 20:57:59.70

よなこーしー

**仕様書無しさん** · 2017/08/20(日) 22:44:25.32

2問しかできなかった｡ﾟ( ﾟஇωஇﾟ)ﾟ｡

**仕様書無しさん** · 2017/08/20(日) 23:03:39.14

アットコーダーの順位表、20人分表のインデックスが倍々で跳びやすくなっててUI向上してる。+114514点
20人分表インデックス選択時、（糞忌々しかった）ページ全体の再読込はせずにJavascript？で20人分表だけパパッと（更新）やって終わりになっててレスポンス向上してる。+1919810点

**仕様書無しさん** · 2017/08/20(日) 23:36:07.51

ユーザーお気に入り機能が搭載されてる凄い

**仕様書無しさん** · 2017/08/20(日) 23:46:47.75

レーティング上がった｡ﾟ( ﾟஇωஇﾟ)ﾟ｡

**仕様書無しさん** · 2017/08/21(月) 08:34:44.29

【貧困】早く安く売るな【原因】

人月契約は早く作るほど早く使い捨てられるぞ！
実態派遣残業サービスして使い捨て促進するな！

・料金搾取の損害業界
・偽装請負多重派遣の損害業界
・将来リストラ問題の損害業界
・契約外期限遵守の損害業界
・客先指示遵守の損害業界
・知的財産譲渡の損害業界
・時間外労働違反の損害業界
・低予備工数見積の損害業界
・残業見積の損害業界
・無料追加の損害業界
・学習不足の損害業界
・裁判苦手の損害業界
・対人障害の損害業界
・健康障害の損害業界
・使い捨ての損害業界
・孤独死の損害業界
・低収入の損害業界
・低技術の損害業界
・結婚障害の損害業界
・鬱病早死多数の損害業界
・孤独死多数の損害業界
・裁判官が技術判定不能の損害業界

実態派遣社員は使い捨てという厳しい現実
https://xn--t8jud0j6au6x3bvde6876eixa.biz/tsukaisute/

**仕様書無しさん** · 2017/08/21(月) 10:55:21.20

>>798
簡易的なものだから履歴消したら一緒に登録も消えるんだよな

**仕様書無しさん** · 2017/08/21(月) 14:48:59.93

>>762
競プロの基礎って何だ？
蟻本を読むこと？

**仕様書無しさん** · 2017/08/21(月) 19:42:27.52

>>772
タイピング出来る

**仕様書無しさん** · 2017/08/21(月) 20:23:44.47

まずは問題を理解することだろうね

**仕様書無しさん** · 2017/08/24(木) 00:59:45.96

Topcoder DS Weekly Challenges End - Topcoder
https://www.topcoder.com/blog/ds-weekly-challenges-end/
> The winner is sigma425:

sigma425さんおめでとうございます

**仕様書無しさん** · 2017/08/24(木) 18:24:15.27

20時からSRMだょ

**仕様書無しさん** · 2017/08/24(木) 18:46:58.13

レジった

**仕様書無しさん** · 2017/08/24(木) 19:14:01.38

翌1時半からコードフォースィズですね！

**仕様書無しさん** · 2017/08/24(木) 22:49:41.74

れじ

**仕様書無しさん** · 2017/08/25(金) 01:27:54.56

そろそろ前後に大股開いてアキレス腱延ばして、手首クルクルしておくか

**仕様書無しさん** · 2017/08/25(金) 21:40:52.89

yukicoderだぞ

**仕様書無しさん** · 2017/08/25(金) 23:01:15.55

今からderu

**仕様書無しさん** · 2017/08/26(土) 02:36:44.02

yukicoder no.563の解説が、さっぱり分からないよ。

**仕様書無しさん** · 2017/08/26(土) 08:54:39.76

【貧困生活】派遣残業は結婚障害【家事困難】
偽装請負多重派遣搾取業界SEと離婚
両親や親戚に反対されましたが、低収入なのに時間外労働違反するSEと結婚してしまい生活困難で中絶と離婚をしました。現在は高稼働低収入でない共働き可能な相手と結婚して将来不安から救われました。
・モラルがない
・モテない
・キモい
・ファッションセンスがない
・コミュニケーションが苦手
・コンピューターが趣味
・プログラムの料金以上の不利益生産
・プログラムの巨額利益を客先に提供
・プログラムの巨額報酬を人売に提供
・プログラムの知的財産を人売に提供
・ITスキルが高いのに安売り低収入
・高度情報技術者なのに安売り低収入
・高生産なのに安売り低収入
・高利益なのに安売り低収入
・高需要なのに安売り低収入
・学習多いのに安売り低収入
・人員不足なのに安売り低収入
・会社員なのに早期退職
・PC使用過多で不健康
・運動不足で不健康
・高稼働で不健康
・高稼働で家事困難
・低収入で生活困難
・低収入なのに鬱病多発
・低収入なのに早死多発
・偽装請負の多重派遣損害あるのに稼働
・裁判官が技術判定不能だから賠償困難
【IT業界】独身が多い職業の象徴として「ITエンジニア」が取り上げられる
http://itpro.nikkeibp.co.jp/atcl/watcher/14/334361/110200713/?ST=spleaf

**仕様書無しさん** · 2017/08/26(土) 18:10:17.35

海外の主要な競プロサイトだとユーザ同士の交流の機能（チャットやフォーラムやブログなど）があるように見えるけど
それらと競合するところのAtCoderには交流機能がないね、日本人文化のせい？

**仕様書無しさん** · 2017/08/26(土) 20:48:40.28

さあ、（レートを）あげていくぞ！

**仕様書無しさん** · 2017/08/26(土) 20:49:31.92

日本人競技プログラマーは既にtwitterでコミュニティ築いちゃってるからなぁ
海外勢もこどふぉのコメント欄でコンテストの話してるし特に必要と思ってなさそう

**仕様書無しさん** · 2017/08/26(土) 20:57:37.29

作問touristじゃん！！

**仕様書無しさん** · 2017/08/26(土) 20:58:04.50

なよしーこー

**仕様書無しさん** · 2017/08/26(土) 20:59:25.51

今日は１問解く。(｀・ω・´)ｼｬｷｰﾝ