競技プログラミングにハマるプログラマのスレ 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/19(金) 17:34:34.56
数学の論文とかほとんど文章なんだけど
2020/06/19(金) 17:36:26.34
>>302はなかなかだと思う
競プロ力が異様に高い某ベンチャーのtech blogとか読むとみんな文章がうまくて、ああいうのは見当たらない
2020/06/19(金) 17:41:11.82
競プロの話しよう
2020/06/19(金) 18:05:26.88
>>319
そういう奴って、自分を大きく見せたいという(隠しているつもりの)意図は簡潔に正しく伝えられているなw
324仕様書無しさん
垢版 |
2020/06/19(金) 18:07:14.63
言うほどむずい単語なんて使ってるか？(´・ω・`)
2020/06/19(金) 18:18:10.77
匿名かつ書き捨ての、意味はちゃんとわかる文
と
会社の名前で公開してるテックブログ
を大真面目に比べて前者を批判してるわけね

ん〜〜〜これは「ガチ」ですね。。。
2020/06/19(金) 18:28:28.67
>>321
指示語の使い方が微妙では？
渦中のレスをガッツリ指差してるわけだから「ああいうの」じゃなくて「こういうの」の方が適切じゃない
2020/06/19(金) 18:37:34.28
やべー奴
2020/06/19(金) 18:43:02.93
明日のAGCのwriterはやっぱりmaroonrkなんか？
寒色虐殺回が意外と楽しいので期待
2020/06/19(金) 18:52:54.94
黄でも上級が一番多いのか
2020/06/19(金) 19:10:14.50
満点の割合が知りてえ
2020/06/19(金) 19:12:43.39
粗を見つけてはマウント取りたがるやつの多いこと
2020/06/19(金) 22:50:01.49
黄上級と申します…
2020/06/19(金) 23:47:42.89
お前らってyukicoderのコンテストにも出たりすんの？
2020/06/19(金) 23:48:23.93
出てるよ
2020/06/20(土) 00:42:02.20
当然だな
2020/06/20(土) 01:58:27.87
それはできない
337仕様書無しさん
垢版 |
2020/06/20(土) 10:44:55.62
writerって何のために公開してるんだろ
2020/06/20(土) 11:04:07.01
writer側からしたら公開してほしいだろうし、他全員に隠すことが無理な以上全体に公開した方が公平そう
2020/06/20(土) 11:48:57.32
AtCoder用のユーザースクリプトの宣伝します！
テストをボタン1つで実行できるようになります！
https://qiita.com/flyingMaguro/items/18a2212106e5de07a7fa
https://greasyfork.org/ja/scripts/405702-easy-test-atcoder
2020/06/20(土) 12:51:16.42
すごい
サイト上で書いてた頃なら使ったかも
2020/06/20(土) 14:01:01.43
初心者ほど需要ありそうだけどuserscript使うような層には需要減りそう
342仕様書無しさん
垢版 |
2020/06/20(土) 14:24:54.98
ojで間に合ってるけど手軽に使えていいかもね
2020/06/20(土) 15:57:21.04
本人かは知らんけど5chで宣伝されるとなんか仕込まれてるんじゃないかと勘繰ってしまう
344仕様書無しさん
垢版 |
2020/06/20(土) 18:02:39.93
DEGwer単独回、意外と珍しいね
数学問を期待している
2020/06/20(土) 18:38:32.05
003,009,015,021,024,039,046(今回)って感じかな
C解きたいなー
2020/06/20(土) 19:26:36.89
「競プロは数オリなんだ」の人じゃん
今日もnosub
347仕様書無しさん
垢版 |
2020/06/20(土) 20:54:23.35
でぐわの問題は難しくていつも解けない
2020/06/20(土) 20:56:40.95
数学問は好き好き大好き
2020/06/20(土) 22:52:07.22
>>343
いろんな情報収集ができるよね
2020/06/20(土) 23:30:33.65
nosubのはずがレート上がった
本当にありがとう
2020/06/20(土) 23:48:33.83
C解けたけどみんな通しすぎだろ
(4乗に定数倍改善かけただけだから人のこと言えないけど)
2020/06/21(日) 00:11:41.99
明日のABCはまた炎上しそうなライターだ
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すれば黄色なれるよ
■ このスレッドは過去ログ倉庫に格納されています
5ちゃんねるの広告が気に入らない場合は、こちらをクリックしてください。
ニューススポーツなんでも実況