競技プログラミングにハマるプログラマのスレ 11 [無断転載禁止]©2ch.net
■ このスレッドは過去ログ倉庫に格納されています
プログラミングコンテスト(プロコン)やオンラインジャッジや競技プログラミング(競プロ)や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にテンプレ続く >660
一行目は、数列の長さを出力する。
4
3 3 3
だと、二行目の数列の長さと一行目とが整合していない。 なんにもできなかった｡ﾟ( ﾟஇωஇﾟ)ﾟ｡ Div1 A(Div2 C)問題が以前話に上がったGCDと指数のMINの関係を使って解ける問題だったな 約数やGCDや中国剰余定理のあたりを理解しているかどうかで壁が一つある気がする
(競プロでも数学オリンピックとかでも) 事実としては知ってるけど名前を知らないパターンもありそう 情オリまるで日本人に午後サボって観戦しろと言っているかのような時間設定だw なんにもできなかった｡ﾟ( ﾟஇωஇﾟ)ﾟ｡ yutaka1999には競技時間5時間もいらないんだよな
実力通りなら彼はAbsolute Winnerだと思う ニコニコでN高等学校「高橋直大の競技プログラミング入門」公開授業やってるよ
URLはNGワードで書けないが ちょくだいはこれで授業料いくら稼ぐの？
二時間で何万稼ぐ男？
30分×4だから20万？ http://live.ni
covi
deo.jp/watch/lv303493194 atcoderで緑ってARCのタイムと正解数どれぐらいでなれるの >>680
ARCのCが早解きできれば水色にはなるので、時間かかってもCが通せれば緑にはなる
Cが解けるかどうかの人はABCの方が安定しそう
結局レートは毎回のパフォーマンス値に漸近するからそれ見れば分かると思う そのレート帯の人のコンテスト成績見れば具体的にわかるよ 競プロが富裕層に有利なのは事実(PCや環境が必須だから)
競プロをまったくしらない界隈じゃなくて、名もない灰色コーダーや挫折組が共感してRTしてるんだよ >>685
まだ８００点行かないっす。(´・ω・｀) PFNにトヨタが105億円追加出資のニュースが出てたね。
競プロあがりの人達の活躍する場が国内にも増えていきそうだね。 トヨタなんていうビッグネームとディールできるなんてプリファードなんちゃらも出世したもんだなぁ ちなみにPFNのスピンアウト元のPFIは、tanakhがその設立時メンバーの一人だった
というのは田中ファンなら知っておかなきゃならないうろ覚え知識 >689
同感。
解説読んで、解き方が分かった気になっても、いざ実装しようとすると、詰まってしまうことがある。
まだ、たくさん書いて実装力をつけるフェーズなのかな。 1問しかできなかった｡ﾟ( ﾟஇωஇﾟ)ﾟ｡ Eの解説と同じ解法思いついて間に合わなかったんだけど実装重すぎじゃないか
はい練習不足ですねすみません レーティング下がった｡ﾟ( ﾟஇωஇﾟ)ﾟ｡ いつもDが解けないからABC出てるんだけど今日はC以上に考察もなんもなくて拍子抜けした 今回のE問題みたいにセグメント木を使う場合の実装ってどうしてるの？
蟻本写経？ アルゴリズムイントロダクションにsegmentTreeが乗ってないだと・・・ >>702
自前の実装を用意しておいてコピペするのが普通だと思うぞ
ちな蟻本は電子版を達人で買うとコピペ可能 >703
segment tree を解説しているアルゴリズムの教科書って、あまりないのかもね。
以下の本には載ってなかった。
CLRS（アルゴリズムイントロダクション）（再掲）、
Sedgewick の Algorithms 第4版、
Skiena の The Algorithm Design Manual 第二版、
AOJ本（プロコン攻略のためのアルゴリズムとデータ構造）、
最強最速アルゴリズマー養成講座、
オライリーのアルゴリズムクイックリファレンス、
こうして見ると、やっぱり蟻本は凄いと思う。
あのコンパクトな本の中に、あれだけのアルゴリズムやデータ構造が詰め込まれているのだから。 一般の教科書に載ってないのはsegment treeが競技以外で需要が少ないからじゃないのか
適当言ってるが セグメントツリーの利点ってデータが動的に変更されても再計算が早いってことでしょ
シミュレーション系のゲームAI向き、というか人工知能全般向けな気はする >>707
ゲームAIは評価値最高以外に興味ないことが多いからヒープでいいし、
人工知能は規模的にメモリに乗らないからディスクに分割して保存できるB木の亜種(普通は内部なんて考えないが)が普通じゃないのか？ プログラミング問題正解でアマギフと最高級松坂牛を813名（総額81万3千円）にプレゼント｜怪盗paizaからの挑戦状 #8月13日はpaizaの日 https://paiza.jp/poh/phantom_thief
そこそこ面白いミニマラソンって感じかな ほとんどが独身男性だろうに生肉貰っても仕方がないぞｗ 牛肉に毒混ぜたらpaizaにとって邪魔な競プロ勢を一掃できるな 競プロ初心者なんですけどチーター本と螺旋本ではどちらがはじめに取り組む書籍としてふさわしいでしょうか？
皆さんの意見を教えろください。 チーター本よりも、螺旋本の方がいいと思う。
螺旋本の方が体系的、網羅的にデータ構造やアルゴリズムの解説がしてある。
ただし、何故そのアルゴリズムで正しい答えが得られるのかの説明は螺旋本でも不十分な印象。 螺旋本の目次に書いてあるアルゴリズムは一通り知っていて、Dまでコンスタントに解けるけど、
なんか細かい知識が抜けてるかと思って興味ある。 やべえARC忘れてた
今うんこしてるからちょっと待って 新あっとこーだー、一番下のルール、用語集、よくある質問のリンクが404になっちゃってる
chokudaiさん見てたら直してくれると嬉しいです C,オーバーフロー対策で１時間以上格闘して、撃沈した・・・ >>728
1 long long型にする
2 aとbのgcdをcとおいて、
a * b / c → (a / c) * (b / c)
で俺は解決した >>729
のcは平方根？
>>730
でやったけど、pythonで通らなかった。 pythonはそもそも多倍長整数だからオーバーフローしないはずだけど いや10**18レベルだと流石にしてるっぽかったので、
LCMの中身を場合分けしたりして塞いでました。 んなわけないと思って調べたらpython2のintは多倍長じゃないのか、python3だと思ってた a = T[1]
for iが2からNまで
b = T[i]
a = lcm(a, b)
で普通にいけた >>734
python2はint自体は固定長だけど溢れたら勝手にlongに変換されるとかじゃなかったっけ
通ってるコード見ても特に変わったことが必要になっているようには見えない 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)。 >>738
python3の整数除算は//
これだと一旦floatになってそこで丸められちゃってるということではないかな
python2ならそのままでもいけるかと（intの変換は要らないが） >>739
//だとピッタリあった。
切り捨てだと合わないと思ったけど・・・orz 確かに切り捨てだけど実際はgはmとnの最大公約数なのでm//gはちゃんと割りきれるよ >738
今更で問題の核心とも違うけど、pythonならgcdが標準ライブラリにあるよ。
3.5以降は、import math して、math.gcd
それ以前は、import fractions して、fractions.gcd
パージョン違いでコンパイルエラーになったりするから、自作gcdを使うというのも、賢い判断だと思う。 散々悩みに悩んで長々書いてようやく動いた嬉しいって思ってたら他の人が遥かに洗練されたコードを書いてたときの徒労感
これは俺が初心者だから起こる事例？それとも上手くなってきてもあること？ そこは、『やった！ もっと高みに登れる！ ありがとう洗練コーダーさん！』でしょ プログラマによって生産性がn倍違ってくるってのは競プロでもありえる 洗練されていることが理解できるならそのレベルまではあとちょっとよ 何やってるのかわからん、何でそれで解けるのかわからん、の壁は超えてるってワケよ RCO presents 日本橋ハーフマラソンでマラソンerが増えた 競プロ、マラソン、Kaggle、将棋AI、CTF
競プロerいろんなジャンルに進撃 >>753
standingsの順位ついてる32人中25人が日本人…
日本人以外はこの7人だけ…
gorbunov wleite u_seem_surprsd LLI_E_P_JI_O_K kishore_g84 lg5293 id 【非婚】３億円以下の低生涯収入SEは辞めろ【離婚】
偽装請負多重派遣業界搾取SE結婚相手の犠牲対策
巨額搾取させて結婚妨害するな！
無能残業して共働き妨害するな！
・IT社長に贅沢資金を搾取させるな
・客先経営資金削減の犠牲になるな
・平均年齢40歳未満の会社は辞めろ
・6時間/日以上PC使用の会社は辞めろ
・1,000万円/年以下報酬の会社は辞めろ
・100万円/月以下報酬の契約は辞めろ
・100万円/月以下報酬のプログラムは作るな
・実態派遣プログラムを作るな
・プログラムの料金以上に作るな
・プログラムの利益を搾取させるな
・プログラムの報酬を搾取させるな
・プログラムを客先に渡すな
・不利益な依頼は断れ
・知的財産を渡するな
・客先指示に従うな
・生産利益を上げろ
・生産効率を上げろ
・契約外作業期日に従うな
・時間外労働違反は止めろ
・多重契約は止めろ
・残業見積りは止めろ
・残業しないで学習しろ
・残業しないで副業しろ
・残業しないで家事やれ
・偽装請負多重派遣は通報しろ
・損害賠償訴訟を怠るな
エンジニアの78%は“結婚待ち”
https://next.rikunabi.com/tech/docs/ct_s03600.jsp?p=002356 ■ このスレッドは過去ログ倉庫に格納されています
