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

■ このスレッドは過去ログ倉庫に格納されています
2021/11/20(土) 02:43:43.44
競技プログラミング、オンラインジャッジ、プログラミングコンテストやCTFに関する雑談スレ
次スレは>>950

AtCoder https://atcoder.jp/
yukicoder https://yukicoder.me/
Codeforces https://codeforces.com/
CodeChef https://codechef.com/
Project Euler https://projecteuler.net/
CLIST https://clist.by/
AtCoder Problems https://kenkoooo.com/atcoder/
AtCoder Clans https://kato-hiro.github.io/AtCoderClans/

前スレ
競技プログラミングにハマるプログラマのスレ 74
https://medaka.5ch.net/test/read.cgi/prog/1636865136/
2021/11/23(火) 00:50:21.92
CF上位陣のコード見てると案外行儀の良い人もいるんだな
2021/11/23(火) 01:00:55.11
グローバル変数じゃなくて、全部引数渡しにしたところで、書く手間は10秒もかからんだろ

まあおれは短く書ける方法を選ぶけど
2021/11/23(火) 01:04:23.22
わざわざ上に行かなくてよくてお行儀もセーフなラムダ再帰を使おう
2021/11/23(火) 01:05:19.54
グローバル変数じゃなくてもせめてクロージャー使えばいいんだけど、Rustのクロージャーって競プロ的にはかなり不便だよね
2021/11/23(火) 01:15:37.03
>>460
もう少し詳しく言うと、constでないグローバル変数はunsafe扱いで、
扱い方によっては未定義動作が出ちゃう
未定義動作は早々出ないとは思うけどunsafeで囲むだけでも手間
466仕様書無しさん
垢版 |
2021/11/23(火) 01:17:23.45
純粋培養の僕にはちんぷんかんぷん
2021/11/23(火) 01:19:26.16
C++の不便な点を指摘するひとって全然いないけど、やっぱり競プロはC++が圧倒的最強なのかね
2021/11/23(火) 01:24:06.29
ポインタ使う必要ないからな
2021/11/23(火) 01:33:59.40
いやC++なんてボロクソに言われまくってるだろ…
むしろ賞賛してる人がいないレベル
2021/11/23(火) 01:34:59.20
お、そうなんだ。競プロだとC++はどのへんが不便なの？
2021/11/23(火) 01:35:43.87
C++が不便なのって競プロでは関係ない所ばっかだからな
2021/11/23(火) 01:42:22.45
冷静に考えると標準では配列の出力が出来なくてcoutに渡そうもんならクソ長エラーが出てくるの草だろ
2021/11/23(火) 01:45:53.62
std::get<0>(hoge)は酷い
rustならhoge.0やぞ？
2021/11/23(火) 01:51:48.96
rustは安全性重視なのは確かに競プロ向いてない感じもするけど、
色々モダンな言語機能も入っててC++より書きやすいところも多いし、
それでいてC++同等の速度なのは嬉しい
2021/11/23(火) 01:57:08.71
こういう時語られるC++って古いイメージのままな気がしてもにょるわ
C++20とか結構簡潔な記述できるようになってるで
2021/11/23(火) 01:57:21.56
C++もいろんな機能が増えてきてるけど、テンプレートで無理やり後付してる感すさまじいよね
477仕様書無しさん
垢版 |
2021/11/23(火) 01:59:42.19
あとtupleに関して言えば多分比較的最近主流になってきたfunction return typeとかを(bool,f64)とかみたいにかけないのもちょい不便よね
かと言ってinclude pairとかtupleとかしてまで書こうとは思わんが(´・ω・｀)
2021/11/23(火) 02:02:20.16
よく知らんけど index_tuple イディオムみたいなやつで hoge[i] できるようになったりしない？
2021/11/23(火) 02:15:05.52
boost::fusionを使おう
480仕様書無しさん
垢版 |
2021/11/23(火) 10:35:06.33
>>450
それなりの高校行ってれば指定校あるだろ
2021/11/23(火) 10:37:56.21
指定校推薦とか主席他数名みたいなレベルだけで
まず通らんだろと思ってたけど
最近は枠多いの？
2021/11/23(火) 10:41:33.99
それなりの高校というやつのレベルに寄りそう
自分の出身である地方の進学校だと地元の国立医学部に推薦でフツーの成績の人を大量に送り込むみたいなことやってたし都内の学校なら似たようなことしてるとこあるんでないか
2021/11/23(火) 10:59:15.93
流石にマーチはノー勉だわ
484仕様書無しさん
垢版 |
2021/11/23(火) 12:20:22.79
>>481
首席がマーチの指定校って結構馬鹿そう
2021/11/23(火) 12:25:50.70
マーチの扱い方でスレの学歴が大体分かるな
2021/11/23(火) 12:28:52.15
マーチに行った知り合いなんていないのでよくわからん
2021/11/23(火) 12:29:05.56
学歴ネタは5ch補正を忘れるなよ
2021/11/23(火) 12:30:12.44
競プロスレでは本当に落ちこぼれだからな
2021/11/23(火) 12:32:27.67
マーチに行ってないお友達もいないのでは…？
2021/11/23(火) 12:33:36.38
そうそう友達なんていないよね
2021/11/23(火) 12:55:06.92
別に東大だってノー勉だろ
2021/11/23(火) 13:20:50.75
デジタルハリウッド大学とか日大危機管理学部の判定で争ってたやつならノー勉だろうな
2021/11/23(火) 13:32:51.39
グローバル変数はMainクラス作ればメンバ変数に出来る
494仕様書無しさん
垢版 |
2021/11/23(火) 14:15:47.44
>>493
rustの話し？クラスなんてあったっけ？
2021/11/23(火) 14:45:26.38
みんな冊子掲載常連じゃないの？
まさか理一合格者平均点付近で東大合格みたいな雑魚がこのスレに居座ってるのか？
496仕様書無しさん
垢版 |
2021/11/23(火) 14:47:37.75
いつまで大学受験の栄光に縋ってるんだ？
497仕様書無しさん
垢版 |
2021/11/23(火) 14:58:34.46
懐かしすぎてワロタ
2021/11/23(火) 15:06:28.92
>>494
C++の話だけどRustでもMain構造体作って全部その構造体のメソッドで処理すれば、グローバル変数は構造体のフィールドに出来るよ
2021/11/23(火) 15:27:47.99
使う変数に毎回selfつけるくらいなら引数もりもりのがええわ
2021/11/23(火) 15:41:50.54
>>499
関数の外のスコープの変数を参照しようとするとき、
エディタが自動的に関数の仮引数に変換してくれたらいいのにい、っていつも思ってる
2021/11/23(火) 16:24:28.03
>>499
それはそう(´・ω・｀)
2021/11/23(火) 17:27:26.28
なんで競プロにしてくれないの
https://www.itmedia.co.jp/news/articles/2111/22/news128.html
2021/11/23(火) 17:48:00.22
競プロで培ったアルゴリズムや数理最適化の技能で殴り込めばいいじゃん
タスクの種類的にみじめにぼろ負けするだろうけど
2021/11/23(火) 17:56:24.95
みじぼろは嫌だなあ
505仕様書無しさん
垢版 |
2021/11/23(火) 18:52:35.75
>>498
しなくていいよねw
2021/11/23(火) 18:55:37.21
さんちゅっ
2021/11/23(火) 18:56:57.45
>>498
snukeさんこれで書いてるよね
2021/11/23(火) 19:36:30.45
たしかに
2021/11/23(火) 19:53:18.07
callableな構造体すき
2021/11/24(水) 00:30:18.02
★★★★★
会話をすればポイントが増えてアイテムを買える。
次世代の大型掲示板、メルプラネット。
https://merpla.net/boards/
2021/11/24(水) 06:04:02.14
ガイジスレ終了
2021/11/24(水) 10:03:52.19
オフ会事変からしばらくたったがコロナ増えそうにないな
このまま波乱なしなのかね
2021/11/24(水) 11:23:31.48
日本だけこのまま感染者数が少ないまま推移していくのだろうか
514仕様書無しさん
垢版 |
2021/11/24(水) 12:17:59.09
入国者次第
2021/11/24(水) 12:21:53.17
どうせ感染者増えねえから、もっとGoToとかしようぜ
2021/11/24(水) 12:23:04.79
ワクチンパスポート必須なら
2021/11/24(水) 15:03:09.83
結局またスレ長の勝ちか
2021/11/24(水) 15:33:01.96
藤井聡太よりも勝ち続けてる気がする
2021/11/24(水) 18:21:49.67
次期スレ長候補がホームページ作成配信しとる
2021/11/24(水) 18:38:43.41
ゴリラに関してはもうこれ初代永世スレ長でしょ
2021/11/24(水) 18:41:28.20
いもすさんでも倒せないスレ長をRuteくんごときが倒せるとは思えない
2021/11/24(水) 18:42:25.14
メニューから保存してる人初めて見た
523仕様書無しさん
垢版 |
2021/11/24(水) 18:55:51.14
Ruteくんすこ
524仕様書無しさん
垢版 |
2021/11/24(水) 18:57:27.59
>>519
どこ？
2021/11/24(水) 19:06:57.30
>>521
別に倒す必要はない
岸田だって菅を倒したわけではないし菅だって安倍を倒したわけではない
2021/11/24(水) 19:23:05.24
ああん？ おめーどこスレの出身よ？ うちのスレ長なめてんのか？ やるか？ オラァ！
527仕様書無しさん
垢版 |
2021/11/24(水) 19:39:12.35
キモ
2021/11/24(水) 21:09:08.38
餃子とかオレンジアメが好きらしいよ
2021/11/24(水) 21:16:47.55
Ruteくんは作文作法の本を読んでくれ
530仕様書無しさん
垢版 |
2021/11/24(水) 21:55:53.42
悪い意味でハマってる
茶色だが解説を見て証明に納得してもそれがどこから思い付いたのかわからん
だが解けた時の楽しさが忘れられずjobsの求人も魅力的だからやめられねえ
531仕様書無しさん
垢版 |
2021/11/24(水) 22:01:31.31
解説から攻略に繋げるコツとかある？
2021/11/24(水) 22:02:52.36
どの問題か言ってみ
533仕様書無しさん
垢版 |
2021/11/24(水) 22:03:19.74
一から発想しようとするのが間違っていて、そういう解き方の典型があるって引き出しを自分の中に一つ増やせばそれでいいんじゃないの
増えた引き出しから必要なものをすぐ引けるようになるには問題数こなして感覚を身につけるしかないと思うけど
2021/11/24(水) 22:11:55.79
ABCの特に青diff以下の問題は全て典型問題です
ここ1年のABCの青diff以下でアドホックな問題ありません
もしあったら指摘ヨロ
535仕様書無しさん
垢版 |
2021/11/24(水) 22:28:01.26
なんか分かったすまん
536仕様書無しさん
垢版 |
2021/11/24(水) 22:28:53.37
ちなみにDPコンのF
2021/11/24(水) 22:30:01.96
A問題が全くわからなかったけどRuteくんの神解説のおかげでスッキリしました
538仕様書無しさん
垢版 |
2021/11/24(水) 22:33:20.65
s[i]==t[j]ならdp[i][j]==dp[i-1][j-1]ってのはすんなりそれはそうだろって分かったんよ
だけどs[i]!=t[j]のときにdp[i][j]==max(dp[i-1][j],dp[i][j-1])っていうのが分からんかった
それの妥当性は分かるし、答えを見れば証明はできるが、どうやって問題からそこに辿り着くのか？っていう話
539仕様書無しさん
垢版 |
2021/11/24(水) 22:41:30.52
ちなみに考え方は
とりあえず答えに影響する部分列だけ分かりやすくABCみたいに書いて可視化したもので示すと
(X)とか(Y)はXが含まれてるかもしれないorYが含まれてるかもしれないっていう意味ね
S=...A...B...C..(Y)..X
T=.A....B..C...(X).....Y
みたいに考えればX!=Y(S[i]!=T[i])のときにdp[i][j]がdp[i-1][j]かdp[i][j-1]であることが直感的に分かるって感じ
540仕様書無しさん
垢版 |
2021/11/24(水) 22:52:02.59
(S[i]!=T[j])だったわ
2021/11/24(水) 23:04:02.71
DPって全探索の効率化だから、元となる全探索アルゴリズムから考えればそうなるよ
542仕様書無しさん
垢版 |
2021/11/24(水) 23:33:29.08
>>541
この問題って元々の愚直全探索からたどってもこの考え方になるのか
しばらく考えてみたけど分からんかった
2021/11/24(水) 23:34:25.31
Ruteくん、報告があるってなんだろ
2021/11/24(水) 23:35:03.62
DPコンのAから解いてるんなら、遷移（探索）だということはわかってると思うんだが、わかってないのか？

二次元配列の中身がどうなるのか書き出して、遷移と照らし合わせてみろ
面倒だけど、最初はそういう泥臭い作業をしないと理解が進まない
545仕様書無しさん
垢版 |
2021/11/24(水) 23:42:07.87
codechef何があった？
2021/11/24(水) 23:43:41.46
ドメイン購入コンテストか
547仕様書無しさん
垢版 |
2021/11/24(水) 23:52:33.22
仕組みがわからないと発想の出所がわからない、は違うだろ
2021/11/24(水) 23:58:30.70
そういうことか
2021/11/25(木) 00:01:02.74
忘年会47歳さんも参戦か
彼がスレ長派につくかどうか見極める必要があるな
2021/11/25(木) 00:06:32.77
R君、競プロの色なんて社会に出たらよくも悪くも誰も気にしないけど、文章力の問題はずっとついて回るから、そっちの方を精進してほしい
2021/11/25(木) 00:15:35.35
発想の出所に関して言えば、ある状態の情報を計算するために近い状態の情報を使うというDPの典型思考そのまんま
DP[i][j]を計算するときに、DP[i-1][j]やDP[i][j-1]などの近場の情報を使ってどうにかしようって考えじゃね
そんな突飛な発想じゃないと思うぞ
2021/11/25(木) 00:29:50.44
忘年会すげー
無料観戦権とかないのか？
553仕様書無しさん
垢版 |
2021/11/25(木) 00:34:49.81
1時間待機したのに延期になってワロタ
2021/11/25(木) 00:36:00.69
理系ならそのうち勝手に文章力はつくんとちゃうか？文系と違って
2021/11/25(木) 00:36:49.09
マルコフ連鎖的とかそういう発想だろうね。
なんかそこまで情報持たなくてよくね？ってな感じだとは思う。
2021/11/25(木) 01:13:13.47
延期って何の話？
557仕様書無しさん
垢版 |
2021/11/25(木) 01:16:52.34
典型っぽいやつは決め打ちで解いてみるってことか
でも最初に斜めを使うのが思い浮かぶDPで縦横を決め打ちで試すの怖いし難しいな
2021/11/25(木) 01:21:49.39
決め打ちなんてしないよ
全く同じ問題なんて出題されないし、そんな考察スキップするようなことしてたらバグだらけになって通らないよ
2021/11/25(木) 01:23:52.24
これは二分探索っぽいな、って解法をある程度決め打ちして、考察を深めていくことならある
560仕様書無しさん
垢版 |
2021/11/25(木) 01:28:32.65
これはDPコンだから最初からDPって分かるけど、これとコンテストで未知のときに遭遇したらDPで行くっていう行為自体がすでに決め打ちだし、その上に決め打ちを重ねるのが怖い
でも証明自体は手際よくやれば3分で済むから袋小路でグルグルするくらいならやったほうが良いな
■ このスレッドは過去ログ倉庫に格納されています
5ちゃんねるの広告が気に入らない場合は、こちらをクリックしてください。
ニューススポーツなんでも実況