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

■ このスレッドは過去ログ倉庫に格納されています
2020/06/15(月) 00:23:23.42
プログラミングコンテスト(プロコン)やオンラインジャッジや競技プログラミング(競プロ)や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/proj
※前スレ
競技プログラミングにハマるプログラマのスレ 25
https://medaka.5ch.net/test/read.cgi/prog/1588952913/
2020/06/28(日) 01:43:49.24
突き合わせというか愚直解のメモ部分圧縮して埋め込むイメージ
2020/06/28(日) 01:43:57.75
Dのままだと恥ずかしいからやるのか？
Dのままでも就職くらいできるだろ
2020/06/28(日) 01:46:37.98
D行って就職できないという話はちょくちょく聞くが本当なのだろうか
2020/06/28(日) 01:47:14.10
逆に聞くがDできたから採用しようって思うか？
2020/06/28(日) 01:51:16.66
D取れるなら人格破綻してるかハリボテのDでない限り採用されるんじゃない
俺の知る範囲だと中退ばっかみるし
2020/06/28(日) 01:53:59.52
Dって茶色？派遣のフィルタには使えそう
新卒ならどうでもいい情報
2020/06/28(日) 01:59:25.43
なんか噛みあわねえなと思ったらPh.Dの話じゃないのね
2020/06/28(日) 02:02:17.78
何故philosophy
2020/06/28(日) 02:06:42.09
JobsのDランクじゃなくてPh.Dの話だったのか
ABCのDのレスも挟まってこれもうわかんねぇな
2020/06/28(日) 02:06:59.84
俺がアスペだから
2020/06/28(日) 02:24:19.88
生物Dはピペドって話よく聞くけど情報Dはどんな状況なのかな
2020/06/28(日) 02:27:36.31
>>773
歴史的経緯
2020/06/28(日) 02:32:40.27
ぼくはね、こんかいのDで10^7ならN log Nがとおることをまなんだよ
2020/06/28(日) 03:54:21.34
>>757
事務でそんだけ貰えるのは超勝ち組で羨ましい
日本は年収1千万のまったり私大職員が、年収600万の激務プログラマに
仕事を発注する国だから…
2020/06/28(日) 04:34:27.48
>>778
うせやろ…？通るんか？
2020/06/28(日) 05:47:43.63
特定の言語でTLEするなら、その旨は解説じゃなくて
問題文に書くべきだろ
2020/06/28(日) 05:55:42.91
〇〇言語で間に合いそう/間に合わなそうは問題に対する考察の一部なのでコンテスタントが考えるべきだと思う
（もちろんライターやテスターは幾つかのメジャーな言語についてはTLや制約の検討の際に意識したほうがよいとは思うが、コンテスト中に伝えるべきではないという意味）
2020/06/28(日) 05:58:26.33
どの言語を使うかの選択を問題に含めるかどうかで意見が分かれそう
2020/06/28(日) 06:02:19.99
だってO(N)でTLEしそうなら、TLEは正答解法で間に合うように設定されている
はずだから、O(1)解法があるのかって考えるのが普通でしょ
それとも、「TLEは正答解法で間に合うように設定されている」と考えるのが
そもそも間違いだと言うの?
785仕様書無しさん
垢版 |
2020/06/28(日) 06:10:17.55
＞それとも、「TLEは正答解法で間に合うように設定されている」と考えるのが
そもそも間違いだと言うの?

相対的に遅い言語を使っている場合は間違いだと思う。 逆に質問するけどBrainfuckや生bashを使っている
人が「TLEは正答解法で間に合うように設定されている」と想定するのも正しいと思う？
自分はまったく思わない。これらの言語はシリアスにコンテストの成績を求めるなら到底向いているとは言えない、
だけど使えないようにするよりは使えたほうが楽しいからという理由であるものだと思っている。

あなたが正しいと思っているなら同意しないけど主張は興味深いな、という感じ。
思っているなら、程度問題でどこかに線引きがあるという合意に達しそう。
2020/06/28(日) 06:23:01.17
頑なに解説ACを拒む人:「あれ、D問題にしては難しくね…?」
→1か月後、遂に解説を見る:「畜生、言語選択を間違えたッ!!!」
2020/06/28(日) 06:34:31.37
与えられた制約、時間制限、メモリ制限の下でACできるかがすべて
シンプルなゲームだろ？
2020/06/28(日) 06:51:39.57
「TLEは正答解法で間に合うように設定されている」かどうかは運営の方針次第
なので、アナウンスされているなら正しいし、アナウンスされていないなら
正しいとは限らない、それだけでは?
2020/06/28(日) 07:11:23.50
運営の方針はC++,Java,C#は間に合うことを保証するだったはず
2020/06/28(日) 07:20:31.11
「心苦しいですが、C++をお使いください。C++でしか、間に合いません」
2020/06/28(日) 08:24:23.38
>>758
数独で飯が食えるんですかね
2020/06/28(日) 08:25:54.26
C問はC++よりPythonで解ける人の方がレベル高いよね
793仕様書無しさん
垢版 |
2020/06/28(日) 08:55:32.49
>>792
そう？私は優劣ないと思う
2020/06/28(日) 09:05:16.18
Pythonならbisectあるから楽チンだよ
795仕様書無しさん
垢版 |
2020/06/28(日) 09:58:50.70
>>779
757だけど、atcoderで青とかいくほどの高学歴だったらわりとそれぐらいもらってるイメージ
（自分も早慶（文系だけど）だし）
2020/06/28(日) 10:10:29.70
Dはね・・・競技中は倍数インデックスいけそうなことは薄々勘付いてたんだよ
2 3 4 5 6
2 . . .
3 . .
5 .
みたいな感じにいけそうだなって
でも、素数じゃなくて↓普通にやるのがわからなかった
1 2 3 4 5 6
1 1 1 1 1 1 1
2 1 1 1
3 1 1
4 1
5 1
6 1
2020/06/28(日) 10:11:30.80
約数って聞いて拒絶反応起こしたけど倍数足すだけかよ修行が足りんかった
798仕様書無しさん
垢版 |
2020/06/28(日) 10:18:41.65
D問題のΣkg(k)に、どんな意味があるのか整数論とコンピューターサイエンスの専門家にインタビューしてみてほしいわｗｗｗ
2020/06/28(日) 10:55:52.08
>>798
与えられた仕様の見た目に比べて遥かにアルゴリズムが簡単というプログラムの本質に迫る意味
2020/06/28(日) 11:19:26.19
心苦しいですが、間に合う言語はありません。
あまりに苦しくて、涙が溢れてくるのです。
2020/06/28(日) 11:31:46.52
>>799
どんな業務の、どんな場面で、どう使うのか、具体的に述べなさい
そして、それは総業務時間における何%の時間を占めるのか、合わせて答えよ
2020/06/28(日) 11:51:29.18
>>785
あそう、そう「思う」のね、きみがそう「思う」ならきっとそれはそうなのねw
単に言語別にTime Limitを設定すればいい話だと思うんだけど
きみがそう「思う」ならきっとそれは真実だよ!
2020/06/28(日) 12:03:55.22
>>785
ねえ、きみは宇宙はどうやって始まったと「思う」?
あと、生命はどうやって誕生したと「思う」?
賢い君が「思う」ことはきっと真実だから、「興味深い」意見を聞かせておくれよ!
2020/06/28(日) 12:05:51.71
Dは10^7にした意味はなんだったんだろう
わざわざ3secにしなくても10^5なら2secに出来たのでは
805仕様書無しさん
垢版 |
2020/06/28(日) 12:12:11.04
順位表の描画がクソ重いのどうにかして
2020/06/28(日) 12:32:56.14
>>804
それだとO(n^1.5)が通るから
2020/06/28(日) 12:33:29.56
D問題が解けなかったからって掲示板でストレス発散しても何も解決しないぞ！
2020/06/28(日) 12:49:31.14
>>802
言語別に適切な制限時間なんて無理だろ。
同じ言語で同じアルゴリズムを実装しても実装方法によってはある程度の幅が出るからそれを見越して制限時間を決める必要があるが、異なる言語も含めて公平に設定することなんてできない。
遅い言語を使った方が制限時間が緩くて正解の方法でなくても通ってしまい有利だったなんてことが起こるくらいなら、同じ制限時間で遅い言語では間に合わない、嫌なら速い言語を使えって方がよほど公平だと思うぞ。誰でも好きな言語を使用して良いのだから。
2020/06/28(日) 13:02:22.88
勉強目的なら別にいいと思うけど競技してるのに自分の使ってる言語遅いって言い訳する人はよくわからんな
2020/06/28(日) 13:17:55.21
>>799
フォームからDBへのデータの受け渡しは、プログラミングの本質なの、非本質なの?
非本質的なプログラミングについて、端的に定義を述べてくれたまえ
2020/06/28(日) 13:29:19.90
僕は数学パズラー 豆コーダー
数え上げるし 構築するよ?(いつ、どこで使うんですか、それ?)

僕は数学パズラー 豆コーダー
Xorには詳しいよ?(いつ、どこで使うんですか、それ?)

こんなに賢い僕だけど(競数パ専門知識があるだけでは?)
役に立たないとか言われると ガチでキレるよ?(IPA資格より更に現実離れしてますよ?)
2020/06/28(日) 13:43:38.33
pythonistaのみんなが一定額課金すると全参加者のpython時間制限を一定期間個別に調整してもらえるゲームシステムちょうだい
813仕様書無しさん
垢版 |
2020/06/28(日) 13:47:40.47
D問題がPythonで通せないわけないと思ったけど10^7だったからマトモな解法じゃないと思って初手OEISした
想定解はまったく理解してない
2020/06/28(日) 14:06:05.71
普通に理工系出て就職するなら、atcoder不要だよね。
F欄だけど青コーダーみたいな人は活用できるけど、マーチで緑だと普通でアドバンテージないじゃろ
2020/06/28(日) 14:10:09.40
>>814
TOEICスコア600みたいな？
2020/06/28(日) 14:25:46.85
TOEICは英語力の担保になるから有用みたいよ
会社によっては転職や昇進の条件になってる
2020/06/28(日) 14:28:44.79
なんかキモいやつ増えてきたな
遅い言語使ったらTLEしやすいし速い言語使ったらTLEしにくいのは当然だろ
2020/06/28(日) 14:34:54.28
競プロ全否定するだけで精神保たれるならそうすればいいけど
そういう人って業務プログラムも平均より出来るイメージはないな
2020/06/28(日) 14:35:07.08
そりゃこんだけユーザー増えればアホも増えるよ
2020/06/28(日) 14:39:53.39
>>818
前スレのこれマジだと思う
「学歴は関係ない」って本気で言ってる高卒とやってる事変わらん

741 仕様書無しさん sage 2020/06/04(木) 12:02:16.78
まあわざわざこんなニッチな趣味のアンチになるって嫉妬以外考えられないからな
本当は活躍したかったけど緑にすらなれなかった雑魚の成れの果てってとこだろ
あるいは精々が競プロ勢に居場所奪われる危機感覚えてるエンジニア
2020/06/28(日) 14:49:22.62
素朴な疑問なんだが、昨日のDをOEISに突っ込んでる人って競技プログラミングしてて楽しいんか？
何を目指しているのかよくわからん
2020/06/28(日) 14:50:18.39
人によるだろって言われると、まあそうなんだけど
2020/06/28(日) 14:53:36.13
>>814
新卒ならどうせ教育するから今緑だろうが水色だろうがどっちでもいいよね
余分な自尊心も付いてくるならむしろ害まである
2020/06/28(日) 14:54:14.98
>>821
単にコンテスト中にできることなくなっただけだろ
2020/06/28(日) 14:54:36.52
>>818
イメージだけのお気持ち表明はTwitterでやって
2020/06/28(日) 14:54:37.04
Introduction to Heuristics Contestとは
2020/06/28(日) 14:55:55.43
>>821
ルールに則ってる訳だしゲーム勢なら普通に楽しいんじゃね？
マリオカートでショートカット使うようなもん
2020/06/28(日) 14:58:56.32
アンチというか、学歴に比例するのはチョクダイも認めてるからどうすんだろうなって
完全にネトゲじゃん。楽しいけど
2020/06/28(日) 15:09:46.63
E-sportsだよ
2020/06/28(日) 15:10:35.98
問題をACして得点を得る競技なんだから埋め込みでもOEISでも使えるものは使うだろ
2020/06/28(日) 15:18:07.73
とりあえずC++使っとけの精神、一理ある　C++使えたら普通に重宝するので
言語によってはTLEになるならならない言語さがせばいい（でも適当な定数倍するとかでちょっとは調整してほしいな）
むしろTLE解法で解こうとするなよ。#pragma使いか？
あと競プロで就職が有利に焦点絞るのはちょっと違う
役に立たなくてもキレるな。サッカーが就職の役に立ちますか（面接の話題作りとか体力＆コミュアピ以外で）
そんな奴がいたとして、その愚痴をここに吐き出す必要がどこにあるんですか
2020/06/28(日) 15:19:03.09
なお私はC++使えない
2020/06/28(日) 15:28:00.75
就職のためにやるなら3か月くらいやってやめるのが最適で
それ以上にやってるのはただの趣味だよ
2020/06/28(日) 15:30:03.16
プログラミングの本質(笑)
835仕様書無しさん
垢版 |
2020/06/28(日) 15:31:30.23
青以上にほぼ精進せずにいけるのって、数オリ予選余裕通過ぐらいじゃないと無理そうで、そのレベルに優秀だったらそもそもatcoderいらないのではと思うし
精進して上がった人はある程度は大学の学業とか研究がおろそかにならざるをえないだろうし
採用担当としてはなんだかなあという感じ
836仕様書無しさん
垢版 |
2020/06/28(日) 15:32:05.82
言語別にTLE設定とかをするとPythonにC++を埋め込んだりしてズルできてしまうのでダメです
2020/06/28(日) 15:35:04.28
OEIS知らなかったけど、立ってるものは親でも使えって言う感じですな
2020/06/28(日) 15:35:07.95
bashでbase64エンコードしたバイナリ送り込んでbashでのAC稼ぐのはやった
2020/06/28(日) 15:41:42.88
>>835
あらゆる趣味がそうなんだが

> 採用担当としてはなんだかなあという感じ
これまさかご自身が採用担当だとおっしゃってるんですか？笑
2020/06/28(日) 15:41:58.96
そう言えば言語アップデート来たからRustの練習するかな。200点問題や
2020/06/28(日) 15:44:51.28
御社は学生時代に何も打ち込まなかった人を評価してるんですね
2020/06/28(日) 15:48:47.06
TLEに文句言っている層ってどういう層なんだ
勝手なイメージだとpython使っている人だと思うんだが
2020/06/28(日) 15:50:44.82
pythonもjit使えるからatcoderでは捨てたもんじゃないと思うぞ
ではjit解をACさせてしんぜよう
2020/06/28(日) 15:51:32.23
>>841
将棋アマ初段です!
845仕様書無しさん
垢版 |
2020/06/28(日) 15:58:38.69
>>835
あなたみたいなのがいるところに、私たちのような優秀な競プロerは入らないので大丈夫でちゅよ
2020/06/28(日) 16:23:05.42
>>814
緑できれいなコード書いてるなら有りかな
2020/06/28(日) 16:24:20.96
プログラミンの本質は論理演算手順の最適化じゃない？
2020/06/28(日) 16:33:05.49
>>841
まともに研究もできない人間は何に打ち込むとか以前に足切りかな…
2020/06/28(日) 16:33:48.55
ABC158 D
RubyでO(|S|+Q)やってTLEなったからCrystalでやったらACなってワロタ
RubyからCrystalに書き換えるには、getsのあとに.not_nil!をつけるだけ
あと文字列は全部""
2020/06/28(日) 16:39:30.84
40前に黄色とれたらウルトラホワイト社内SEに転職できますか？
2020/06/28(日) 16:39:32.12
お、gets.not_nil!じゃなくて、(gets || "")にすればRubyでもCrystalでも動くコード書けたわ
2020/06/28(日) 16:56:30.11
中途だと新卒以上に競プロ以外の能力求められそう
2020/06/28(日) 16:59:20.62
高校生でも水色ぐらいなんぼでもとれるしね
競プロの立ち位置は緑未満で足切りって程度かな
2020/06/28(日) 17:03:49.74
ABC172 Fを上位桁からの桁DPで実装しようとしたのですが、
あまりの場合分けの多さに途中で投げ出してしまいました
しかし、すぬけさんの実装を真似て下位桁からの桁DPで実装すると、ものすごく楽に実装できました
なぜここまで楽に実装できるようになったかがわかりません

そこで質問なのですが、上位桁からの桁DPか下位桁からの桁DP、どのような判断基準で選ぶのが最適でしょうか？
繰り上がりが発生するときは下位桁からの桁DPのほうがいいのかな？と思ったり思わなかったり…
回答よろしくお願いします
2020/06/28(日) 17:13:34.71
>>847
仕様決めて設計してテストする。だよ
あとはコードの可読性と、仕様と設計のドキュメント
2020/06/28(日) 17:14:50.38
>>850
社内SEは業務と忠誠心みたいのが重要じゃね?
2020/06/28(日) 17:15:01.32
>>851
おー、それならJavaやc#覚える必要なさそうか
2020/06/28(日) 17:16:45.58
どうせ仕事でJava覚えないといけなくなるで
2020/06/28(日) 17:18:07.90
PythonとかいうPyPyのおかげで市民権得てるクソ言語
と言いつつオーバーフロー考えなくていいのが便利すぎて他に移る気になれない
860仕様書無しさん
垢版 |
2020/06/28(日) 17:35:01.22
昨日のEですが、Aiがiと等しくないより、iと等しい、の方が考えやすいので余事象を考える、
となる思考過程がいまいちわかりません(考えやすい、という感覚)。解けた方はどうやって余事象を考えようと思って、包除に帰着しましたか。
2020/06/28(日) 17:41:34.03
両方考えるだけ
2020/06/28(日) 17:44:51.31
感覚的な話になるからアレだけども
A_i = i かつ A_j = j の場合の数は簡単に求められるけど A_i != i かつ A_j != j は求めにくいということからA_i = i から攻めたいという気持ちになれるかって点がある
https://mathtrain.jp/montmort
ここの最後の包除原理を用いた導出が参考になるかも知れん
2020/06/28(日) 17:54:34.99
>>859
こないだのIEEE754のfloat桁落ち問題はハマったわ。decimal使えば強引に行けたけど
864仕様書無しさん
垢版 |
2020/06/28(日) 17:54:44.54
>>862
確かに!=の「かつ」でやろうとすると考えにくそうな気持ちになるのもわかる気がします。URLも参考になりました。(これを知ってるとちょっと有利かもしれませんね)
ありがとうございます。
865仕様書無しさん
垢版 |
2020/06/28(日) 18:05:21.66
すみません、昨日のEについての質問をしたものですが、
もしatcoderかこどふぉなどに類題が有れば教えていただけないでしょうか。
2020/06/28(日) 18:13:28.74
今日はIntroduction to Heuristics Contestだぞみんな出るよな
■ このスレッドは過去ログ倉庫に格納されています
5ちゃんねるの広告が気に入らない場合は、こちらをクリックしてください。
ニューススポーツなんでも実況