競技プログラミングにハマるプログラマのスレ 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/21(日) 00:26:23.11
D通せるようにならないとなあ
2020/06/21(日) 01:07:36.37
数え上げ、つまらん
2020/06/21(日) 01:32:40.79
B水Diffなのか…
2020/06/21(日) 02:00:14.07
Nosubよくやるからサンプル合わせれば大体正解な数え上げは好きだわ
2020/06/21(日) 02:32:10.67
遠隔授業で暇な大学生だけど最近AtCoderしかやってない
でもAtCoderしかやってないと（まだ灰なのに）AtCoderしかない奴になりかねないから
数学の復習とか他のこともやっとこうじゃん
2020/06/21(日) 02:40:13.30
チラシの裏にでも書いてろ
2020/06/21(日) 02:53:26.44
なんでこここんなに殺伐としてるんですかね…
2020/06/21(日) 02:55:35.66
>>357
あっとこーだーだけにやっとこうじゃん、ってかｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗ
2020/06/21(日) 02:57:00.51
>>360
あ、バレた？
2020/06/21(日) 02:59:52.45
>>361
遠いわ
2020/06/21(日) 03:03:55.89
>>352
またevimaとケモナーか
2連続で解説やらかしたら逆に応援するわ
364仕様書無しさん
垢版 |
2020/06/21(日) 03:25:20.26
しかしアースンライタなんて起用し続けていい事なんてあるのかね(´・ω・`)
2020/06/21(日) 15:25:50.25
頂点に非負の重みがある木について、合計の重みが最大となるパスを調べたい
木の直径を求めるアルゴリズムと同じようにやると
微妙に問題が違う気がするけどこれで合ってる？
2020/06/21(日) 15:28:37.90
木の直径を求めるアルゴリズムはいろいろあるのでどれを想定しているのか言ってくれ
367仕様書無しさん
垢版 |
2020/06/21(日) 15:38:20.84
2回dfsするやつ
2020/06/21(日) 15:40:59.45
重みつきの木を考えるときは、重みWの辺1辺を重み1の辺W辺に分解して考えると考えやすいぞ
ダブルスイープが上手くいくことも分かるぞ
2020/06/21(日) 15:56:18.19
全方位木DPでしょ
2020/06/21(日) 16:15:32.15
頂点を >o---o< みたいな2頂点に分割し、分割された2頂点を結ぶ辺の重みを元の頂点の重みにして、それ以外の辺の重みを0にすると木の直径に帰着されます
2020/06/21(日) 22:42:53.18
今回ヤバイな
灰coderだけど水perf出て茶に成り上がった
2020/06/21(日) 22:45:02.94
おめでとう
ところで今回の解説は見た感じしっかりしてるな
2020/06/21(日) 22:46:25.25
DECの順番にしろ
難易度おかしいだろ
2020/06/21(日) 22:47:13.80
E問題のお気持ちが自明すぎたな
2020/06/21(日) 22:48:39.84
初めて5完
地味にCが難しかった
37564
2020/06/21(日) 22:49:26.01
xorの気持ちに親しみすぎた競技プログラマー達
2020/06/21(日) 22:49:27.50
D解けてたのに考え事してたら提出しそこねた
あー悔しいなあ
2020/06/21(日) 22:50:22.15
解説が丁寧でワロタ
2020/06/21(日) 22:51:23.63
解説が丁寧すぎて笑った
380仕様書無しさん
垢版 |
2020/06/21(日) 22:52:40.34
C、26進数から微調整する方針で全然合わなくて諦めた、その前の桁の分もあるのに気づかなかった・・・
381仕様書無しさん
垢版 |
2020/06/21(日) 22:53:50.49
Aから過去のE,Fくらいの量の解説あって草
2020/06/21(日) 22:54:41.05
>>380
ナカーマ
毎回-1しないといけないのわからなかった
2020/06/21(日) 22:57:13.25
でも解説のコード間違ってる
aとAが逆になってる
2020/06/21(日) 23:13:53.64
解説がクソ丁寧になってて草
2020/06/21(日) 23:19:32.13
解説笑ったわ
最初からやれ
2020/06/21(日) 23:19:37.12
ABCなのにDPもBFSも出ない・・・だと・・・！？
2020/06/21(日) 23:20:02.45
>>371
実力やぞ。誇れ。
2020/06/21(日) 23:20:25.71
C問で沼にハマる人やってた
389仕様書無しさん
垢版 |
2020/06/21(日) 23:25:46.66
AとBのアホ問題枠をやめて、典型的な問題も入れれば良いのに・・・
2020/06/21(日) 23:27:50.50
Cは仕事のデバッグ経験が活きたなー
競プロは仕事の役に立たないけど仕事は競プロの役に立つ（？）
2020/06/21(日) 23:44:01.40
Nが偶数ならやるだけなんだけどなーと思ったらやるだけでびっくりした
2020/06/21(日) 23:58:37.99
F組み合わせかー全然分からなかったわ
2020/06/22(月) 00:33:36.35
F多項定理と勘違いした
2020/06/22(月) 00:44:27.32
競プロはじめたぱっかなんだけど、今回のFみたいな問題ってどういう風に解けるようになる？
解説見た感じ典型的な解法使う問題じゃないじゃん？
沢山の問題解いてればこういうのも思いつきやすくなるの？
2020/06/22(月) 00:51:05.57
部分文字列に元の文字列を含む場合の数と言い換えた後、DPテーブルを書いて眺めたら気づいたから、
僕のやり方ではあまり突飛な発想は使わなかった
2020/06/22(月) 01:09:49.22
とりあえず、問題文に書かれている操作に対して結果が一つではないように見える→まずは結果と一対一対応するような操作のルールを考えよう、が超典型で、個人差はあれど黄色くらいまでにはだいたいみんなできるようになる。
（もちろんこの典型思考ができても思いつくとは限らないけれど、典型を知らないとハードルが少し上がる）
2020/06/22(月) 01:11:07.03
×結果が一つではないように見える
〇結果が一対一に対応しないように見える
だった
2020/06/22(月) 01:35:27.04
(|S|+K)C(K)だと思ったら結果が違うからおかしーなーとかやってたら時間切れで死亡した
2020/06/22(月) 02:37:27.32
某エントリ読んで、学歴によって見える世界が全然違うんだなあと思った。
2020/06/22(月) 02:42:46.44
今日めちゃくちゃ平和じゃん
こういうのでいいんだよ
2020/06/22(月) 02:55:12.87
今日凄くいい回だったと思うけど、典型的なアルゴリズムが全くでないのもどうなんだろう
頑張って精進してる（し多分頭も自分より良い）知人達が、全く勉強してない自分よか順位低かった
2020/06/22(月) 02:55:56.79
>>399
具体的に頼む
エントリは伏せてていいから
2020/06/22(月) 03:01:59.32
いやー全体的にdiff低すぎないか、これ早解きで橙パフォ出るのはなー…
まあこういうこと言ってると崖やら難易度逆転やらで「理想のコンテスト」が10回に1回くらいしかなくなるんだけど
2020/06/22(月) 03:06:37.74
>>402
学歴によって競プロの問題の難易度が全然違うってことね。
学歴というよりは算数的センスかな。

人によって当たり前は違うんだなと再認識した。
俺より頭良い奴の当たり前は、俺にとっては当たり前ではなかったりするだろうしね
2020/06/22(月) 07:11:28.17
算数の教養がほぼ0のプログラマが1年間AtCoderをやった結果の振り返り｜きりみんちゃんノート｜note
https://note.com/kirimin_chan/n/n889ec80b6fbc
2020/06/22(月) 07:13:00.15
高度なプログラムを組むことと、
実務でチームで組むプログラムは全く違うものだということらしい。
2020/06/22(月) 07:38:37.49
競プロの典型要素はABC-Eくらいに多いから
それ未満が算数ばかりなのはそれはそう
2020/06/22(月) 08:01:38.70
本当に数学というか算数全くわからないエンジニアっているんだなと勉強になった
2020/06/22(月) 08:06:35.46
>>404
どうも。算数的センスの方は納得（学歴はちょっと違うと思った）

該当noteの内容って至極当たり前だと思うんけど、新鮮な気持ちで受け取ってる人が多いのが逆に新鮮
2020/06/22(月) 08:17:51.46
低難易度で典型アルゴリズムが出なすぎるのが問題
B問題あたりで疑似コードが与えられるからその通り実装しろみたいな問題だしたら？
2020/06/22(月) 08:23:18.54
一般論として、「幼女」って言葉がクソきもい
公の場で使っていい言葉ではない
ペド丸出しじゃん
2020/06/22(月) 08:30:12.35
アルゴリズムの問題は出るけど
必ず数学を絡めてくるのが問題
単純にバブルソート実装しろってだけでいいのに
変に便利な関数とか使えちゃうと問題の意味ないからなぁ
2020/06/22(月) 08:59:50.37
Q#コンやろう！！
https://codeforces.com/contest/1357

だいじょぶこわくないよカンタンだから！！
行列できる人ならとてもかんたん！
2020/06/22(月) 09:07:28.91
基本的な量子ゲート一覧
https://en.wikipedia.org/wiki/Quantum_logic_gate

例：与えられるqubitが0か1かを判定する
operation Solve (x : Qubit) : Int { // xは与えられるqubit
　let result = M(x); // 測定
　if (result == Zero) { // 結果が0なら
　　return 0; // 0
　} else { // 1なら
　　return 1; // 1
　}
}

例：与えられるゲートがEかXかを判定する
operation Solve (unitary : (Qubit => Unit is Adj+Ctl)) : Int {
　using (x = Qubit()) { // 自分でqubitをつくり
　　uniary(x); // 適用する
let result = M(x); // 測定
Reset(x); // リセット (これをしないと実行時エラー）
　　//略：結果がZeroならE、OneならX
　}
}
2020/06/22(月) 09:17:23.83
Twitterやってると、Atcoderやってる人の過半数が東大卒な感じがするし、過半数が中受経験者な気がしてくるな
その辺りの統計あったら面白いのに
2020/06/22(月) 09:27:37.65
>>413
これって何を競ってるの？
問題文公開されてからACするまでのタイム？
417仕様書無しさん
垢版 |
2020/06/22(月) 09:35:22.92
>>412
ほんと？コピペするだけになるよ
2020/06/22(月) 10:06:08.54
>>415
東京の高校生も多そう
部活の先輩とかに教えられてるのかな
2020/06/22(月) 10:17:33.12
学歴なくても数学しらんくても黙って2000ACすれば黄色なれるよ
2020/06/22(月) 10:19:31.26
ただし虚無埋め、テメーはダメだ

数ある謎風習の中で虚無埋めだけはほんとに意味分からん
簡単に解ける問題をわざわざ解くって、生きる才能がないだろ
2020/06/22(月) 10:26:14.00
解けない問題ばかり解いているとストレスがたまるから
ついつい虚無に手が伸びてしまう
2020/06/22(月) 10:28:49.69
AtCoderには1000問以上の虚無があるけど
2000問はないのである程度の実力がないと無理だとおもう
2020/06/22(月) 10:39:03.99
競プロって言ってるけど普通に数学パズルコンテストだししゃあない
2020/06/22(月) 10:39:06.14
虚無って灰diffの問題?
茶色は時々落とすんだよな
2020/06/22(月) 10:43:23.10
真面目に勉強しようとする初学者の足を引っ張っている
そんな奴らの対策のためとか本末転倒じゃないか
2020/06/22(月) 10:54:02.42
>>417
検索禁止とかにするんじゃない？もしあったら絶対つまんないから参加しないけど
2020/06/22(月) 10:55:27.10
>>424
「自分にとって学ぶことのないあまり考えずに解ける問題」だから人による
2020/06/22(月) 11:12:17.52
>>410
これ

>>423
これ
2020/06/22(月) 11:34:12.80
昨日のDくらいは同じ仕事するなら解けて欲しいと思ってしまうが理想高いんだろうか。
2020/06/22(月) 11:40:49.57
>>410
めっちゃ同意できる
せっかく大学受験数学の延長とか言われてるなら、誘導付き問題を出してみてほしいところある
2020/06/22(月) 12:21:35.36
典型アルゴリズムってどんなの？
クイックソートを自分で実装しろとかそういうの？
432仕様書無しさん
垢版 |
2020/06/22(月) 12:33:35.27
苦手なことじゃなくて得意なことに時間使ったほうがいいよ
2020/06/22(月) 12:50:29.15
10回とかで水色の人何
数倍やっても緑なんだが
2020/06/22(月) 13:00:03.37
水パフォ安定して出してれば10回もすれば水レートになる。って感じじゃろ
自力の違いだよ
2020/06/22(月) 13:04:12.42
10回で水は水上位安定たまに青perfくらいじゃないかな
数学かプログラミングに慣れててAtCoderの形式と噛み合ったら不思議じゃない ちな10回で青
2020/06/22(月) 13:16:55.02
Q#、A4までACした
むずかった
2020/06/22(月) 13:23:57.46
10回で青（現青）から10回で青（現赤）までいるからなあ
成長曲線は人それぞれ
2020/06/22(月) 13:38:51.56
成長がめっちゃ遅くても5年越しかで赤色になった人もおるんやで、名前忘れたけど
2020/06/22(月) 13:52:01.73
>>433だけどコンテストとその復習くらいでしか解いてないからかな？
もっと解けば上がる？
2020/06/22(月) 14:13:41.15
>>439
そりゃ人それぞれだろう。誰かがそれで上がったとして、他の人も同じように上がるだなんて誰にも断言できない。
2020/06/22(月) 14:23:58.05
短期間ですぐにあがってるやつも滅茶苦茶精進してたりするかるな。
過去問がこんだけあるんだしどんどんやると良いかと。
もしくはレッドコーダーおすすめ問題を解くとか
2020/06/22(月) 14:57:06.73
多分虚無梅も、タイムアタックするなら意味あるんじゃないの？
パフォーマンスカンスト勢はだいたいA問題B問題を20秒くらいで解いてるし
2020/06/22(月) 15:22:30.42
20秒くらいでA問題しょりしてる人ほとんど居なくね
2020/06/22(月) 15:33:43.61
20秒で解く方法ってリスクデカいからratedでやってる人はいないんじゃない
2020/06/22(月) 16:04:20.81
20秒で解くとか、問題を予想してあらかじめコード作っておかないと無理じゃない？　
幽遊白書のポロロッカか。
2020/06/22(月) 16:11:35.81
前回のABCなら20秒以内に2AC、30秒以内に7ACされてる
そのうちratedはそれぞれ半分くらい(1人,3人)
案外ratedでも早解きしてる人がいるもんだな
2020/06/22(月) 16:14:16.91
低難易度早解きできるようになるとある程度パフォーマンスが安定するとは思う
さすがに20秒台はレアだし高難易度も解かないと急上昇はしないけど、練習としての意味はある
2020/06/22(月) 16:16:58.59
入出力をパターン化して慣れれば、目的の解法の実装に集中できるというもの
2020/06/22(月) 16:28:01.62
>>438
誰？
そういう人こそ称えて目標にすべきだろ
2020/06/22(月) 16:32:40.41
A20秒まではいらないと思うけど1分くらいでは解けるようにすべきだとは思う
2020/06/22(月) 16:44:44.86
>>449
チョクダイかけんちょんがたたえてた記憶
ワイも名前忘れちゃった
2020/06/22(月) 16:46:16.39
>>438
kyuridenamidaさんでしょ
https://www.topcoder.com/members/kyuridenamida/details/?track=DATA_SCIENCE&;subTrack=SRM
■ このスレッドは過去ログ倉庫に格納されています
5ちゃんねるの広告が気に入らない場合は、こちらをクリックしてください。
ニューススポーツなんでも実況