競技プログラミングにハマるプログラマのスレ 15

■ このスレッドは過去ログ倉庫に格納されています
1仕様書無しさん
垢版 |
2018/05/14(月) 06:43:50.62
プログラミングコンテスト(プロコン)やオンラインジャッジや競技プログラミング(競プロ)や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/
157仕様書無しさん
垢版 |
2018/06/06(水) 08:05:31.76
【偽装請負】SEは結婚難孤独死が多数【多重派遣】

☆不利益で迷惑だから料金増やすか生産減らせ☆

リストラのためのSEだからな！
SEのリストラの対策を考えろ！

[時間外労働違反追放のお願い]

時間外労働違反
↓
偽装請負多重派遣搾取
↓
低技術
↓
低収入
↓
結婚難
↓
孤独死

SEの疾病や早死の確率が高いのは深刻な問題です。
残業や安売りなんかをしてる場合ではありません。
孤独死して社会に迷惑かけないようにしましょう。

反社会な孤独死の現場
http://matsuri.5ch.net/test/read.cgi/infosys/1509679563
2018/06/06(水) 08:42:52.06
皆さんレスありがとうございます
愚直全探索という言葉自体知らなかったのでもっと勉強します
2018/06/06(水) 12:59:52.50
>>158です
https://www.slideshare.net/mobile/chokudai/wap-atcoder1
調べてたら、このスライドいいなと思いました
同じ初心者の人が居たら是非
2018/06/06(水) 23:32:50.51
「愚直」という修飾語は不要かと存じます
競プロerたちにとって役不足であるから「愚直」などと表現しているのだと思われます
2018/06/07(木) 07:33:33.68
愚直って強プロerがよく『脳死』って言ってるやつでしょ
162仕様書無しさん
垢版 |
2018/06/07(木) 09:46:35.35
Facebook Hacker Cup 2018 のお知らせ

https://m.facebook.com/story.php?story_fbid=1915605128471666&;id=133954286636768
163仕様書無しさん
垢版 |
2018/06/07(木) 09:47:45.58
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
2018/06/08(金) 22:41:41.51
yukicoderのコンテスト開催中ですよ
https://yukicoder.me/contests
2018/06/09(土) 00:21:51.00
★5の問題って
上位の桁から桁の数字をメモりながら順列の個数を足していくのかな？
2018/06/09(土) 00:30:25.32
Cは転倒数というやつが関係しているらしい
転倒数はググると数学用語だけど高校数学までで習わないと違いますか
2018/06/09(土) 00:39:28.63
高校数学を逸脱してはいけないというルールは無いですよ
2018/06/09(土) 00:46:03.90
100000000000000007でググったら誰かのコードスニペット出てきた

https://pastebin.com/cGGXA2tZ

100000000000000007って結構定番な値なのか？
2018/06/09(土) 00:50:49.73
次のAtCoderのコンテストは日曜日か
2018/06/09(土) 00:55:44.89
土曜日ヒマならCodeChef Long Challenge (通称ChefLong)にトライして精進してみてはどうでしょうか？
ChefLongは残り2日となりましたが取り組むには十分な時間がまだあります！

http://www.codechef.com/JUNE18
171仕様書無しさん
垢版 |
2018/06/10(日) 20:25:23.82
AtCoderの退会方法で盛り上がったみたいだけど
何で誰もchokudaiさんのツイートを見ないのだろう

https://twitter.com/search?q=退会%20from%3Achokudai&src=typd


https://twitter.com/chokudai/status/972175474934800384
https://twitter.com/chokudai/status/765824968428965888
2018/06/10(日) 20:52:20.40
chokudaiのツイート見なきゃ退会方法分からないってのが欠陥だって話でしょ
順位表に退会者がー、ってのは向こう側の理屈でユーザーからしたら知ったことではないし
2018/06/10(日) 21:50:02.94
退会できないサービスとかひっでえな
競プロやってるほどネットリテラシー高くても学生なんかパスワード使いまわしまくってるだろうしセキュリティは大丈夫なのか
2018/06/10(日) 22:11:33.01
退会したかどうかなんて外から分からないから気にすることないのに
2018/06/10(日) 22:42:03.25
中からは分かるだろ
途中で規約に賛同しかねる状況になったらどうすんの？
どの程度個人情報握られてるかとか全部把握してるわけ？
2018/06/10(日) 22:58:38.99
そうじゃなくて順位表云々の話でしょ
まあプロフィールとか消えるだろうから外からでも分かると思うが
退会フォームがないのは擁護できないわ
2018/06/10(日) 23:03:19.68
俺は初めから個人情報は国籍以外は虚偽の申告をしているので心配ない
178仕様書無しさん
垢版 |
2018/06/10(日) 23:13:32.31
AtCoderJobs を利用するのでなければ個人情報入れてもメリット無いな
2018/06/11(月) 01:40:16.21
Cの6^pと9^pを独立して考えてよいみたいなの分かるの数学的センスからくるのか？
2018/06/11(月) 03:12:54.19
Cookie の期限
2018/06/11(月) 08:45:38.91
取引先へのアピールのために気にしてそうだけど、直近一年でコンテストに参加したアクティブユーザー数なんかを見るだろうから、退会できないのは謎
2018/06/11(月) 08:52:04.81
個人情報とかコンテストでTシャツもらえるようになってから考えろよ。賞品配送先住所くらいじゃね漏れて困る情報
2018/06/11(月) 08:55:29.04
CF487今日だったか
2018/06/12(火) 01:57:13.66
TL眺めててコドフォ参加してる人たち楽しそうに思えた
そろそろ英語と真剣に向き合うべきか
2018/06/12(火) 01:59:00.95
英語できなくてもgoogle翻訳にぽいーでいけるいける
2018/06/12(火) 02:02:57.54
英語が原因で参加しない人とかいたんだ
2018/06/12(火) 09:42:49.37
例だけでも行ける行ける。やることはatcoderとおなしだから
188仕様書無しさん
垢版 |
2018/06/14(木) 07:24:00.23
日本語のサイトだけで手いっぱい
189仕様書無しさん
垢版 |
2018/06/15(金) 07:06:51.64
はむこ @hamko_intel

なんだって！？ある筋からの情報によると、今週のyukicoderは、はむこが作った6問が出るらしい…！難易度も★1, 2, 3, 4, 4.5, 5と、暇な主婦にもお手軽な問題が並んでいるとのことだぞ…

これは、出るしか、ない??
https://yukicoder.me/contests/200
2018/06/15(金) 10:15:08.04
マルチ止めろ
2018/06/15(金) 10:30:19.92
yukicoderは大事だな。
2018/06/15(金) 10:57:32.53
23時か寝ちゃう
193仕様書無しさん
垢版 |
2018/06/15(金) 20:44:10.13
＞2018-06-15 22:20:00〜2018-06-16 00:20:00のコンテストです。

なんでこんなに深夜なんだろ
2018/06/15(金) 20:55:39.18
yukicoderの管理人がブラック企業に勤めていて帰宅時間が22時だからと予想（完全な妄想です）
2018/06/15(金) 21:17:37.98
マルチってマ板だけか
2018/06/15(金) 21:46:35.35
はむこさんの問題ならこの2つから答え探索できそう

https://twitter.com/hamko_intel/status/1001630841703837696
http://home.wakatabe.com/ryo/wiki/index.php?%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0
2018/06/15(金) 22:17:43.41
才能を10段階で評価で無能を0、天才を9とするなら、一般凡人は2〜4程度
才能6〜7くらいの人がかなりの量の努力してやっと競プロ黄色というところか
2018/06/15(金) 22:34:46.89
バズったときyukicoderでの自作問題を宣伝することにより間接的に競プロを布教するテク
2018/06/16(土) 01:12:37.92
https://yukicoder.me/problems/no/702/submissions?lang_id=&;status=AC&sort_time=enabled&date_asc=enabled

No.702 中央値を求めよ LIMITED
100ms切る高速解法があるとは驚き
200仕様書無しさん
垢版 |
2018/06/16(土) 12:39:54.81
200げっと
2018/06/16(土) 21:41:57.17
WAが取れない（滝汗
このままでは無得点にｗ
202仕様書無しさん
垢版 |
2018/06/16(土) 21:49:48.86
俺もWAが取れない注意してるところを見逃してるのか？
2018/06/16(土) 21:58:13.02
B問題まじでひどいなこれwwww
ほんと笑う
2018/06/16(土) 22:27:34.12
わかんねー。(´・ω・｀)
寝るわ・・・・
2018/06/16(土) 22:57:26.07
Cは何を求めればいいかわからないです
206仕様書無しさん
垢版 |
2018/06/16(土) 23:00:41.41
cの説明文のｉが難しくしすぎてるよaiが中身なのにｉって言っちゃうかな数列の番号なのか中身の数値なのかあれじゃあ何言ってんだって言われるぞたぶん
やってほしいことはわかったけどさあ
2018/06/16(土) 23:01:41.43
え、今日ABCだったのorz
2018/06/16(土) 23:07:51.42
すべてのa_iに対して処理をするって書いたらa_i=a_jとなるa_jにも同時に同じ処理をするのかってなるじゃん
a_iとa_jは添字以外で区別できないんだからああ書くのが正確で単にあなたの読解力がないだけ
2018/06/16(土) 23:08:06.35
なんか今日のジャッジこどふぉ並に重かったな
2018/06/16(土) 23:52:36.84
さくっと確信をもって提出できたらもう少し上に行けそうなんだが提出する前に毎回これでいいのかと自問してしまう
今回のAとDは想定解法通りだったのだが本当にこれでいいのか、抜けはないかと考えて無駄に時間を消費する
数こなせばその辺の自信もつくのだろうか
2018/06/16(土) 23:54:15.02
テキトーに提出するよりそっちのほうが伸びるよ
2018/06/16(土) 23:55:25.43
aもbも解けなかった
213仕様書無しさん
垢版 |
2018/06/17(日) 00:07:30.92
全ての i に対して 3 倍することはできず, 操作後の ai の値は整数でなければならない
これが混乱するわ、aiの処理なのにiに足して処理するのかって困惑した
2018/06/17(日) 00:15:51.84
CodinGameでゲームAIコンテストがやってます(6/16〜6/26)
同じプログラミングコンテストでも競プロやマラソンとは少し違いますが実装力が身につくらしいです

https://www.codingame.com/contests/code-of-kutulu
https://www.codingame.com/leaderboards/challenge/code-of-kutulu/country/jp

CodinGameはコードの公開はコンテスト後でも禁止されてるようですが
戦略・戦術などはヒント程度のものであればコンテスト中でも語り合っていいようです

初心者の人はtsukamoさんをフォローしておくとヒントなどが得られます
https://twitter.com/tsukammo/status/1007987650865713153
https://twitter.com/tsukammo/status/1007900838113624065
2018/06/17(日) 00:21:04.68
Cで変な勘違いする人、普通に生活するのが大変そう
2018/06/17(日) 00:26:47.75
100分と言う制限時間が俺の冷静な判断力を奪う
2018/06/17(日) 00:37:19.42
双子はこのスレを見ている可能性が微レ存
2018/06/17(日) 01:22:25.05
今時の中高生が2chなんて見ないだろ
2018/06/17(日) 01:45:36.75
おじいちゃん2chは5chに改名したんだよ
220仕様書無しさん
垢版 |
2018/06/17(日) 06:54:26.78
ABC昨日だったんか！
2018/06/17(日) 12:12:59.17
AOJでC++のset使うとRE出るの俺だけ？
2018/06/17(日) 14:14:41.04
ソースコード晒せばこのスレの住人たちがマサカリ投げてくれそう
2018/06/17(日) 16:09:33.37
このソースの39行目です。
https://pastebin.com/QU3wArp7

アホー知恵遅れにも投げたので知恵コイン欲しい方はどうぞ
https://m.chiebukuro.yahoo.co.jp/detail/q13191909163?__ysp=Qysr
2018/06/17(日) 16:49:34.96
解決しました
スタックオーバーフロー（バッファオーバーフロー？）が原因でした
2018/06/17(日) 20:11:08.46
昨日の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)の組は存在しない(存在したら真の解とはらず矛盾する)というあたりから攻めていった
2018/06/17(日) 20:17:45.06
ややこしいことしてんな
前半の不等号に等号含めれば終わりだろ
2018/06/17(日) 20:18:33.34
なるほど！サンキュー！
2018/06/17(日) 22:34:24.38
|x| = max(x, -x) なので max(Σx, -Σx) + max(Σy, -Σy) + max(Σz, -Σz) の最大値を求める問題と見ることができる
これが一番しっくりきた
2018/06/17(日) 22:44:11.15
数学力の差が競プロ力の差に繋がる事例
2018/06/17(日) 22:49:55.56
答えの形が±Σxi±Σyi±Σziのどれかしかないんだから8通り全部試して終わりじゃん
絶対値バラすだけで数学って笑
2018/06/17(日) 22:57:41.85
絶対値が出てくる問題では正負の場合分けの可能性も考慮するのが典型思考？
2018/06/17(日) 23:02:21.63
そう思うのは勝手だけどなんでいちいちマウント取ってくるんだろうね、こういうことするからやるだけハラスメントとか揶揄されるんだろうな
2018/06/17(日) 23:05:02.71
競プロの問題を解くAIを思いついた

-対象は過去問のみ
-問題のURLを与えると解答コードを即座に出力
-その実態はURLからACコードを引っ張ってきてコメントや未使用マクロ等の削除、マクロの展開、変数名関数名を適当な文字に置換、適当なフォーマッタでコードの見た目を調整、あたかもオリジナルで生成したコードかのように見せかける
2018/06/17(日) 23:11:09.26
的外れなこと言ってるからだろ
2018/06/17(日) 23:14:06.07
まああれが数学力だと言われるなら競プロは数学だな
2018/06/17(日) 23:15:43.53
競プロの問題を生成するAIを思いついた

-アルゴリズムを指定するとそのアルゴリズムが解法に含まれる問題を生成する
-その実態はアルゴリズム分類されてるCSAなどの英語の問題を日本語に機械翻訳した結果をあたかも生成した問題かのように見せかける
2018/06/18(月) 01:19:09.56
https://twitter.com/search?vertical=default&;q=atcoder%20youtube&src=typd

atcoderの実況やっている人あまりいないね
2018/06/18(月) 01:28:23.34
YouTube内を「動的計画法」で検索すると説明している動画が色々と出てくるのだけど
DP分からないと言っている人たちはこういう動画をチェックしているのだろうか
239仕様書無しさん
垢版 |
2018/06/18(月) 02:01:01.31
＞AtCoder、凄い色んな人にやってもらってるイメージが自分の中であるけど、日本人数百人くらいなのよね。

なのにAtCoder社が続けられるのはすごい
2018/06/20(水) 23:38:42.31
アリ本の最小費用流のコラム(P205)で、流量が正である辺のコストの和の最小化のような問題になったら
他の解法を考えろと書いてありますが、この問題を解く効率的なアルゴリズムってないのでしょうか？
2018/06/21(木) 23:53:44.57
蟻本持ってない競プロerなので
2018/06/22(金) 00:00:36.93
Div3にみんなよく出る気になるな
Div2と違って全完強いられるみたいで辛みしかない
243仕様書無しさん
垢版 |
2018/06/22(金) 00:22:43.16
7月20日25時(=7月21日1時)から3日間のチーム戦のプログラミングコンテスト ICFP Programming Contest 2018 があります！
chokudaiさんらのUnagiチームが活躍したことで有名です！

参加資格は特になくチームといっても人数1名のぼっちチームでも参加可能らしいです
複数人でチーム参加する場合は生活スケジュールの調整もあるでしょうし早めにチームを組んだほうがよさそうです！
過去の参加記などを読むと作業量が多いようでチーム内で作業分担するのが一般的な戦略のようです！(ぼっち参加する人はかなりの実装力が求められそうですね！)

https://twitter.com/ICFPContest2018
https://icfpcontest2018.github.io
244仕様書無しさん
垢版 |
2018/06/22(金) 12:20:03.64
＞流量が正である辺のコストの和の最小化

問題知らんがクラスカルのアルゴリズムのことか？？？
245仕様書無しさん
垢版 |
2018/06/22(金) 20:33:38.40
社会人オンリーのプログラミングコンテストが開催されるらしいぞ
30歳以上には特別枠があるらしいぞ

https://twitter.com/kenkoooo/status/1010059919863656448
https://twitter.com/chokudai/status/1010052170777911296
https://soundhound2018-summer-qual.contest.atcoder.jp

会社の同僚に競プロ布教するチャンスだな！
246仕様書無しさん
垢版 |
2018/06/22(金) 20:41:02.82
http://oldcar-purchase.com/
2018/06/22(金) 20:43:11.99
既卒（大卒）
社会人（非無職）

コンテスト詳細からして中途採用とも関係は無さそう
(SoundHoundを気に入った英語出来る青色以上コーダーが自発的にAtCoderJobs経由で応募する形か)
248仕様書無しさん
垢版 |
2018/06/22(金) 21:40:09.71
＞社会人オンリー

これはびっくり！
2018/06/22(金) 22:39:12.90
全く無関係の他社の社員をもてなすコンテストか
250仕様書無しさん
垢版 |
2018/06/22(金) 22:52:15.20
いや、熟練の他社社員を引き抜こうという意欲的なコンテストだろう
2018/06/22(金) 23:04:59.36
>>247
社会人なら最終学歴が中卒でも大丈夫そうだな
https://twitter.com/kenkoooo/status/1010063455452200961
2018/06/22(金) 23:07:21.89
30歳以上の定員割れを気にしてるみたいだから
30歳以上なら何色コーダーでもワンチャンあるか

https://twitter.com/kenkoooo/status/1010107255579033600
2018/06/22(金) 23:21:09.28
予選や本戦当日にスケジュールが空いてる社会人のみがオンサイト枠のライバルだから結構な人にチャンスがありそう？
2018/06/22(金) 23:23:43.16
交通費も少し出るみたいだしちょっとした東京旅行ができたりするのかな
2018/06/22(金) 23:45:44.10
辞書的な意味の『既卒』なら単に学校を卒業した人って意味なはずだが
リ○ナビなどの新卒業界が作り出した造語の『既卒』の意味(新卒就職失敗して卒業した人の意味)に勘違いしてる人がチラホラいて良くないね(Wikipediaにはその造語の意味が載ってしまっている)
2018/06/22(金) 23:49:17.00
非学生と書いたほうが分かりやすかったのではないか
■ このスレッドは過去ログ倉庫に格納されています
5ちゃんねるの広告が気に入らない場合は、こちらをクリックしてください。