競技プログラミングにハマるプログラマのスレ 11 [無断転載禁止]©2ch.net
■ このスレッドは過去ログ倉庫に格納されています
プログラミングコンテスト(プロコン)やオンラインジャッジや競技プログラミング(競プロ)やCTFなどを楽しんでる競技プログラマ(競プロer)の雑談スレ
競プロイベントや競プロ問題や有名競プロerや競プロでよく使うアルゴリズム等について語りあったり、競プロ関連の質問相談なんでもおk
競プロ初心者でググっても解説読んでも分からないことがあったらスレの競プロの先輩方に訊いてみるのも手だよ(分かりやすい解説サイトとか書籍とか教えてくれるかもしれないよ)
次スレは>>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にテンプレ続く SnackDown確か女子を含むチーム内で 1 位を招待みたいな枠があったはず 美少女と同じ部屋で寝泊りとかkenkooooさん羨ましい 交通費や宿泊費用が出ないオンサイトに出るって観光気分なのかな >>308
中学受験経験ないけど俺もそう
あと基本情報にもそういう問題が出てた記憶がある 週末にIPSC 2017というチーム戦のコンテストがあるらしいぞ
uwiさんtomerunさんchokudaiさんのチームが出てる
https://ipsc.ksp.sk/2017/teams そういえばこのスレのdiv1/div2ってTopcoderの? Codeforcesの? 古いデータのでは大差ないように見える
TopCoderとCodeforcesのレーティングの相関を調べてみる - minus9dの記録 - TopCoder部
http://topcoder.g.hatena.ne.jp/minus9d/20120205/1328426684 >>323
相関取るのに日本人参加者だけ抽出した理由は何なんだろう CFのdiv1はTopcoderの青上位〜黄以上くらい ICFP Programming Contest 2017というチーム戦のプロコンが夏にあるらしい
http://events.inf.ed.ac.uk/icfpcontest2017/ 某コンテスト、
こっそりチーム組んで参加するの、やめて欲しいなあ
就活の時にアピール材料にするつもりか?
つるんでるのバレバレだよ >>333
これ R1 終わったあと直後のやつしか反映されてなかったりしないか? wleiteさんってTopcoderの色々なジャンルのコンテストに参加してるんですね >>333
chokudaiが優勝したのはスポンサーMMじゃないしPointの付け方もおかしい
色々とおかしいそのページ >>330
ICPCとAtCoderのコンテストのスポンサー 今日はyukicoder無いのか…仕方ないAOJ埋めで時間潰すか… ツイッターを「競技プログラミング」でキーワード検索するとbotのツイートばかり引っかかる 『嘘解法』って競プロ用語で競プロerしか使ってない チーム戦にぼっちで参加する人もいるんだね…(´・ω・`) りんごさんとこは誰かと思えばW4yneb0tか
もう一人は適当にググったら天才youtuberみたいのが出てきたがこの人か? 名前とprogrammingを一緒にして検索すると出てくるよ Yukiって誰だろう
てっきりCTFのあの方だと思ってたんだけど TCO AlgorithmのRound2 ParallellってRated? choukdaiおじさんチームは平均年齢が高いから頑張れ BasicLawってチームじゃなく個人なのに23問も行ってて強い cgy4everさんとか本当に強い人は数回の参加で赤く染まるよな
AtCoderのランキング見てて思った レート的にABは解けるだろうが
Cは部分点すら難しい ACRush参戦?
といっても今さらどうということもないか 1問しかできなかった。゚( ゚இωஇ゚)゚。 はじめて本番でDPが書けた(今回のA)
というか200点なのに想定解DPなのか Aは和が偶奇のどっちかになるかって話で
各要素の偶奇の数を数えて、コンビネーション? 想定解はDPじゃないっぽいよ
俺もDPで解いちゃったけど 200点って言ったらABCのB問題相当やんけ
数学マンにとっては簡単に見えるのか 今回のAはARC/ABCのC-Dレベルだと思うけどなぁ 数学強者のりんごさんによる難易度判定だと数学寄りの問題の難易度が低く見積もられる可能性が微レ存? レーティング上がった。゚( ゚இωஇ゚)゚。 DPに逃げてしまえば普通のナップザック問題
だからAなのでは 点数とか難易度とか関係ねえ!どんな問題も解けるようになればいいんだ! Aは自分で書いたdpの式を良く見直すとforループがいらないのだけど、
数式じゃないから気づきにくい・・・ 最近DPに慣れてきて何でもかんでもDPで解きたくなってくる B問題の解説を読んで数列や数式に直して思考するというやり方を習得 Cの重複を区間にする発想は何をどうやったら思い付けるのか 重複を区間にするという考え方を今日あなたは覚えたのでもう使えますね そういう細かいテクを片っ端から覚えて問題に対して片っ端から当てはめていって解くとか? Bも不等式を足しす所までは思いつけたとしても、逆が正しい確証をとるのが難しい・・・ [c,d]と[c,d]の和で[2c,2d]が埋め尽くせるのは、2cから1ずつ増やしていけることから分かります AGC参加できなかったけどA問題からワカンネ。
カナシス。 >>385
A問題はコンビネーションを使って愚直に場合の数を数えてく方式でも解ける
ただ入力の最大値がおっきいので素直に階乗使ってコンビネーションを計算してるとlong longでもオーバーフローして答えがおかしくなるけどそこ間違ってたりしない?
時間内だとA含め一個もダメでプロコンもできない自分も嫌いになる〜 オーバーフローうざ過ぎるからスクリプト言語で解いたったwww Aは大物から下位まで、結構解法がばらけてるね
上位陣も結構dp風で解いてる
想定解に気づいてないというわけではなくて、
その方が何も考えないで解けるという判断なのかもしれないけど
コンビネーションが想定200点解かとおもったけど、
オーバーフロー考えるとそう単純でもないか コンビネーションC(n,k)はC(n,k)<=2^nを満たすからn<=50なら(普通に64bit整数で計算すれば)オーバーフローしないぞ 普段からlong longで計算するようにしてたらいいのかもしれないな
MLEすることなんて早々ないし実行時間がちょっと増えるくらい? ここで古き良き#define int long longの出番である >>390
>>386が言ってるのは、定義式を適当に写して順列計算して階乗で割って、とかやるとだめという話では
競プロ勢的には"普通"でも、初心者が初見で突破できるかというと微妙 >>390
>>396の言う通りで、階乗を使ってmCn = m!/{(m-n)!n!}ってやると計算途中でオーバーフローするってこと
競プロ勢にはそんなん当たり前なのかもしれないが…初心者はひっかかりました。 C(n,k)(n-k)が各k (0 <= k <= n - 1)でオーバーフローしないならok
結局2^(n-1) * n < 2^63ならok >>398
>>397とかとは別人だけど、その手があったか。
ありがとう。 どうやらオーバーフローというやつかも、というのがはっきり意識出来たら、
ググれば解決ではあるんだよな
自力で書くならtanakhみたいに再帰使うことにしておくのも一策か http://www.carraria.jp/entry/2015/04/03/152600
ttp://cdn-ak.f.st-hatena.com/images/fotolife/c/carraria/20160317/20160317171424.jpg
両手に花 404 not found flowers grabbed with both hands 「procon」って別に競プロだけで使うわけではないのね
プロコンサートとか引っかかった TopcoderのUIに文句言う人たまにいるけどこういうコンテストに出たりしないのかな
TOPCODER - DASHBOARD IMPROVEMENTS
https://www.topcoder.com/challenge-details/30058261/?type=develop ■ このスレッドは過去ログ倉庫に格納されています