競技プログラミングにハマるプログラマのスレ 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-10あたりにテンプレ続く
※前スレ
競技プログラミングにハマるプログラマのスレ 14
http://medaka.5ch.net/test/read.cgi/prog/1517756393/ >>149
>>150
10のべき乗は10になるのが分かってればAC出来てたのか‥
こういう数学ってどうやって身につけるんだ A問題ごとき
普通の競プロerは思考停止の愚直全探索をまず検討するだろう(※入力の最大サイズが全探索可能なサイズの場合に限るだろうが)
解説PDFのように法則性を見つけ出そうとする人あまりいないのでは 愚直全探索をどうしたら思いつくかは慣れでしかないと思うが
公式解説PDFが愚直全探索で済むことに触れず法則性について語るだけばかりだと
いつまでも愚直全探索を思いつける感覚を養えないかもしれないが 全探索で済むのであればコンテスト中は全探索を書くべきで余計な考察はバグの温床 >>151
0から思い付くのは天才以外無理なので小さい数で愚直解を書いて実験するのが王道
今回は愚直解が書ければACできちゃうけど 【偽装請負】SEは結婚難孤独死が多数【多重派遣】
☆不利益で迷惑だから料金増やすか生産減らせ☆
リストラのためのSEだからな！
SEのリストラの対策を考えろ！
[時間外労働違反追放のお願い]
時間外労働違反
↓
偽装請負多重派遣搾取
↓
低技術
↓
低収入
↓
結婚難
↓
孤独死
SEの疾病や早死の確率が高いのは深刻な問題です。
残業や安売りなんかをしてる場合ではありません。
孤独死して社会に迷惑かけないようにしましょう。
反社会な孤独死の現場
http://matsuri.5ch.net/test/read.cgi/infosys/1509679563 皆さんレスありがとうございます
愚直全探索という言葉自体知らなかったのでもっと勉強します 「愚直」という修飾語は不要かと存じます
競プロerたちにとって役不足であるから「愚直」などと表現しているのだと思われます 愚直って強プロerがよく『脳死』って言ってるやつでしょ Online Qualification Round
July 6, 2018 4pm PST - July 9 4pm PST (72 hours)
https://www.timeanddate.com/worldclock/fixedtime.html?msg=Hacker+Cup+2018+Qualification+Round&;iso=20180706T10&p1=1240 ★5の問題って
上位の桁から桁の数字をメモりながら順列の個数を足していくのかな？ Cは転倒数というやつが関係しているらしい
転倒数はググると数学用語だけど高校数学までで習わないと違いますか 高校数学を逸脱してはいけないというルールは無いですよ 100000000000000007でググったら誰かのコードスニペット出てきた
https://pastebin.com/cGGXA2tZ
100000000000000007って結構定番な値なのか？ 土曜日ヒマならCodeChef Long Challenge (通称ChefLong)にトライして精進してみてはどうでしょうか？
ChefLongは残り2日となりましたが取り組むには十分な時間がまだあります！
http://www.codechef.com/JUNE18 chokudaiのツイート見なきゃ退会方法分からないってのが欠陥だって話でしょ
順位表に退会者がー、ってのは向こう側の理屈でユーザーからしたら知ったことではないし 退会できないサービスとかひっでえな
競プロやってるほどネットリテラシー高くても学生なんかパスワード使いまわしまくってるだろうしセキュリティは大丈夫なのか 退会したかどうかなんて外から分からないから気にすることないのに 中からは分かるだろ
途中で規約に賛同しかねる状況になったらどうすんの？
どの程度個人情報握られてるかとか全部把握してるわけ？ そうじゃなくて順位表云々の話でしょ
まあプロフィールとか消えるだろうから外からでも分かると思うが
退会フォームがないのは擁護できないわ 俺は初めから個人情報は国籍以外は虚偽の申告をしているので心配ない AtCoderJobs を利用するのでなければ個人情報入れてもメリット無いな Cの6^pと9^pを独立して考えてよいみたいなの分かるの数学的センスからくるのか？ 取引先へのアピールのために気にしてそうだけど、直近一年でコンテストに参加したアクティブユーザー数なんかを見るだろうから、退会できないのは謎 個人情報とかコンテストでTシャツもらえるようになってから考えろよ。賞品配送先住所くらいじゃね漏れて困る情報 TL眺めててコドフォ参加してる人たち楽しそうに思えた
そろそろ英語と真剣に向き合うべきか 英語できなくてもgoogle翻訳にぽいーでいけるいける 例だけでも行ける行ける。やることはatcoderとおなしだから はむこ @hamko_intel
なんだって！？ある筋からの情報によると、今週のyukicoderは、はむこが作った6問が出るらしい…！難易度も★1, 2, 3, 4, 4.5, 5と、暇な主婦にもお手軽な問題が並んでいるとのことだぞ…
これは、出るしか、ない??
https://yukicoder.me/contests/200 ＞2018-06-15 22:20:00〜2018-06-16 00:20:00のコンテストです。
なんでこんなに深夜なんだろ yukicoderの管理人がブラック企業に勤めていて帰宅時間が22時だからと予想（完全な妄想です） 才能を10段階で評価で無能を0、天才を9とするなら、一般凡人は2〜4程度
才能6〜7くらいの人がかなりの量の努力してやっと競プロ黄色というところか バズったときyukicoderでの自作問題を宣伝することにより間接的に競プロを布教するテク https://yukicoder.me/problems/no/702/submissions?lang_id=&;status=AC&sort_time=enabled&date_asc=enabled
No.702 中央値を求めよ LIMITED
100ms切る高速解法があるとは驚き 俺もWAが取れない注意してるところを見逃してるのか？ cの説明文のｉが難しくしすぎてるよaiが中身なのにｉって言っちゃうかな数列の番号なのか中身の数値なのかあれじゃあ何言ってんだって言われるぞたぶん
やってほしいことはわかったけどさあ すべてのa_iに対して処理をするって書いたらa_i=a_jとなるa_jにも同時に同じ処理をするのかってなるじゃん
a_iとa_jは添字以外で区別できないんだからああ書くのが正確で単にあなたの読解力がないだけ さくっと確信をもって提出できたらもう少し上に行けそうなんだが提出する前に毎回これでいいのかと自問してしまう
今回のAとDは想定解法通りだったのだが本当にこれでいいのか、抜けはないかと考えて無駄に時間を消費する
数こなせばその辺の自信もつくのだろうか 全ての i に対して 3 倍することはできず, 操作後の ai の値は整数でなければならない
これが混乱するわ、aiの処理なのにiに足して処理するのかって困惑した ソースコード晒せばこのスレの住人たちがマサカリ投げてくれそう 解決しました
スタックオーバーフロー（バッファオーバーフロー？）が原因でした 昨日のABC100のD問題の解法の正しさの証明やっと分かったが難しかった
M個選ぶ真の解があったとして
|ΣXi|+|ΣYi|+|ΣZi|において
|ΣXi|は正か負かゼロなり、|ΣYi|も|ΣZi|も同様として
例えば |ΣXi| > 0, |ΣYi| > 0, |ΣZi| < 0 となるケースで
|ΣXi|+|ΣYi|+|ΣZi|=(ΣXi)+(ΣYi)-(ΣZi) =Σ(Xi+Yi-Zi) となるから(Xi+Yi-Zi)を大きいほうから取れば最大になるのは分かって
同様にすれば|ΣXi|,|ΣYi|,|ΣZi|の正か負かだけケースでは全探索が有効なところまでは難しくはないのだけど
真の解の|ΣXi|,|ΣYi|,|ΣZi|のいずれかがゼロになる場合
例えば |ΣXi| > 0, |ΣYi| > 0, |ΣZi| = 0 が解となるケースで
|ΣZi|を正と仮定した (Xi+Yi+Zi) や |ΣZi|を負と仮定した (Xi+Yi-Zi) の全探索で求めることが可能なのかどうかのあたりが難しかった
(Xi+Yi+Zi)や(Xi+Yi-Zi)でソートした場合にどちらの場合でも真の解が見つかることを阻む(X,Y,Z)の組は存在しない(存在したら真の解とはらず矛盾する)というあたりから攻めていった ややこしいことしてんな
前半の不等号に等号含めれば終わりだろ |x| = max(x, -x) なので max(Σx, -Σx) + max(Σy, -Σy) + max(Σz, -Σz) の最大値を求める問題と見ることができる
これが一番しっくりきた 答えの形が±Σxi±Σyi±Σziのどれかしかないんだから8通り全部試して終わりじゃん
絶対値バラすだけで数学って笑 絶対値が出てくる問題では正負の場合分けの可能性も考慮するのが典型思考？ そう思うのは勝手だけどなんでいちいちマウント取ってくるんだろうね、こういうことするからやるだけハラスメントとか揶揄されるんだろうな 競プロの問題を解くAIを思いついた
-対象は過去問のみ
-問題のURLを与えると解答コードを即座に出力
-その実態はURLからACコードを引っ張ってきてコメントや未使用マクロ等の削除、マクロの展開、変数名関数名を適当な文字に置換、適当なフォーマッタでコードの見た目を調整、あたかもオリジナルで生成したコードかのように見せかける 競プロの問題を生成するAIを思いついた
-アルゴリズムを指定するとそのアルゴリズムが解法に含まれる問題を生成する
-その実態はアルゴリズム分類されてるCSAなどの英語の問題を日本語に機械翻訳した結果をあたかも生成した問題かのように見せかける https://twitter.com/search?vertical=default&;q=atcoder%20youtube&src=typd
atcoderの実況やっている人あまりいないね YouTube内を「動的計画法」で検索すると説明している動画が色々と出てくるのだけど
DP分からないと言っている人たちはこういう動画をチェックしているのだろうか ＞AtCoder、凄い色んな人にやってもらってるイメージが自分の中であるけど、日本人数百人くらいなのよね。
なのにAtCoder社が続けられるのはすごい アリ本の最小費用流のコラム(P205)で、流量が正である辺のコストの和の最小化のような問題になったら
他の解法を考えろと書いてありますが、この問題を解く効率的なアルゴリズムってないのでしょうか？ Div3にみんなよく出る気になるな
Div2と違って全完強いられるみたいで辛みしかない 7月20日25時(=7月21日1時)から3日間のチーム戦のプログラミングコンテスト ICFP Programming Contest 2018 があります！
chokudaiさんらのUnagiチームが活躍したことで有名です！
参加資格は特になくチームといっても人数1名のぼっちチームでも参加可能らしいです
複数人でチーム参加する場合は生活スケジュールの調整もあるでしょうし早めにチームを組んだほうがよさそうです！
過去の参加記などを読むと作業量が多いようでチーム内で作業分担するのが一般的な戦略のようです！(ぼっち参加する人はかなりの実装力が求められそうですね！)
https://twitter.com/ICFPContest2018
https://icfpcontest2018.github.io ＞流量が正である辺のコストの和の最小化
問題知らんがクラスカルのアルゴリズムのことか？？？ 既卒（大卒）
社会人（非無職）
コンテスト詳細からして中途採用とも関係は無さそう
(SoundHoundを気に入った英語出来る青色以上コーダーが自発的にAtCoderJobs経由で応募する形か) ■ このスレッドは過去ログ倉庫に格納されています
