X

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

0015デフォルトの名無しさん
垢版 |
2023/10/04(水) 13:20:25.89ID:nwK1CNVl
このまま5ch潰れてもいいから一緒にXも閉鎖してくれ
これでネットも平和になるしみんなの幸福度も上がるだろ
0022デフォルトの名無しさん
垢版 |
2023/10/04(水) 20:08:24.22ID:xZAW7T/f
>>20
気合い入れて集中しないと出来ないことだけはわかった
アカウント公開している？みたい。
0024デフォルトの名無しさん
垢版 |
2023/10/04(水) 21:14:59.58ID:nwK1CNVl
>>22
評価は緑でカンストって言ってるのは別のスレで荒らしてた緑で停滞してるやつの工作だから騙されないようにね
0025デフォルトの名無しさん
垢版 |
2023/10/04(水) 21:19:11.80ID:Qkzf+M66
どうせID有りにするんだったらワッチョイとかも付けようぜ
あっちのスレみたいに緑agerが自演連投してもNG出来るようになるし
0026デフォルトの名無しさん
垢版 |
2023/10/05(木) 05:09:33.61ID:HizYIKXy
>>14を見てみたけど蟻本を読むための前段階の本があるんだな

ABC過去問やってみた感じAは確実Bも大体とけるcは半々ぐらいDは一度も解けたこと無い
俺の適正ランクは茶色あたりです？
0029デフォルトの名無しさん
垢版 |
2023/10/06(金) 07:03:08.70ID:BgvqARb2
vtuberのきりみんちゃん4年もかけて緑コーダーになったのか
一度灰色まで落ちても続けられる精神力がすごいわ
0030デフォルトの名無しさん
垢版 |
2023/10/06(金) 16:51:25.24ID:jg1c5xSH
[クライシスアクター」「豊島保養所」←画像検索＆拡散！

他スレに丸ごとコピペよろしっく！！！
ネットでできる反ﾚﾌﾟﾃｨﾘｱﾝ・反ｲﾙﾐ活動です！！！！！
動画サイトのコメ欄もねらい目だぞ！！！！！！！
0031デフォルトの名無しさん
垢版 |
2023/10/06(金) 20:23:53.79ID:BgvqARb2
atcoder過去問といてると本番中に一度ACしたコードを再度提出してる人(速度とかが速くなってる)がいるんだが
速度やメモリ消費量とかもパフォーマンスに影響するの？
0032デフォルトの名無しさん
垢版 |
2023/10/07(土) 20:49:58.50ID:mbXWdBfT
もうすぐ始まるよー
彼はノートパソコンが手に入ってから始めるのかな
始めたばかりだからまずは茶色を目指すぜ
0033デフォルトの名無しさん
垢版 |
2023/10/08(日) 08:23:54.42ID:r0wb7MqW
ノートパソコンは手に入れたのだけど環境設定するのに
gccとMingwとCygwinの関係がよくわからず調べ中
基本のgccで行きたいのだけど。
0034デフォルトの名無しさん
垢版 |
2023/10/08(日) 08:24:18.34ID:r0wb7MqW
ノートパソコンは手に入れたのだけど環境設定するのに
gccとMingwとCygwinの関係がよくわからず調べ中
基本のgccで行きたいのだけど。
0035デフォルトの名無しさん
垢版 |
2023/10/08(日) 09:18:11.73ID:sATj6jAg
windowsはよくわからないけどcygwinは今もメンテされてるらしいからcygwinにgccを入れればいいんじゃね
visual studioを入れるって手もあるけど
atcoderがgcc使ってるからgccのほうがいいだろうね
0036デフォルトの名無しさん
垢版 |
2023/10/08(日) 09:35:38.64ID:CrdCteTP
>>33-34
初心者さんなら
Code::Blocks の mingw 版がお薦め
tdm-gcc も良い
0038デフォルトの名無しさん
垢版 |
2023/10/08(日) 10:41:52.91ID:r0wb7MqW
>>35-37
ありがとう　レスが助かります
VSはマシンの性能上厳しいかと思うし
できるだけ基本で行きたいので
Cygwin入れました
選択はgcc-core 11.4.01 gcc-g++ 11.4.0-1 gdb 12.1-1
バージョンはこんなもんかなという選択です
0039デフォルトの名無しさん
垢版 |
2023/10/08(日) 10:51:13.47ID:r0wb7MqW
黒い画面にHelloWorld出たので良し！
これが出るだけでもうれしいものです
0040デフォルトの名無しさん
垢版 |
2023/10/08(日) 11:04:18.90ID:sATj6jAg
おめっと
atcoderのほうのバージョンはすごい新しいよ
gccは12.2だよ
来週から参加するの？
0041デフォルトの名無しさん
垢版 |
2023/10/09(月) 06:43:24.09ID:5XBl3KCR
APG4bを通してから参加しようとおもっているだけど。
0044デフォルトの名無しさん
垢版 |
2023/10/10(火) 08:18:33.44ID:BDsbHemP
sakuraエディタ使ってるんだけど
競技プログラミングやってるなら
emacsとか使う方がかっこいいよねw
そこで選ぶか
0045デフォルトの名無しさん
垢版 |
2023/10/10(火) 08:34:01.65ID:BDsbHemP
入れた
Emacs 28.2
慣れるまで時間かかりそう
0046デフォルトの名無しさん
垢版 |
2023/10/11(水) 01:47:14.08ID:EqvtTLCX
カッコよさで選ぶのは間違っていると思うが
emacsは慣れると使いやすいよ
自分好みにカスタマイズしていかないと普通のエディタだよ
俺はライブラリをコマンドとして登録しているよ
0047デフォルトの名無しさん
垢版 |
2023/10/11(水) 07:16:58.55ID:C2s5FYzv
かっこいいかと思ったらそうでもなかった
ジャラジャラいろいろ付いてて頑固だった
ツールバーを非表示にしたのに再度開くと非表示になりません
設定ファイルに設定しなきゃ言うこと聞きませんって感じでしょ？
0048デフォルトの名無しさん
垢版 |
2023/10/11(水) 08:00:25.09ID:EqvtTLCX
一番お気に入りの機能は2画面に分割して片方でインタプリタを起動して
書いたソースを送り込んで即実行！ってやるやつ
でもこれはvimでも出来るようになったらしい
後はC++ならCtrl+x Ctrl+p Ctrl+iで画面全体を適切にインデントしてくれる機能とかかな
0049デフォルトの名無しさん
垢版 |
2023/10/11(水) 08:33:40.69ID:+hn9Nc+C
>>48
それどうやるの？
0050デフォルトの名無しさん
垢版 |
2023/10/11(水) 09:47:04.86ID:1pnnvG+R
emacsのmodeにそういう機能が含まれているよ
inferiorモードとかいうのがreplが動くほうの画面
まず自分の言語のemacsのモードについて調べてみては
そういうモードを起動したら自動的に2画面になるけど
Ctrl+x 1(1画面) ctrl+x 2(上下画面) ctrl+x 3(左右画面)は覚えていて損はない
0051デフォルトの名無しさん
垢版 |
2023/10/12(木) 06:50:09.24ID:gAp1qlED
毎回必ず入力するincludeなどのボイラープレートコードをABCDの問題分だけコピーするシェルスクリプトを書いた
E以降は多分手に負えないからスルーだ
ちょっとずつ環境整備していくぜ
0052デフォルトの名無しさん
垢版 |
2023/10/14(土) 06:32:39.94ID:uAEsZXMS
APG4bは進んでるかな
今日も21:00からある
俺ははじめてやったとき参加登録をしてなくて
アンケートに答える分だけ時間を損したぞ
0053デフォルトの名無しさん
垢版 |
2023/10/14(土) 07:39:46.17ID:tWs5FVR1
APG4bを第一章だけ読んでいざ実践とBeginnersSelecitionを開いていみたら
これは難儀だぞとビビッてしまいました
問題の意味を理解するのさえ出来かねる
もしかしたらワイが到達できるレベルってBeginnersSelectionまでじゃなかろうか
とても色を求めるのは無理じゃなかろうか
と委縮している現状です
0054デフォルトの名無しさん
垢版 |
2023/10/14(土) 08:12:15.06ID:uAEsZXMS
そうなのけ
Beginners Selectionちょっとだけ見てみたけどC問題までのってるのね
C問題はBeginner用ではないと個人的には思う
Aはほぼ解ける、Bは時間をかけたら解けるぐらいであってほしいところかなあ
Cは練習していったら解けるようになるかも
茶色になるにはCが解けるか、A,Bを早解きできるかって感じだと思う
0055デフォルトの名無しさん
垢版 |
2023/10/14(土) 09:27:22.57ID:uAEsZXMS
一応目安があるみたい
https://qiita.com/masakinihirota/items/d1ffac54e70a1adf084c
によると
100点問題は100点以上を10問練習すればだいたい安定する
200点問題は200点以上を20問練習すればだいたい安定する
300点問題は300点以上を40問練習すればだいたい安定する
400点問題は400点以上を80問くらい練習すればー
あくまでも数学をやってきた人たちが対象であり、文系であったり数学の土台がゆるかったりすると、この3−5倍の努力が必要です
0058デフォルトの名無しさん
垢版 |
2023/10/14(土) 20:52:19.40ID:uAEsZXMS
はじまる・・
>>53はビビって諦める感じだろうか
参加登録の後にレーティングには反映されない形での参加も選べるよ
ここは人がほとんどいないから俺と彼と広告しかおらんような
マ板のスレは俺ら雑魚には人権がないかのようだ
0060デフォルトの名無しさん
垢版 |
2023/10/15(日) 06:45:02.09ID:S4b3SqiG
>>58
諦めてないよ
ただまず実際にC++で簡単なコードを書けないとダメじゃないかと思ってる
その課題としてスレ読みをC++でやりたいと考えてる
それからアルゴリズムに挑戦するべきかなと。
目標は来年４月までに茶色をクリア
0061デフォルトの名無しさん
垢版 |
2023/10/15(日) 07:05:35.63ID:p9CLqDEe
諦めて無かったか
スレ読みって何？
簡単なコードなら過去問のA問題をやるといいのでは？
俺は解説コードを読みたいがためにC++20とかpython3とかもアドホックに勉強してる
教材は解説コード
0062デフォルトの名無しさん
垢版 |
2023/10/16(月) 06:40:59.56ID:gLYo6B+i
素直にそうするわ
エディタもお勧めの多いVSCODEでじっくり進める
それさえまだ出来ていないのだから横道それちゃいけないね
スレ読みとかはその後に示せたらと。
0063デフォルトの名無しさん
垢版 |
2023/10/16(月) 08:03:35.72ID:4YNW+NBz
やっぱりワイは素直じゃないな
素直ならVSCode使わずにAtCoderのオンラインエディタでやってるよな
0065デフォルトの名無しさん
垢版 |
2023/10/16(月) 21:03:50.63ID:+BkDA/Xt
マ版スレのほうがレベル高いよね
帰ってもインコだのなんだのいわれるだけ
ここは初心者の隔離所みたいなものだから

>>63 環境設定はまぁぼちぼちやってくれ
入出力に慣れるためにA問題やるのはいいと思うけど
10問程度やったらもっと難しい問題もやっていかないと上達しないよ
0066デフォルトの名無しさん
垢版 |
2023/10/17(火) 23:40:35.40ID:D8GqI7aV
馬鹿ドカタは開発料金の泥棒組織を支援するな↓

馬鹿だから詐欺被告者より反社会で低知能な奴隷になってくれます。
非婚だから低価格で高稼働の多重派遣奴隷をご用意しております。

レバテック 代表取締役 岩槻 知秀 いわつき ともひで

1980年生まれ。大阪府出身。早稲田大学社会科学部入学後、大学1年時からIT企業にてビジネス経験を積む。
携帯コンテンツ開発会社における2年半のインターン経験後、オープン系システム開発会社の立ち上げに加わり、マネージャーとして活躍。
大学卒業後、レバレジーズ株式会社を設立。
設立5年で売上高20億円を突破。雑誌「ベンチャー通信」のベストベンチャー100に選ばれた実績を誇る。

https://i.imgur.com/SaXuOmM.jpg
https://i.imgur.com/BQdJFGg.jpg
0067デフォルトの名無しさん
垢版 |
2023/10/18(水) 18:49:46.88ID:vCrdR6l9
演習は進んでいるか？
最初は新しい入出力法が出る度に慌てていたな

過去問D問題解けたと思ったら灰diffだった
そんなに甘くはないD問題
0068デフォルトの名無しさん
垢版 |
2023/10/20(金) 07:26:25.97ID:KPMH7UZf
>>67
進んでいません
先入れ後出しといいますか
スタックを積んでいるといいますか
有言不実を恥じ入ります
0069デフォルトの名無しさん
垢版 |
2023/10/20(金) 19:31:11.54ID:1GCawA7K
なんか別のことやってるんかな
まあそこは個人の自由だし
俺はアルゴリズムの夢を見るぐらい過去問に取り組んでるよ
でも演習量が足りないのかなかなか上達しない
0070デフォルトの名無しさん
垢版 |
2023/10/21(土) 06:44:16.25ID:NxESm74G
今日もコンテストあるけどキングオブコントも観たい
参加するか迷う
過去問解いてて参加回数が一緒の人を発見。こっそりライバル視
0073デフォルトの名無しさん
垢版 |
2023/10/22(日) 12:57:32.38ID:viqLu2bC
それはあなたのレベルが高いだけではなくて？
俺は緑コーダーからすごい人って認識
それにム板の競プロ総合スレ誰もいないじゃん
ム版はレベルが高いかというより人がいない
0074デフォルトの名無しさん
垢版 |
2023/10/22(日) 20:10:01.59ID:kVgbEUo7
>>69
実はその別のことというのがサーバーを借りるってことでした
C++が動くレンサバがあるというのを知っていろいろ調べたり悩んでいました
これから古本屋で手に入れた蟻本を最初の部分だけでも読んでみようとしています
実践あるのみなのに本に頼ろうとしているのが駄目だなぁと思いながらですがw
0075デフォルトの名無しさん
垢版 |
2023/10/22(日) 21:42:15.36ID:viqLu2bC
>>74
蟻本は難しい部類に入るみたいだから気をつけて。俺もまだ序盤しか読んでないけどdpのページは何度も読み返してる
なんか筋が悪いというか、atcoderのオンラインエディタがどうのってのは実行環境がまだなかったからそういう話をしてたのね
WindowsならVisual Studio Community editionとかを入れればC++の実行環境は整うよ
それですら初心者には少し敷居が高いけどcygwinとかmingwとかでgccを使うほどじゃない
0076デフォルトの名無しさん
垢版 |
2023/10/22(日) 23:16:23.03ID:R7UyRloS
蟻本はマジで難しい方だぞ、オンサイトで黄橙らへんに聞いても全部理解してる人は皆無だったし
7割理解した辺りで黄色になれるレベルの難易度なので、競プロ本の中でも別格
もちろん最初の方を読むだけでも力は相当付くが、先に挫折しないか心配になる
0077デフォルトの名無しさん
垢版 |
2023/10/23(月) 05:53:46.30ID:el5J+Utf
蟻本はバイブルとネットで見たから
てっきりAtCodeのバイブルかと思ったら全然ちがってた
当然問題中身は理解できないけど
でもパラパラめくってるだけでも自分にとって大事と思えることに気づけた
一番先に問題の最後の"求めよ"文を見るそしてしばらく制約を見て考える
それから問題文を最初から読む
しかしこれって競技プログラミングに限らず自分の"やりたい"というときにも同じではないか
0078デフォルトの名無しさん
垢版 |
2023/10/23(月) 06:40:46.65ID:8gpCEC0e
>>72
同意

マ板はポトペタでプログラムしてるようなのばっかり
ム板はディスクリートでフルスクラッチよ
0079デフォルトの名無しさん
垢版 |
2023/10/23(月) 06:45:56.48ID:8gpCEC0e
>>73
競プロなんて暇人のやること
0080デフォルトの名無しさん
垢版 |
2023/10/23(月) 06:53:11.54ID:BRnuIPFI
7割で黄色、そんなレベルの本だったのか
灰コーダーにはまだはやいかな？
他の本は知らないけどatcoderの過去問もいい教材なので
過去問A-D埋めをまずやる。それが終わったら典型90問をとく予定
今回のD問題は蟻本にのってた区間スケジューリング問題と同じアルゴリズム+tの圧縮が必要だった
後半をやったことがなかったので解けなかったけど
0081デフォルトの名無しさん
垢版 |
2023/10/23(月) 13:20:59.99ID:kClWNwaY
プログラミング・コンテスト・チャレンジブック、第2版、2012
表紙に蟻が描かれているので「蟻本」とも呼ばれる

ほとんど全てのアルゴリズムを網羅。
問題数も多く、パズル感覚で楽しめる。
AIやシミュレーションゲームの参考になる

言語は、g++用のC++。
初心者は、初級の問題しか解けないと思う。
初級では、動的計画法・ナップサックなど

中級ではネットワークフロー、上級ではグラフも出てくるから、
図を描いて、じっくり考えないと分からない。
何年か掛けて、勉強する本

TopCoder, Google Code Jam(GCJ), PKU OnlineJudge(POJ),
会津大学のAIZU ONLINE JUDGE(AOJ) などから、
3人の大学院生が、よくこれだけ良問を集めたなと感心した

セジウィックも読んだけど、
やっぱり蟻本・石畑清・川中真耶など、日本人の本の方がわかりやすい

R・セジウィックの20年前のアルゴリズムC++の本を見たら、
2分木の回転については、10行ほどしか載っていなかった。
蟻本にも、2分木の回転・平衡化は載っていない

オライリーの「入門 データ構造とアルゴリズム」には、
AVL木の回転について、図入りの説明が載っていた

でも赤黒木を詳細に説明した本は無い
Linuxのタスクディスパッチで使っているのに
008281
垢版 |
2023/10/23(月) 14:30:03.44ID:kClWNwaY
>>81
修正
>でも、red-black tree を詳細に説明した本は無い

川中真耶の「アルゴリズムを学ぼう」2013 という本で説明しているみたい
0083デフォルトの名無しさん
垢版 |
2023/10/23(月) 18:40:03.38ID:BRnuIPFI
red black treeは難しくて真面目に学んだことはないが
left leaning red black treeという性質をそのままに回転を半分にした
赤黒木より理解しやすい木があってそっちを覚える方がいいなって思ったことがある
llrb treeとかでググると出てくるぞ
0088デフォルトの名無しさん
垢版 |
2023/10/24(火) 04:47:22.79ID:olZYNVmh
レベルといっても
技術レベルとコミュニケーションレベルがあると思われ
0090デフォルトの名無しさん
垢版 |
2023/10/24(火) 20:59:22.67ID:hIZgfU8r
苦節9ヶ月、やっと水色になれた
これから
・ベルマンフォード法
・ワーシャルフロイド法
・最小全域木
・ゲーム問題
・LISなどの高度なDP
・最小共通祖先
・セグメント木
・ネットワークフロー
を学んで青を目指すぜ！
0091デフォルトの名無しさん
垢版 |
2023/10/24(火) 21:52:15.25ID:JWvpu44b
水色いいなー
目標が具体的だね
少し人が増えてきたのかなこのスレも
俺は今日はいもす法というのを勉強中
0092デフォルトの名無しさん
垢版 |
2023/10/24(火) 21:52:22.21ID:JWvpu44b
水色いいなー
目標が具体的だね
少し人が増えてきたのかなこのスレも
俺は今日はいもす法というのを勉強中
0093デフォルトの名無しさん
垢版 |
2023/10/25(水) 02:00:00.40ID:wSFtWsW2
水色になるまでに使った教材
・鹿本（難しめの演習問題が少し残っている）
・JOI本（全部解けた）
・典型90(★5の半分まで)とその類題（難しめの類題は積み残し）
・EDPC(Pまで、Jは除く)

これから使う教材
・PAST本ｴﾝﾄﾘｰ〜中級編　→　・PAST本上級〜ｴｷｽﾊﾟｰﾄ編
0094デフォルトの名無しさん
垢版 |
2023/10/25(水) 06:52:04.31ID:XCHj3SsF
調べてみたけど鹿本よさそう、今度買おう
調べてる途中で見つけたけど環境構築で
atcoder-cliとonline-judge-toolsというのがあったけどこれも入れた方がいいかもね
0095デフォルトの名無しさん
垢版 |
2023/10/25(水) 08:42:11.36ID:wSFtWsW2
C++で書かれてる初心者向けの本は、鹿本か鉄則本の二択だね
鹿本は教科書的で、鉄則本は高校数学でいうチャート式的
鹿本のほうが初歩レベルの問題や、考え方の部分のフォローが手厚い一方で、網羅度は少し低かった
鉄則本のほうはたくさんの典型を一通り網羅している一方で、一つ一つの項目に対するフォローは手薄い（例えば、掲載されている類題がそれぞれ1題ずつだけ、など）
なので目次や中身を見比べて決めるといいかも
もちろん両方買ってもいいんだけどね
0096デフォルトの名無しさん
垢版 |
2023/10/25(水) 18:40:58.52ID:XCHj3SsF
独学だと、公式/web解説と人のソースコードだけがたよりだから
解説がよくわからない場合ソースコード読み解けないと辛い
だから考え方の部分のフォローが手厚いのは魅力的
0097デフォルトの名無しさん
垢版 |
2023/10/26(木) 07:21:08.94ID:+j1jszqL
>>5は環境整備終わったか？
レンサバでC++やるってことはsshとかでログインしてからコードを書くつもりなんか
0098デフォルトの名無しさん
垢版 |
2023/10/26(木) 09:11:06.00ID:0lWmddKF
>>97
えらい遠い安価だなと思ったけど
まだ一か月は過ぎてなかったので安心w

正直なところVSCodeの設定を探求中なんです
jsonでいろいろな言語に対応できるってのが便利だし
追及する価値あるなと。
これってリアルの対面で教えてもらったらすぐなんだろうけど
調べながらやると時間かかる
しかたないけどね
0099デフォルトの名無しさん
垢版 |
2023/10/26(木) 09:12:56.62ID:0lWmddKF
C++でCGIはRubyとかPythonと同じようにFTPでいけるだろうと見込んでいる
0100デフォルトの名無しさん
垢版 |
2023/10/26(木) 18:52:47.55ID:r/HctLyn
凝り性なんだろう、なんだかヤクの毛刈り状態だな
早く参戦してくるのを待ってるよ
0101デフォルトの名無しさん
垢版 |
2023/10/27(金) 04:05:27.82ID:93zv19AS
>>98
VSCode の拡張機能のおすすめは、Code Runner で、
右クリックメニューから、選択したコード、またはファイル全体を実行する

この設定をチェックしておく
Code-runner: File Directory As Cwd
Whether to use the directory of the file to be executed as the working directory.

そうすると実行時にcd で、そのファイルがある場所へ、カレントディレクトリを移動してから、
例えばRuby なら、ruby "絶対パス/ファイル名.rb"
又は、ruby "絶対パス/tempCodeRunnerFile.rb"
で、そのファイルを実行する

tempCodeRunnerFile.rb は、Rubyのコード片をコピーした、一時的なファイル

設定項目、executorMap には、多くの言語の実行コマンドが書いてある。
"code-runner.executorMap": {

"javascript": "node",

"c": "cd $dir && gcc $fileName -o $fileNameWithoutExt && $dir$fileNameWithoutExt",
"cpp": "cd $dir && g++ $fileName -o $fileNameWithoutExt && $dir$fileNameWithoutExt",

"python": "python -u",
"ruby": "ruby",

あとは、VSCodeのスレで聞いて
0102デフォルトの名無しさん
垢版 |
2023/10/27(金) 19:17:31.93ID:IlYWK5hg
親切な人だな
俺はemacsだからVSCodeはわからない
それより明日もコンテストがあるぞ、環境整備だけで1ヶ月かかっちまうか？

今日はC-D問題レベルで頻出のUnion Findを自分で書く作業をしている
0103デフォルトの名無しさん
垢版 |
2023/10/28(土) 08:54:36.64ID:Ez/aDbKH
>>100
ヤクの毛刈り状態って慣用句があるのね
まさにそれだわ
>>102
なんだか見限られそうね

マラソンするのにスタートラインで片一方の靴だけ履いてうろうろしてる状態だわ
もう先輩の背中が霞んでいる


>>101
そうコードランナーあればこそのVSCode選択の理由です
いろいろできる分設定がややこしいけど。
0104デフォルトの名無しさん
垢版 |
2023/10/28(土) 09:24:58.62ID:NkomaJCq
Wandboxみたいなオンラインコンパイラでも人によっては暖色までいくからな
環境構築は非本質
0106デフォルトの名無しさん
垢版 |
2023/10/28(土) 20:33:35.18ID:jWGzqwz7
蟻本のはunion by rankを実装してるけど
union by sizeを実装してサイズを取得できるインタフェースを作ったほうが
実用上はお得なのではないかと思う
蟻本のは経路圧縮もしてないからwebでも調べたほうがいいかも
車輪の再発明いいじゃんね
0108デフォルトの名無しさん
垢版 |
2023/10/28(土) 23:28:04.63ID:jWGzqwz7
2問しか解けなかったけどまだレーティング低いからレートが上がった
逆元のライブラリを作っておけばE問題も挑めたかもしれないから今度つくろう
0109デフォルトの名無しさん
垢版 |
2023/10/29(日) 08:50:29.48ID:Y6XfPZLZ
やっとこさアカウントの新規登録をした！
その名も"ヤクの毛"
コンテストの参加はまだかかりそうだけど
150日でどこまで行けるかが自分課題。
0110デフォルトの名無しさん
垢版 |
2023/10/29(日) 10:25:19.37ID:3Uq29h2r
ヤクの毛w
登録お疲れさま
環境構築ガンバレ
150日だとコンテストに参加できるのは20回ぐらいだな
1回に20ずつアップすれば茶色になれるな
俺は最初の1回は10台のレートしかつかなかったけどそれ以降は順調に増えてる

今日は拡張ユークリッドの互除法で逆元を求めるコードを書いた
0111105
垢版 |
2023/10/29(日) 16:31:22.45ID:BfylPvH9
>>106
蟻本は、木の縮約をしていない

子の追加時に、親がルートではない場合に、
親からルートをたどって、直接ルートに子を追加する

木の高さ・rank は、
2つ木の併合時に、rankが少ない方を、子にする

今、場合分けして図を描いて、論理的な考え落ちがないかチェック中。
頭の体操になる
0112デフォルトの名無しさん
垢版 |
2023/10/29(日) 22:20:10.67ID:3Uq29h2r
しっかり場合わけできるのはすごいな
俺は出来上がったものを適当に使ってたから
人のコードを参考にしながらUnionFindを書いたよ
実際に使ってみたらバグがあった
1つの集合のサイズを取得するコード
rootをたどってサイズを返さないといけないところを
そのノードのサイズを返すバグがあったからそこを修正したよ

今日は昨日解けなかった問題を、人のコードと解説を見ながら解いたよ
C問題はしゃくとり法だった
しゃくとり法は本番思いついていたのだが、不慣れで引数を何にするか迷ってる間に時間切れだった
0113デフォルトの名無しさん
垢版 |
2023/10/30(月) 06:43:45.13ID:eNvHbAw5
>>110
なんとか法みたいなことはその都度調べるとしても
逆元とかいうような数学の基本的な単語の理解をしていない身とすれば
またまたおおきな毛玉に出会ったような気がする
0114デフォルトの名無しさん
垢版 |
2023/10/30(月) 12:07:50.54ID:KHkbnNCS
大きな毛玉？ケサランパサランみたいな？

逆元というのはかけると1になる数字のことだよ。
1なら1、2なら1/2、3なら1/3が逆元
つまりa*逆元=1になる
たとえば11で割ったあまりの世界では
2*x=1 mod 11の答えは6になる(2*6)mod11==12%11==1
同様に3の逆元、4の逆元、...10の逆元はそれぞれ4 3 9 2 8 7 5 10になる(プログラムで計算した)

尺取法はバグらせやすいアルゴリズムとして有名らしい
0115デフォルトの名無しさん
垢版 |
2023/10/30(月) 13:06:42.65ID:5GlLglIx
尺取り法は書き方を決めておくことがバグらせないコツだと思ってる
私は下記で書いた
int ans = 0;
for (int l = 0, r = 0;l < N;++ l, r = max(l, r)) {
while (r < N && rを加えても条件を満たす) ++ r;
ansに[l, r)を足す
}
新着レスの表示
レスを投稿する

ニューススポーツなんでも実況