競技プログラミング総合スレ 65
レス数が1000を超えています。これ以上書き込みはできません。
!extend:checked:vvvvv:1000:512
↑2行になるようにする
競技プログラミング、オンラインジャッジ、プログラミングコンテストや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/
※前スレ
競技プログラミング総合スレ 64
https://mevius.5ch.net/test/read.cgi/tech/1664700238/
VIPQ2_EXTDAT: checked:vvvvv:1000:512:: EXT was configured 社長曰く以外の感じなので、例えばバックエンドエンジニアで良い評価が欲しいなら青色くらい必要
https://twitter.com/chokudai/status/1474258242452987907
AtCoderがそのまま役立つ業務ってだいぶ少なくて、
【評価高】は赤まで、
数理最適化・研究開発
【評価中】は青～水まで、（黄もまれに？）
バックエンドエンジニア・機械学習エンジニア
【評価低～評価無】は水～茶色まで、
その他のITエンジニア
くらいがプラス評価になります。関連度が高ければ高いほど高いレートが評価されやすくなり、逆に低いと低いレートですぐカンストしちゃう、って感じ。
評価低に関しては「コードが書けることが保証されてる」くらいのアピールにしかならないです。
https://twitter.com/5chan_nel (5ch newer account) 問題文によってX軸とY軸がどの方向か明記されていない場合どうすれば良いのでしょうか
左右方向がX軸
上下方向がY軸
と思って解いていたら解説の画像見ると真逆でした
例えば鉄則本のB09 - Papers >>3
プラス効果実感できそうなのが青くらいというのはそうなのかもしれない
茶色以上だったら、ないよりはある方がマシって場面はたくさんあると思うけどね
こんなのセルフプロモーション力次第だから、そこがヘタクソだと何色でも…というところがあるかな >>8
本持ってないので確認できないけど、確かに普通数学では左右がx軸、上下がy軸方向で書かれることが多いからちょっと混乱する人もいるかも
問題見た限り、答えに影響しないのでどっちで書いてもいいってことで、逆に書いたんじゃないかな
ちなみに競プロだと配列の添字の関係で逆に書く場合のメリットもあるんだよね（この問題はそのメリットも別にないけど）
明記されてない場合はほぼ答えに影響しない場合だから、勝手に自分の中で決めればいいと思う、影響するんなら質問タブから聞こう >>11
ごめん、思い切り多次元配列使うから普通にメリットあったね 軸の方向なんてだいたいどうでもいいよ
自分の好きに描いてくれとしかいえない
向きの考慮必要な問題なら普通は記載されてる
ただまあ実装としては配列操作の都合上、どっちかのほうが簡単になることはあるので、
賢いひとだと考察や実装しやすいように柔軟に向きを入れ替えてるかな >>11
＞＞答えに影響しないのでどっちで書いてもいいってことで、逆に書いたんじゃないかな
ありがとうございます 業務プログラミングでも画像処理やってるとたまに軸の順番が入れ替わるから困る googbyeみたいに定期的にall ratedコン出せるのすごいよな
逆にAtCoderが厳格すぎる 質問
apg4bが終わったばかりの競プロ初心者だけど、次に読めばいい本は3つのうちのどれですか？
・競技プログラミングの鉄則
・問題解決のためのアルゴリズム×数学
・アルゴリズムとデータ構造 apg4b終わった時点でも人によってどのくらいの行間を読めるか違うから一概に言えない
実際に書店とかで読んで選んではどう？ 新しい本だから今取り組んでる人が多いという理由で鉄則本かなあ
〇〇本を読んで上達したみたいな話は聞かないから
結局自分の努力次第だよね AtCoder Problemsで自分のレートに近いdiffの問題解いていくのが結局一番着実だったりする 蟻本完璧に咀嚼しきれたら青〜黄色はいけると思うしアレは中級者向けでしょ
螺旋本は教養としては大事だけど傾向が若干違う気もするし鉄則本かけんちょん本が良さそう 結局本とかで勉強するよりも自分の実力ちょい上の問題を解きまくる方が効果あるのは事実 黄色より上は知識とは別体系の技能だから、本読んでどうこうって感じの世界ではないかな 蟻本は難易度的には、第2章が普通に初心者向けの内容だし、初心者でも読めるでしょ
ただジャッジがPOJとかだったりして不便、という理由があるために今どきの入門者向けではないかなあ
基礎問題のあとにいきなり難易度が上がった問題が出てきたりするけど、そういうのを飛ばせば誰でも読めるだろうし、
そういうのも全部習得していけばABC卒業できるほどの基礎力が付く
鉄則本は基礎問題が中心に載ってて、解説もわかりやすいから、数学力に自信のない初心者にはとてもおすすめ おじさんが学生の頃は螺旋本読んで蟻本読んだら青になれた
最近は新しい本出てるらしいけど読んだことがないので何色向けか分からない ・数学の得意不得意
・プログラミングの経験
この二つで結構勉強方針変わるかも そうそう、初心者向けじゃない競プロの本なんてないけど、地力の違いでどれがフィットするかはちょっとずつ変わるよねえ 数学そんなに得意じゃない場合、大学数学の場合の数や整数の参考書が役に立つこともある あ、大学数学じゃなくて大学受験な
大学数学も実は役に立つ本あるんだが >>30
蟻本も人によってはくどくなくてちょうどいい入門書だからね 数学は特に得意でも不得意でも無いよ
あと、プログラミングの経験はほとんど無くてAPG4bが初めてと言っても過言では無いと思う
上で挙げた3つの本の他にけんちょんさんが書いてるAtCoder入門なんかも良さそう 運営がワールドワイドならそれも可能だろうけどこれはしゃーねえべ(´・ω・`)ぽれはお盆の時期とか出たくないのに逆にコンテスト生やしてくるし 俺も正月はいいや、暇だけど実家だから回線悪い(´・ω・｀) 整数と場合の数だと大学への数学のやつかな
あれを全部スラスラ解けるぐらいにしとくと捗る 初等整数論とか組合せ論の初歩についてあまり詳しくないけれど、
プログラミングコンテストでは強いっていう人はいるんですか？
プログラミングコンテストで強い人はみな数学にも強いのではないですか？ プログラミングコンテストにもいろいろあって、競技プログラミングのアルゴリズムという分野のコンテスト（具体的にはAtCoderのABC、ARC、AGCは全部そう）は、整数、組合せ論の問題が離散数学の一部として出題されるので、もろに成績に関係する
一方で、ヒューリスティックだったりKaggleに関しては、実はそうでもないんじゃないかという気がする
当然、基礎的な能力として、整数と組合せ論を最低限勉強しておいた方が離散数学的な操作に慣れて思考の助けになるところはあると思うし、勉強さえすればレベルの高いところまでできるような人がいずれのコンテストでも上に来ると思うけど 組合わせ論・数論の精選とかパーフェクトマスターみたいな数オリ用対策用の参考書って競プロにも役立つの？たまに買ってる人見かけるけど黄色以上で効くのかな 繁野麻衣子著『ネットワーク最適化とアルゴリズム』を買いましたが、積読状態です。
この本は競技プログラミングに役立ちますか？ いつだったか、数オリ高度典型の幾何がAGCかARCに出てて話題になったからごくたまに効くんじゃないか >>47
未読なので目次見ただけだけど、この本のアルゴリズムは全部競プロで頻出だと思うので、知らない知識を摂取するって意味だとどれも役立ちそうかな？ >>44,48,50
ありがとうございました。
>>50
読んでみます。 純粋な学術書は体系的すぎて競プロで使うには多く説明しすぎてることもあるから、効率がいいかはわからんな
ただ、普通に競プロ関係なく勉強になるところはいい 最悪計算量と何ができるか知ってるだけでも競プロでは使えるな
順位クエリ処理できる二分探索木の仕組み分かってないけど他人のライブラリコピペして使ってるわ なかなか灰色から上がることが難しそうですね...
とりあえずアルゴリズム×数学 本 か鹿本(AtCoder入門)を買ってみませんか
茶色に上がってみましょう 和を積に変換
https://twitter.com/noshi91/status/1608869946792235008
和のままで十分性質がいいじゃん！と先入観で思ってしまうが、あえて多項式を使った式を介して積にした方がtop treeに乗せやすいみたい
面白い
https://twitter.com/5chan_nel (5ch newer account) >>55
数学が苦手な人は入茶でもかなり時間かかる時代な気がするね
灰色を分割して階級をさらに分けるのは真面目にありだと思ってるけど 部分列（連続ではない）の和の総和は[x]Π(2+ax)か
この場合はそんなに役立ってる感ないが TopTreeて高度典型みたいなやつだろ
俺も名前しか知らん LC木の上位互換でLC木に乗らないものが乗ったりするが、そもそもLC木自体がマニアックでAtCoderではなかなか使用機会ないだろうな
強いデータ構造がなきゃ解けない問題、強いデータ構造で一瞬で解けてしまう問題をAtCoderがそもそも好まないというのもあるし データ構造に載せるモノイド、頑張れば多項式か行列に帰着できる説 半束とかはモノイドだけど多項式や行列にはならなくないか 適当に和に相当する演算を導入して半環の積にできんかとか考えたけど無理か あまり半束であって束じゃない例について考えたことなかったけど根付木のLCAとか？ >>65
ところで、束論はどの本で勉強しましたか？
離散数学の本にすこしだけ書いてあることがありますが、役に立ちますか？ >>66
min, maxの一般化であるってことと定義を知っているってだけで、まともに勉強したことないかなあ
どこで最初に知ったんだろ、雪江代数にあったっけ？
ゼータ変換を束を使って捉え直すことができるみたいなのはあった気がするけど、束論自体をつきつめることが直接競プロにプラスになる感じではない印象
というか、抽象代数の勉強は全般的にそんな感じな気がする (1+a_k)の積を微分していったら定数項に基本対称式が全部出るのか 嬉しいかなあ 今日日モーメント母関数がそんなにうれしいものなのかという話になりそう 何の捻りもないけど、セグ木にのせてrange M次対称式 query（与えられた区間内の要素のM次対称式を出力）がQMlogNで解ける と思ったけどlogMつくか
更新ないんならセグ木に乗せるんじゃなくて累積和でやる方がいいな どっかで出てそうと思ってelementary symmetric polynomials segment treeとか検索してるけど意外とないもんだ 鯖のcpu性能が上がったせいで過去の問題が別の解法(計算量悪化)で通せるようになることってあるのかな？
パソコン新しくしようとしてて気になった N=2*10^5だとガチガチにチューニングしたC++で非想定が通ってしまうからN=3*10^5にしたみたいな問題だと、普通に非想定通るようになってそうだな 土夜と日夜だったら普通の人は土夜の方が予定入りやすいとかあるんかな テレワークで出勤時間なくなってからは24時までに寝られれば十分になった AtCoderの過去問って他人の提出検索できるけど、case_11.txt だけ間違えてるやつ一覧みたいのって取ってこれるんかな？ 同じようなテストケース通し具合のコードを持ってくるサービスあった気がする
探したけど見つからなかった
確か赤コーダーTLで見つけたはず >>84 >>85
もしかして: AtCoder Companions 言語仕様の勘違い由来のバグ取りはかなり気付くの難しいから、初心者がそういうの見つけるのに使えそうだな 今年こそ青に定着したいのに三が日何もやってねえ...(´・ω・`) 正月で生活リズムが整っちゃってこどふぉに出られなくなっちゃった Hello 2023普通に良コンテストだったぞ
ドンマイ えAtCoder Companions有能すぎるんだけど. これ何でテンプレ入ってないん? TL少し長めの問題なら、10^9回計算する解法でも通るんだね（想定解法じゃなかったけど） 重複組合せの式nHrで、整数のオーバーフローをできるだけ避けて計算したいのですが
とある、場合の数を数える問題で、普通はたぶんDP的に解くんだけど、規則的な形だった
ので、「これって重複組合せじゃん」と見抜いたんですよ
でnHrを例の階乗の公式(n+r)!/n!/r!で計算して、テストケースを走らせるとnやrが小さい
のは通るのでやはりおkらしい。ただnやrが大きくなると階乗がオーバーフローしてしまう
解が数式で求まったのに数値的にはそんなに便利じゃないって?
でも普通nHrの計算って分子と分母でキャンセルして結果は大きくならないことが多い
ですよね。うまいこと変形したらオーバーフローしなさそう。もしそういうのが既にあれば
nHrの漸化式みたいので計算する手もありそう、って結局DPみたいなことしてる気がw >>94
どちらも2から60ぐらいの間の整数がランダムな感じでセットされるようです >>96
どうもです。が、n, mは実際には100ぐらいまでいくようで（すみません）、
リンク先の最初のコードだと 100 C 99 とかで間違った答えが。おっとクヌース先生敗北?
こういう場合は普通にCの性質より 100 C 99 = 100 C (100-99) = 100 C 1 とすれば
精度も計算量も良さそうです
というわけで... 全テストケースクリアしました! ありがとうございます >>99
そうですね、nCrで r=n/2付近はでかい数になりますよね
テストケースではそういう場合は除外されているようです
そういうわけで、組み合わせを直接計算するとテストケースでは64bit整数がいるんですが、
組み合わせの直接計算でなく、DPで再帰的に場合の数を計算するようなコードだと
32bit整数で大丈夫な感じなんですが... ええと ああそうか、それが実質的には >>97 パスカルの三角形を上向きに登っていくのと等価なの
かな。三角形がでかい場合はあんま三角形の底辺の真ん中の方には行かない場合のみで
と自己納得w よくわからんけど答えが32bit整数に収まる程度なら適当に大きめのmodとればいいんじゃないの Dの解説読んでもわけわからん
まず、割り切れるのがわかってるんだから、iの最大値なんて関係なくない？
iの2乗で割り切れる時に解が見つかるとして計算したけど時間内に解が求められなかった。
糞問題じゃないのこれ？ Dで素因数分解出来ることが保証されてるのが頭から抜けてたせいで絶対想定解じゃないだろって思いながら無駄にミラーラビン素数判定法とか使ってしまった 素因数分解出来ることっていうより素因数分解の一意性か 問題は全然クソじゃないと思うけど、i=1,2,…,⌊N^(1/3)⌋のうち、N が i で割り切れるような最大の i って書き方が何か変で、i=2,…,⌊N^(1/3)⌋のうちNを割り切る最小のiと言った方が正しいような気がする G、本質パートからしてボリュームあるのにさらに任意ｍod二項係数使うんかいって思ったけど、想定解は全然使ってなかった >>105
ちなみに、そのやり方でTLEしないと思うんだけど、N^(1/3)までで探索打ち切った？ あー、二乗の計算時間もだめだってのか。効率化難しいな。
sqrt使うところに頭が向かわなかったわ。
お前らよく解けるねこれ... Dは想定回じゃなくても、いろんなテクで解けるし、みんないずれかの解法にサクッとたどり着いてる感じだな >>113
なんかその書きぶりだと、もしかしてj^2 = N/iになるようなjも探索で出した感じ？ Eが素直なDFSすぎてDと逆でも良いだろとは思った Eはむしろ個人的には意表を突かれた感じでギョッとした
Fの方が実は素直にロリハやるだけだったりする >112
すまん、冷静に考えたら打ち切ってない
必ず1個の解が見つかるはずで、解が見つかったら打ち切ったら良いんだから、N^(1/3)までカウントアップしないと思ったんだ。だから、N^(1/3)で止めるロジックは無意味だと思ってる。
ただ、自分のやり方だと解を二乗根に絞って計算したせいで最大値がN^(1/2)/2になってしまったんだね。
そのせいか... >>119
>必ず1個の解が見つかるはずで、解が見つかったら打ち切ったら良いんだから、N^(1/3)までカウントアップしないと思ったんだ。だから、N^(1/3)で止めるロジックは無意味だと思ってる。
確かにそれはそう、ナンセンスな質問ですまない
O(N^(1/2))になってたのがTLEの原因っぽいね EやFはサクッと解けたけど、おれもDはちょっとギョッとしたよ
おれも数学弱だな
てかEなんてほぼナイーブで解けるレベルに感じたし、500点問題としてはあまりにも簡単すぎでは Ex、Polya の原理や包除原理知ってても簡単に見えないし、ABCで出した理由は有名問題だからなんかな というか、GみたいのもOEISにあるのな
この問題用に出てきた謎の量にしか見えなかったが なんちゃらのフルイ使わないでやったらTLEして
脳死で数値設定したら足りなくてWAした雑魚 ついこないだライブラリ作ったポラード・ローの高速素因数分解でDをしばき倒せたので良かった Dは簡単すぎて本当にこれでいいのか何度も見直したんだが
まず2から順に素数で割っていって割り切れたものがpかq
さらに同じ数で割って割り切れたらp確定
その場合はp*pで割った商がq
割り切れなかった場合はその素数がqなので割った商の平方根がp そうじゃなくて小さい方がNの平方根で抑えられるかを見抜けるのが本質では ていうか小さい順に割っていくならpとqの最大値で最も時間がかかるからO(root3(N)*T) >>133
p,qのうちの大きくない方は必ずNの立方根(2×10^6程度)になって、昇順から自然数を見ると割り切れた時点で素因数なのは確定するから素数の判定は実は関係ない(だからp,qが最悪ケースの√N(10^9オーダー)であっても素数判定をする必要はない)っていうのがDのポイントだと思う >>134
最悪ケースは p=2,q=10^18程度 だった >>136
pが2なら最善だろ
真面目に素因数分解するんじゃなくpかqのどちらかになる素因数を一つみつけたら後はO(1) >>137
もし素数判定をするならこのqがめちゃくちゃ大きい素数のケースが判定出来ない(けど実際は必要ないことを見抜けば良い)って話 >>138
わからん
p=2なら4で割ればqが出るじゃん
最初に一つ素因数を見つけたらその二乗で割り切れるかどうかでそれがpかqか判別できるからそこからO(1)になると最初から書いてるんだが >>139
素数の判定云々の話をしてそれに対してそれだとアウトってレスがついてたから、アウトな方の方針を書いただけで小さい方が高々Nの立法根になることを見抜けてるなら問題ないってこと 見抜けてるのは最初のレスを見てもらえばわかると思うが俺が見抜けてようが見抜けてなかろうがそれでアウトになるはずなくね？ 昇順に素因数を確認する方針を取れば自然と10^6程度までで解が求まるけど、実際にはその方針に辿り着けないような人もいて、正解の方針を取らないで何も考えずにp、qの素数判定をしたりすると間に合わなくなるからそこで篩い落としてるっていう話
別に間違いを指摘してるわけではない >>126,128には計算量の話が全くなかったから突っ込まれてただけだよ
計算量がNの立方根らへんになることがわかってれば良い >>131
このアルゴリズムでだめな理由を書いてからいえやw 初歩的なプログラミングに慣れてきたから、ABCの過去問を解いてるんだけど、解説を読んでも意味不明な場合はどうすればいいんだ？ABC284のC問題が何度読んでもよく分からない 深さ優先探索とか幅優先探索なんてAPG4bになかった気がする頭がどうしようもなく悪いみたいだから競プロやめようかな こんな簡単な問題で詰まってるってどうしようも無いレベルの脳障害よな…、 p=2の時に最悪になるなんてとぼけたこと言うやつが煽るスレ
こんなアホが複数いるとは思えんから自演だろーなー
悔しかったんだなー >>152
これはdisjoint-setを知ってるかどうかだけの問題だから解けなくても何も気にしなくて大丈夫 レスバするつもりはないけどせめてワッチョイ確認しろよ
自演してるのはどっちやねん お前だろw
知能でわかるのになぜバレないと思うんだw 幅優先探索も深さ優先探索もUnionFindも知識的な話で、知らなきゃ理解に詰まるのはしょうがない
解説は基本かなりダイジェスト気味だから、一回もう少し詳しいサイトなり本で勉強すればいいと思うよ 桁数が多い平方数の平方根ってどう計算するのが正しいのかな。単に sqrt 取って int にキャストするのだと計算誤差の関係で sqrt の小数点以下が .9999989 みたいになっていたら困るし、だからと言って sqrt に任意の小さい数（0.001 とか）を足してから int にキャストするのも格好悪いし。あるいは元の数が long long で収まる大きさだったら sqrt はピッタリ求まるのかな。 >>163
確かに。でも round が安心して使えるなら、昨日の問題とは別に一般の素因数求めるコードで for (int i = 2; i * i <= n; i++) ってよく見かけるけど、for (int i = 2; i <= round(sqrt(n)); i++) と書いたほうが掛け算の回数が減っていいんじゃないかと思ったわ（計算時間の差は微々たるものだろうけど）。鉄則本での配列の宣言にもあった A[100007] とかと同じで競プロ業界のお作法なのかしら。 >>162
↓の記事にめっちゃ詳しく書いてあるけど、long longに収まる整数でもfloatやdoubleで表せるとは限らない
コンピュータの小数は難しい
https://qiita.com/y-yoshinari/items/76260f6359d5b4418b33 なんでround(sqrt(n))の方が速いと思えるんですか？ 浮動小数点数は値がデカいとスッカスカになって、例えば一定以上の大きさの奇数を表せなかったりするのが怖いんだよな
sqrtぐらいならなんだかんだうまくいくのかもしれないけど俺は浮動小数点数と仲良くないからsqrtは二分探索書いてる >>166
そっか、n の値を別の変数 m とかにコピーして、ループ内では m の方を素因数で割っていくイメージだったのですが（その場合 n は不変なのでコンパイラがちゃんと仕事をしていれば sqrt の計算は1回のみ）、i * i <= n で上限チェックをしているコードはループ内で n を変えていく想定なわけですか。 ARC対策に去年初めのARCの問題を考えてみたら、当時解けたのに今解けなくて笑えない 正月ボケで開催日を間違えて今年最初のABCを見逃してしまいました
昨年末から精進するのを休憩してプログラミングから全く離れていたので
ぶっつけでABC284やってみたらあっさりCまで解けて安心しました
そろそろ参加10回くらいになりますがDの壁が高過ぎると感じているので
灰色のまましばらく解けるものを確実にこなせたらと思います
ずっと毎日精進するのはストレスに感じ始めていたので
コンテスト前などの気の向いた時だけ勉強するようにしてみます
と書いてて今からやる気満々だったABC285は明日じゃん...
ARCは問題見ただけで自分の無能さを思い知るので見ないでおきます C、判定も分割方法もわかったけどそこから回答例出す方法思いつかなかった...
今から説明読んで精進します Bは無理だと思って捨てたけど
1,2の位置だけでわかるのかよ...
なんかそんなに行列が壊れないようなトリックになってそうとは思ったけど、
まさかここまでとは...全然気づかなかった。 むしろ、奇数偶数さえ押さえてれば1の場所だけで良いのか。 C後ちょっとだったけど500人近くも解いててびっくり C問題はslopetrick系かな？と思ったけど式書いてみたら本当に単純な一次関数でびっくり 俺がその場で考え出した超スパゲッティなunion-findでD問題何とか通してやったぜ
ひどいコードだから是非見てほしい、次のレスで やっぱ日頃から精進してないとABCまででも苦戦しますね
問題文が何を問うているのか理解するのに時間が掛かりすぎるのと
解法のイメージは出来ているのにちょっとした関数を用意してないだけで
わざわざ場当たり的に実装して手間取ったり
C問題解けたのが終わる直前でDは無理だと思ったので順位表見てたら
snukeさんがC解いたのが7分台と知って
自分の無能さを痛感しました dic = {}
flag = True
def find(tt, update=None):
if update:
if dic[tt] == tt:
dic[tt] = update
return
cc = dic[tt]
dic[tt] = update
find(cc, update)
return
if dic[tt] == tt:
return tt
p = find(dic[tt])
dic[tt] = p
return p for i in range(int(input())):
a, b = input().split(" ")
if a in dic and b in dic:
for temp in (a, b):
find(temp)
if dic[a] == dic[b]:
flag = False
break
new_ = dic[b]
find(a, new_)
elif a in dic:
dic[b] = dic[a]
elif b in dic:
dic[a] = dic[b]
else:
dic[a] = a
dic[b] = a
print("Yes") if flag else print("No") D...
サイクルになるとNGとなるようにプログラムが作りきれなかった。
Cの問題を応用すれば良いのはわかるのに、単純に時間内に改良出来ん。
もったいなかったなぁ、、、 そういえば今度応用情報受験するんだけど、競プロ勢（といっても俺はガチ初心者レベルだが）
にとって午後のアルゴリズム問題って得意だったりするんだろうか >>179
酷かろうが作ったもの勝ちだよw
dfsにこだわったのは悪くない筈なんだけど、
全探索にして、上書き発生したらNGにするだけなのに、色々脱線して組めなかったわw
最後の最後で初期値1にしてた事に気付いたしw union-find自分で実装するのめんどくさかったから最初どこかからコピペしようとしてたわ
けど、通常のユニファイと違って文字列のアクセスだからどうやって応用したらいいかがわからなかった
>初期値１
これはなんのこと？ >>187
1週間が5000日とか気が遠くなるなw TOPページの左側に表示されているランキング上位10位に日本の国旗が無いのに気づいてしまった >>190
そう思ったけど、改名前と改名後どっちがどうだとかいろいろ考えてたらわけわからなくなって結局自力実装してしまった。 >>191
ほんまやん
やっぱ日本てITレベル低いんだろうか >>188
Cの問題をそのまま利用(大文字小文字だけは違うけど)して英字列を数値に変換したんだよ
最近のdfs絡みって全部初期値が0か1の問題だけだったので、そのまま組んでしまってて、、、
でも例題がそれで通ってたせいで迷走してしまった。 >>195
なんと。。。。職人技だな、その発想はなかった。
数字に変換したいのなら普通にハッシュ関数とかの方が計算量的に早かったりするんだろうか >>196
よくよく考えたらグラフに置き換えるのに数値に変換する必要もないですね・・・
グラフ問題出たら最低でもノータイムで解けるようにしとかないといかんですね。
勿体ない時間が多すぎた。 >>197
連続した整数にするできるならまだしも、離散的な数字を生成するのならメリットはあまりないですな
グラフ問題ノータイムか。。。まだまだ練習が必要そう そうだ、あとA問題
これの解き方まじでわからんかった
https://atcoder.jp/contests/abc285/submissions/38045467
こんな感じで書いたんだけどもっと効率的な書き方あるんだろうか >>200
大きい方を小さい方で割った答えが２ならYes そうか。。よく見たら下のノードは倍だった。。。。。
いやひどい。。なぜ気づかなかったのか >>199
＞離散的な数字を生成するのならメリットはあまりない
その通り・・・C問題の後で、これは数値に置き換えると効率よくなるはずだ！
って声に従って変換してました・・・が意味なかったですね。
なんというか、学校等の模試って１問前の問題を応用することが多くて、
それが完全に染みついてるんですよね。 Aは完全二分木の頂点を配列上で管理する話で、発展的な知識で思考をショートカットできる系の問題と言ってもいいかもしれんな（これぐらいなら再発明するやついっぱいいるだろうが）
ARC/AGCの低難度で出る一見アドホックな問題もこういう感じだったりするんだろうか >>202
自分は法則探しに時間使ったので、ある意味力業の方が早かったかもしれません。 >>194
AtCoderは日本で現役最強格の人や、世界的にも最強に近かった日本人選手が運営で作問作業のコアな部分に携わってるから出られなくて、ランキングにいない
それを差し引いても、中国や東欧の方がやや強いけど >>204
過去のABの比じゃなく難解だったので飛ばして
C→B→Aの順で解きましたが
全条件を組み込みするのは絶対に嫌だったので
何か法則があるんだろうなと捏ねくり回してたら2倍か2倍+1に気づいたので
if文1行で解けましたが解説見ると知ってる人や上位の方が1-2分で解けるのも納得です
考えて解く問題より知ってるかどうかって問題が多い気がしますが
どちらにしてもD問題の壁が高過ぎるのは変わらないので
DNAとかIQなど持って生まれたもので精進レベルではどうにもならない感が半端無いなと思います 二分木の配列実装を知らないレベルでIQやDNAを云々するのは結論を急ぎすぎ
知識増やしても壁を乗り越えられなくなってから言おう AtCoder青色くらいまでは本一冊程度の知識を身に付けていますか？で終わりなんだよな
典型90問とEDPCを全部解いてて水色以下の人を見たことないし 努力でどこまでできるかについては諸説あるが、知識がないうちは自分が知識あれば解けるかどうかすらも分からんもんで、最初のレートの伸びが悪くても一旦勉強してみてから考えてもいいんじゃないか
ABCのD突破するのに要る知識だったら普通のエンジニアリングで遭遇するものも多いから、そこまで損はない 最初天才にしか見えなかった解き方が、有名でありきたりな定石の変種に過ぎなかったなんてよくあることよ
まあもちろん発見者は天才なんだろうが 少なくともD問題くらいまでに関しては毎回かなり典型的な知識しか要求されないし問題も素直なものが多いからそのレベルだとセンスとか関係なく訓練すれば迷わず書けるようになると思う それとレートの伸びが早くて天才に見える人も、中学受験とか数学オリンピックで競プロの役に立つ思考パターンを予めたくさんインプットされてるのがデカいんじゃないかって話もあるからな AtCoderの社長の人の本を少し読みましたが、アカデミックな香りが全くしません。
そういう人が非常に強いというのが不思議です。
逆にアルゴリズムが専門の大学教授は強いのだろうかと疑問に思ってしまいます。 弱い相関はあるだろうが、基本別の能力だぞ
極論チェスプレイヤーが数学者として成功できるかみたいな話
逆にアルゴリズムの世界的な研究者がCodeForcesでそんなに強くなかったりな
高齢だからしょうがない部分もあるが アルゴリズムや関連理論を知っていることと時間内にアルゴリズムを問題に適用できるかは別だしな
だから研究者でも寒色は全然よくある
まぁ若い頃に精進すればもっと上に行ってただろうけど、それをする必要があるかはさておいて >>214
作問者はそういう経歴を辿ってるひとだらけだから傾向は偏っている
アカデミックな研究者が作問してたらもっと別な傾向になるだろう。新しく発表されたアルゴリズムを元ネタにした作問とかしそう そうなった場合"精進＝アルゴリズム系の論文を読み漁る"になった可能性もあるのか...
そうだったらハマってなかったわ まあレート競争するのが楽しいって体質なら、そうなったらそうなったで普通に論文も楽しく読めちゃう可能性あるけどな
Kaggleで論文読むの割と楽しいぞ 暖色コーダーは割と気軽に論文読んでるしな
競プロ強い人は研究者適正もあるとは思うわ 983 デフォルトの名無しさん (ﾜｯﾁｮｲ 6f71-0qRf) 2022/10/03(月) 20:26:59.27 ID:lndyBnH50
https://twitter.com/intent/favorite?tweet_id=1516784253656506369
@rui314
さん
あれはSAPIXとか鉄緑会と同じカルチャーだと思う。
https://twitter.com/5chan_nel (5ch newer account)
https://twitter.com/5chan_nel (5ch newer account) >>222
せめてURLくらい直してからコピペしろ >>226
解説読んで無いからよくわからんけど26進法じゃないの？
書いてある方法の解き方がよくわからんw 26進法ぽいっちゃぽいけど0が無いんだよな
Aが1で26が桁上がり無しのZ
27で桁が上がってAA
単純に前から順にAからZを1から26に変換して26倍して次を足せばいい C#は多分こんな感じ
Console.WriteLine(Console.ReadLine().Aggregate(0L,(p,c)=>p*26+c-'A'+1)); >>227
pow関数使って26の累乗を求めるアプローチだと
整数型にキャストしないとWAが出るのです >>233
10の16乗の桁数くらいだと1ずれるんですよね
>>234
3つだけWAになって何これ？ってなりました その問題特有の性質じゃなくてc++だとpow関数がdouble型を返す仕組みになってることが原因だから問題の本質とは関係ない
pow関数は誤差が怖いから他の方法を使って累乗を求めた方がいい 225,226の言ってる事が理解できて勉強になった
楽したいが為に使おうとしちゃうけど、関数の使い所って難しいね C++のpowあるあるひっかけ問題だなと察して
場当たり的に自作powぽいものを実装してACしましたが
以前他人様の提出見た時に自作powをテンプレ化してる人が複数人いて
なんでだろうと疑問に思っていましたがこういう時に役に立つのだと思いました
ちょっとしたことですがこういう典型的な自作関数などのテンプレを用意しておくだけで
数秒から数分の節約になるんだなと思いました
教プロやってる人にとっては知ってて当然のことなのかもしれませんし
これを知識と言うのか典型と言うのか分かりませんがテンプレなどの事前の準備が大事なんですね >>237
いいや、doubleが溢れる桁数を問う問題を兼ねてるからいい問題と言ったんだよ
doubleだけじゃなくlong longでも同じことが起こり得るから本質に気づいてないお前は気をつけとけよ >>241
わかんない？
困ったな
doubleは整数部と小数部で計算が違うから整数部のみ使う場合において誤差は発生しないんだよ
ただし整数部が大きくなりすぎると指数を使って下の桁を小数部に回すから誤差が発生するようになる
doubleで扱えなくてlong longで扱える整数の範囲ということを問題から読み取る必要があるってことね
long longも大きくなりすぎると負の数になって計算が狂うから知らなかったなら気をつけなよ よくわからないんだけど、pow(a, b)は普通exp(b*log(a))で実装されてるから整数の自然数乗だろうが非整数を扱うことになるんだけど、そういう話ではない？ >>244
そういう話ではないな
俺はpowじゃなくdoubleの話をしてる
処理系の実装で整数のpowでもわざわざ小数を使ってるせいで誤差が出るとするとそもそも戻り値がdoubleだろうがlong longだろうがpowを使うなという話になるな
つまりdoubleじゃなくpowの実装がザコいせい ここまで堂々と頭の悪いこと言われると反応に困っちゃう 文字は聞き返さなくてもちょっと目を上げれば読み直せるからまあ頑張れ
話について来れなきゃレスしない方がいいぞ 前回のARCのCとDを焼きなましでやってるのを見てAHC初心者から見るとすごいなーと思うばかりなんだけど、こういうのって近傍設計が肝なんだろうか 間違ってる知識を堂々と書いてるようじゃそりゃC、Dくらいまでしか解けないよ 多分前回のARCのCとDだったら焼くより普通に解く方が簡単だな 字が読めないからどういう話で自分が何を間違ってるかに気づいてないんだろ IEEE754を覚えていないのは百歩譲って許せるとして、誤り指摘された時に調べずに嘘を強弁できるのは精神力すごいわ
競プロには向いてないけど 競プロなんかより浮動小数点数の仕組みの理解の方が大事 日本語からまなべばいんじゃね
ひらがなおおめにしてみた 前回のD問題でも自分の誤りを認めずに暴言吐いてた奴と同一人物だから無視でいいよもう そういやそんなやついたな
寒色は人じゃないんだから身の程わきまえろよ 競技プログラミングの鉄則で勉強してるけど本当に才能ゲーすぎるな
俺みたいな脳障害だと☆3レベルの問題でも初見で解けない みんなが初見で解ける問題なんて本に載せても意味ないやん なんか毎週こんなことやってる自分が急に虚しくなってきた
生まれつき頭の良い人達だけが楽しめるものなんでしょうね
勉強してどうにかなるようなものじゃないって薄々気がついてたけど
毎回自分の無能さを思い知るだけの罰ゲームは終わりにします 初見で解法が思いつかない
解説を少しづつ見てヒントを小出しにしつつなるべく自力で解く
それでもどうにもならないから写経する
知ってるか知らないか
覚えてるか覚えてないか
テンプレ作ってるか作ってないか
初見で解けるか解けないか
そりゃ流行るわけ無いですよ
極一部の出来る人しか楽しめない
上位も全体も外人だらけ
フェードアウトした人多そう BとCでつまづいたせいでD解けなかった
Cはもうちょいシンプルに解けるやつにしてくれよw Fまで解けた割にパフォ渋いんだけど参加者数の問題？
順位も青色から見てそんなに悪くないのに Bはnnのケース忘れてた
Cは最小0円を忘れてた
限られた時間だと短縮しすぎてこういうの漏れちゃうね >>268
なんかpredictor変かもしれんね >>272
前回も表示バグってた気がするしそうだと信じたい >>260,265
マジレスしておくと、ある程度のレベルまでは間違いなくガチ暗記ゲーだからね
異常な天才は競プロ対策してなくても解けまくれるかもしれんけど、普通のひとにとっては暗記ゲー
そしていろんなことを暗記しまくると(理解度が深まってくると)、応用もどんどん効いて難しい問題も解けるようになる
まあ大学受験とかでも同じだろ
基礎を暗記してからようやく応用ができるようになる やっとF自力ACできた
素数である必要がなかった… >>277
CD程度の問題を見て解法が思いつかず何やっても無理だと悟って
あまりの自分の無能さに嫌気がして
悪態をついた愚痴にマジレスしてくれる優しさに救われます
暗記ゲーにしては範囲が広すぎるし
勉強することを精進だと自分に言い聞かせてましたが
毎回理解出来ないものを永遠と写経するだけになっていて
初見で解法が思いつかないことが苦痛とストレスになって
病みそうなレベルなので
精神衛生的にも少し教プロから距離をおくつもりです >>281
まあ、プログラミングというより数学の競技だと思っておけば安心するだろうね
大学受験数学は当然として、中学受験数学で学ぶようなテクニックが活用できたりするし、
そういう受験数学のエリートがさらにアルゴリズムをめっちゃ勉強して競い合うのが競技プログラミングだ
もし中学受験とかやってないのに、そういう連中に追いつき越えたいなら、そういうエリートがやってるよりもはるかな修練が必要だよ
まあそういうエリートは数学的な問題を解くのが大好きだから現時点の瞬間的な修練量でさえなかなか超えられないだろう
アルゴリズムやデータ構造というより数学そのものの勉強も必要になってくるしね 「競技」プログラミングが十分な勉強と対策をしなくてもできるなら、もうそれは競技じゃないんよ
競技なんだから、勝ちたきゃ多くの対戦相手を蹴落とすだけの努力をしなきゃいけない 今日のARCで大事なのは700点の難度だよなあ
maroon回ほど極端に難しくなることはないと予想 ABCだったら初見力なんてそんなに大事じゃなくて、ちょっと変形された問題が解けることが重要だと思うんだよな
ちょっとの変形に対応できるかどうかの練習をするのにも、土台としてまず知識が要るので、知識ないうちは才能の有無すらわからんよ
むしろ初見力があっても知識不足だと解けないのがABC
AGCは逆に知識無くても初見で解けるやつもいるから、最初はABCよりAGCの方がパフォーマンス出やすいやつもいる ただ、瞬発的に解法を発想できないのは仕方ないにしても（知識不足だと発想の引き出しがないからそりゃ無理）、解説を読む段階になったら時間を掛けてでも書いてあることを理解するように心掛けないと類題を解けるようにならないと思うぞ 800点はブレで結構解きやすいこともあるけど900点はきっちり難しい印象がある
ただ昔の問題だと1000点超えでもそんなでもない問題も稀にあるから決めつけで解けないと思うのもよくないんだろう 昨日のG残り時間少なくて諦めてたけどEかFくらいに置かれてたら印象変わってそう
600点問題の基準が良くわからない ABCは自分の中では結構E<F=G<Exみたいな印象があるかなあ
真っ当にGの方が難しいときもあるけど それと6問ABC時代のF（600点）は今のGより難しかったような気がするね 質問
long long ans＝1ll ＜＜60
このコードのllと＜＜60ってどういう意味なんですか？
apg4bにも載ってなくてわからん… llは1をlong longとみなすってこと
<<はシフト演算子 <<はシフト演算子と言って、数値の各bitをずらす働きがある
例えば5はbitで表すと101だが、5<<2は10100だ
bitを1つ左にずらすごとに数字は2倍になるから、これは1の2^60倍をansに代入してる
ただずらす数字がint型だと、通常32bitだから60もずらしたら溢れるという問題がある
そこで1LLと書くことでlong long型の1であるとコンパイラに教えてやり、オーバーフローが起きないようにしてる 正解してたんだけど、
Aの問題の99...353で割るタイミングってどこが適当なんだろう？
よくわからなさすぎて10^i全部に99…353で割って、更にA＊B前にも99…353で割って、
最後の出力でも99…353で割ってしまった。 D1見つけてそれ使って比較出来るところまでは気付けたのにマージソートにまで辿り着けなくて勿体ない お、ナメクジから初めてようやく茶色になれたw
こらからも頑張りますw >>297
Cまでは解きたかった、、、
遊びがない場合とで分けたかったんだけど、遊びがなくても完全一致のケースもあるし...と考えてたら時間足りなかった
場合分け発生するのによく速攻で出来るね 比較的解きやすい回だったはずだけど、Dなんで思いつけなかったんだろう
反省 >>303
A
自分が解説の意図を勘違いしてるかもしれないけど、ajとbjを交換することを考えるなら、
aibj+ajbiとaibi+ajbj
ではなく
aibj+ajbiとaiaj+bjbi
を比較するべきでは
Cはいま見返したら問題なかった
自分が初見時に誤読したのか訂正されたのか分からん（圧縮後のBの長さ、って最初から書いてあったっけ） >>307
自分の認識だけど
Aは解説。
307の言ってるのは解法。
Aの解説を達成するためには307で合ってるけど省略されてるという認識。 >>309
ごめんよく分かってない
解説の
ここで、～前者となります。
と、
よって、～最小化できます
の部分がどう繋がってるのか分からない 2＊4+3＊5と 2＊5+3＊4を比べる時
Aの解説は
2＊4+3＊5、3＊5+2＊4
どっちでも良いけどどっちかに大きい方を寄せると最小だよと言っている
307の計算が前提 >>311
2＊4+3＊5と 2＊5+3＊4を比べる時
Aの解説は
2＊4+3＊5の2と4が3、5よりそれぞれ小さい(
大きい)なら前者、そうじゃないなら後者だよって話
>
> 307の計算が前提 最近このスレって新参ばかりだな
寒色が程度の低い話をするばかりでちっとも面白くない >>312
そこまでは分かってるけど、そこから次の行の「よって、」以下にどう繋がってるのかが分からない
aibi+ajbj
はどう桁を交換しても作れないから関係なくない？ 暖色は分からなくても自力で考える力が高いからこんなところで質問しないんだよな
自分で高度な話題を振っかければ暖色も反応すると思うぞ arc154_c って文字列テクニックとかでもっと速くなりますかね？ 本質は文字列 S, T が与えられて、S を rotate して T を（連続とは限らない）部分列として含むようにできるか、かな？ 何も考えてないけど文字列アルゴが効くのは連続部分列系じゃないの 区間部分列だと遷移ベクトルを考えるのがDISCO!とかにあったけど……今回は種類数が多いから辛いんだよな
種類が多いならAとBの先頭を出現数が最も少ない文字で固定すれば少しは速くなりそうだが、誤差程度だろうし ウェーブレット木/行列って競プロでどれくらい使える？ >>321 2-SATより上、セグ木より下くらいの頻度で使える
正直言ってACLに匹敵する実用性がある 遅延セグ木はもう誰でも知ってそうなデータ構造と化してるけど、WMは有用性の割にまだそんなに広まってないよな ABC97 B Exponentialについて教えていただけませんか？
Python3です。
from math import sqrt
x = int(input())
ans = 1
for i in range(1,x+1):
if sqrt(i) % 1 == 0:
ans = i
print(ans)
これを提出するとtest4,6,7だけWAになります。
テストケースは検索したけど見つからず...。
よろしくお願いしますm(._.)m for文のインデントがおかしくなってますね(汗)
無視して下さい >>324
pが3以上の場合も考える必要があります sqrt(i)%1に思うことはあるけど、その前にまず誤読してないか？
試しにsqrt(i)%1==0なるiを全部出力させてサンプル1と比較してみなよ >>326
>>327
完全に勘違いしてました(汗)
ありがとうございます。 プログラムだかソフトウエアだか忘れたけど、ひろゆきみたいに上から目線で君臨しているやつまだいるの？
たかが一般人のくせになｗ しゃくとり法について質問
解答例の通りに実装すれば計算量がO(N)で済むと書いてるけど、解答例だとN-1回ループのfor文の中にwhile文が入ってるんだけど、これで本当に計算量がO(N)で済むの？
頭が悪すぎて解説読みこんでもわかんね
https://i.imgur.com/clPvzaA.jpg
https://i.imgur.com/7oJcUMF.jpg Ri＝nである場合、そもそも増やさないから全体の計算量はO(n)で済むんだね
頭が悪すぎてこの程度のことすら理解するのに時間がかかる まあそんなもんでしょ
どうせ無限時間必要とするから、1つずつ典型を学んでいけばいい
レッドコーダーでも問題文誤読したせいで問題解けないこともある 蟻本と螺旋本の電子版がセールで500円になってるの神すぎる
紙版しか持ってなかったから即ポチった 記憶違いでなければ蟻本ってとうの昔に更新しなくなったPKUに則ってたと思うんだけど、新しい版では書き換えられてたりするの？ これ見ると東大生でも大半が緑色以下なんだよな
参加者のレベルがあまりに高すぎてエリートでも灰～緑程度のレベルで燻ってる
これから、AtCoderに参入する人はこの事実を知っておいた方がいいわ
https://i.imgur.com/zfVNSBr.jpg 青より上までいけるのは東大生でも極わずか
1部の数学エリートしか楽しめない娯楽それがAtCoder
俺は恐ろしい世界に入り込んでしまったんだな… これのほうがいいか
しかも、これは1年半以上前のデータだからな
今は当時よりも参加者のレベルが上がってるから、東大生であっても緑まで行くのは相当苦戦するかも
Fラン大学とかだと茶色も無理なんじゃないか
https://docs.google.com/spreadsheets/u/0/d/1_rtU2geWnkZyOBYXyvPtcyn9GRfucd7GGFQqoGM5fZE/htmlview 東大生が多いのは事実だけど全員が競プロに本気出してるわけではなくて適当にやってる人や合わなくて緑以下で辞めるような人もカウントされちゃってるから競プロに取り組んだ時間も結構重要よ そうだよ
真面目にやって緑とかセンス無いから諦めたほうがいいよ ていうか競プロなんて役に立たないんだから、時間を注ぎ込んでないほうが賢くて偉い 前回茶色になれて、今回Dで解けた。
ようやくEの世界と対峙する事が出来そう。 だめだーdpどう使うのか思い付かん
70分お茶飲んでた Cは楽な方法思いつかなかったから
鬼のように条件縛りしたけど、あれで良かったのかよw 自分もFで1時間以上椅子を温めていた
ここ安定して解ければ黄色になれそうなんだけど二乗の木DPなんて知らなかったし経験が足りてない またCで誤解法でACしちゃったかも？
解説見ると条件3つあるのに
if文2個でダメ元で提出したらACしちゃった
ACLのDSUで入力してmergeして
条件2つだけ
if (d.groups().size() != 1) return false;
if (N - 1 != M) return false;
上記抜けたらYes
return true;
これって正しいですか？
ACしたのに自身が無い >>355
4 3
1 2
1 3
1 4
とかはNoだけど、それだとYesになるかな >>355
次数が3以上の頂点を含む木だとダメだから嘘解法では >>355
木だったらだめだな
というかこれ落とすテストケースないのか… >>355
解説の1つ目の例で間違いなのになんで通るのかw EとかはSAISしたあとにLCPテーブルとセグ木を組み合わせる例の典型知ってればすぐ思いつくし、知識ゲー感あるな あちゃー
また誤解法やらかしちゃいましたかね
ラッキーACの方が後でメンタル凹むのでWAにしてください
ダメ元とはいえテストケースで全部通ったから提出したけどやっぱり罠だったか C次数3以上の頂点を含む木のテストケースすら入ってないってガバガバすぎる >>362
ABCはいつも知識ゲーだぞ
例えばセグ木とかローリングハッシュとかをコンテスト中に自分で発明できるひとなんてほとんどいないし Gみたいに座圧とデータ構造組み合わせる問題は思い付いてから書ききるまでが長くてストレス貯まる Gみたいに座圧とデータ構造組み合わせる問題は思い付いてから書ききるまでが長くてストレス貯まる 他の解法何も理解してないけどEはTrieが一番楽だと思ってる Trieの方を先に思いついたがポインタアクセスの定数倍が怖くてやらなかった Eはソートすると両隣と比較するだけで済むけどTrie解法の方を知らない >>371
解説に載ってるケースだから落としたいに決まってる ワイもtrie木の存在を知らないまま再発明してた
もっと勉強しないとダメだな 今週は
将棋→atcoder→将棋→atcoderだけの休みw 今週は
将棋→atcoder→将棋→atcoderだけの休みw >>371
連結じゃないパターンとかはちゃんと入ってるのに解説の図にも載ってるようなシンプルな例外が含まれてないの謎だよね Exって小さい方から追加してワーシャルフロイド的にやればできるよなーって思ってそこから進まなかったけど、そのまんまなんだね
bitsetでの高速化という発想がいつも頭から抜けてしまう まあ次数の方の条件はあんまり見逃さないと思うけどな
自分も連結の判定拾えず1wa だった 参加者がミスりやすい連結判定ではあるけど、解説で必要十分条件を整理しているのにテストケースに反映されていないのを見るとうーんとなってしまう 極端なテストケースを含めてない問題って意外とあるのかな
過去問を埋めてたんだけど、想定解では平方根で計算量を抑えるパートがあったのに普通にそこを全探索して通ってしまった
具体的にどの問題かとは言ってないからアレだけど自分で極端な場合を試してTLEすることは確認してる C++なら通るってのは珍しくない
望ましいことではないけど大騒ぎするほどレアなことでもない ABCのC以下なら有り得るがD以上でそんなことあるか？ 昨日のExもbitset高速化が本質なところを、C++で愚直にO(N^3)やっても通るらしいし（勝手にコンパイラがベクトル化してくれてbitset高速化と等価な処理をしてくれる）、後半の問題でも非想定愚直解が通ることは普通にある そういうのは大体コンパイラが運良く賢い最適化を適用できたときだから、狙って出すのはそんなに簡単じゃない コンパイラの気持ちになればベクトル化効きそうなコード書くのはそんなムズくないと思う 他で類題が出たときにAtCoderはテストケースが弱いとよく言われている気がする このwriterのARC-A問題毎回めちゃくちゃ難しくない？
Bすぐ気づけたから一命を取り留めたけどAの場合分けでごちゃごちゃさせすぎてWA量産してたから初めの一時間くらいは絶望状態だった Aを未証明で通したけど解説見たら全然違うことやってたから自分の解法が正しいのか分からん Aはたしかに難しめだったけど、ARCで類題を見たことある気がする コンセプトだけならAよりCの方が簡単な気がする
Cは無限場合分けがキツいけど、天才的発想が要るタイプじゃない Aも天才って感じの問題じゃないけどな
ただ回文って頭壊れるよな Bがやたらと解きやすかったからAのやりにくさが際立ったのもある A問題diff1500超えは笑う ARC最高記録かな
実際AGCって言われても違和感無かった 前半も難しかったけど、任意色コーダーもお手上げのEFもすごい
500-500-700-900-1000↑-1000↑ぐらいの配点のAGCでも違和感がないね
ARCは定期的にこういう回が来る このまま開催が少ないと文句言われてるagc にすれば良かったよね TwitterのTLに昨日のABCの感想が混ざってるせいで、E問題F問題解けたみたいなツイートがたまに流れてきて驚く Twitterで解決しなかったのでここで質問
昨日のARC-Cを手元でテストケース生成する時、値域は1≦A_i≦4で十分？
重複順列を全部生成しなくてもこれで網羅できてると思うんだけど、証明に自信が持てない 解答の場合分けを全部網羅できるかって話ならまあできてそうじゃないか
偶数も奇数も種類数は3以上いらないはず
コンテストジャッジのテストケースとして十分かという話だと、微妙な嘘解法とかに弱そうな予感がするが コンテスト中に実験や検証の目的で手元でテストケースを生成するという話なら、そこまで条件絞れてる時点でもうテストケース生成要らんレベルで解けてるだろ感あるが 仮に無限個のテストケースを一瞬でジャッジできるとして、1≦A_i≦2e5で作った2e5^N通りのテストケースと1≦A_i≦4で作った4^N通りのテストケースは任意のコードに対して同じAC/WAの結果を返すという主張です 任意の、は流石に過激主張か(57が入力に含まれているとpanicするコードなんかは落とせない)
場合分け系解法なら常に同じになる、程度で 想定解の場合分けをするコードの出力なら一致する
しょうもない話をするが、57を見たら常にYesを出力も場合分け解法だと思うので、場合分け解法なら常に一致するとは限らない そりゃ想定解を書きゃ一致するだろ
そういう揚げ足を取って欲しい訳じゃないんだが まあ偶数が奇数の種類数が3以上ある場合に挙動が変わって不正解を吐き出すような嘘解法って特に思いつかんよな >>415
意図が不明瞭なんだが、要するにコンテスト中のテストケースとして十分か知りたいのか？
すなわち自然に生えてくる嘘解法を落とすには十分かみたいな
任意の場合分け系解法に対して、みたいな話なら一致しないコードをいくらでも構成できるから偽だが あれだわ、こっちで証明書くから正しいか正しくないかだけ教えて欲しい
今回の問題は、Aの各要素の偶奇を定めた時、どの二要素が交換可能かという関係が1位に定まる
この時にAをBに一致できるかという問題はソーティングネットワークであるから、0-1原理より二値のみ見れば正当性が判定できる
各要素の偶奇もいるから、結局{1, 2, 3, 4}の4元のみで場合分けの正当性が判定できる >>418
場合分けに偶奇いずれかの種類数が3以上のときに生じるような情報を使っている場合は、4元に置き換えた時点でYes/Noの出力が変わることがあるので偽なんじゃね
場合分けに使っていい情報をある程度制限すれば真になりそうだが まだ全然理解してないけどプログラムを入力からソーティングネットワークへの関数だと思ってる？ >>418
偶奇は要素に対する条件だからソーティングネットーワークは話が違う気がする
位置に対する条件だったらわかるけど プログラムは全ての(i,j), 1<=i<j<=Nに対し「最初位置iにあったものと位置jにあったものが交換可能」かを定め、それを元に判定を行うものであるという仮定がある？ 全然話についていけてないけど、場合分け系解法の定義がはっきりすればもうちょっと議論しやすくなりそう 多次元のデータを扱う過程でvectorだとMLEするのに全く同じサイズで代わりに生配列を使ったらメモリ制限余裕でクリアしたんだけど、これってvectorの方がより多くの情報を保持してるってこと？
軽く調べてみた感じvectorの各次元のサイズの順番次第でも変わってくるらしいんだけどもしかして生配列の方が地雷少なかったりする？ vectorは配列サイズより大きな領域を確保してpush_backに備えるから
push_backした時に現在のサイズじゃ足りないと二倍の大きさのメモリを確保してそこに既存データをコピーする 多分だけど、
二次元の配列を生配列でやるとメモリ上は連続に並ぶけど
vectorでやるとそうではないので、その分のロスはあると思う 要素数を保持するメンバ関数.size()も悪さに加担してそうだけど色々原因が絡んでそうだな
生配列って変数を要素数に使えないのと初期値に気をつける以外に何か注意すべき点あったかな vector<vector<T>>は多次元配列じゃなくてジャグ配列だよ ジャグ配列という言葉を覚えたてでドヤりたいのか知らんけどC++で区別する意味ねーぞ
そもそも配列じゃないし ？
現にパフォーマンスに差があるって話してんだから区別する意味あるに決まってる よく「C言語に多次元配列はない、あるのは配列の配列だけだ」なんて聞くけど、じゃあ「真の多次元配列」ってなんなのさ
a[1,2,3]みたいに所定の個数の添字を使わないとコンパイルエラーになるような配列とか？ 一般的な多次元配列というのはこれ
https://e-words.jp/w/%E5%A4%9A%E6%AC%A1%E5%85%83%E9%85%8D%E5%88%97.html
C言語で昔から多次元配列と呼ばれてたやつだ
ところがもう一種類の多次元配列を持つ言語が現れて区別の必要が出てきた
そのため片方を多次元配列、片方をジャグ配列と呼ぶようになった
ジャグ配列のジャグとはギザギザという意味で要素である各配列の要素数がバラバラという意味だな
C++の配列(vectorは配列に非ず)では区別の必要はない はえ～、じゃあジャグ配列ってのはいわゆるレトロニムだったのか
サンクス そうだね、レトロニムではある
C言語の初期から「配列へのポインタ」の配列を使うなんて当たり前だし
しかしメモリレイアウトがシーケンシャルになる多次元配列と、ポインタの配列は必要に応じて区別するもんだけど どこのメモリをどのように割り当てるかで用途やコードは変わるけどそれは特に「呼び分ける」必要はないってことだよ
他の言語のように文法から違うならともかく
たとえば二分木を配列にマップしてもそれは二分木だろ 全く何が言いたいのかわからん
int A[3][5]は多次元配列でジャグ配列（配列のポインタの配列）じゃないと思うが C++のvector<vector<T>>はジャグ配列であって、当然多次元配列としても使えるがパフォーマンスは落ちるよね？ってだけなんだがそんなに変か？
要素数が動的な多次元配列（に機能を絞ってパフォーマンスを追求したもの）はC++にはなくてだからこそmdspanが提案されたりしてる >>438
大丈夫か？
ポインタの配列の話なんか誰もしてないぞw
多次元配列は一種類しかないから区別の必要はないと書いたよな？ あ、そうかそうか
配列が第一級オブジェクトだと思ってるのかw
ちげーよw レッドコーダーの人は、プログラミング言語についても詳しい人ばかりですか？ 第一級オブジェクトじゃないと何が起きるの？
ポインタの配列をジャグ配列って呼ぶことにしていい？ 抽象的なデータ構造としての配列の話をしてるのにC/C++の配列と混同してないか？ 言語無関係な抽象的データ構造で多次元配列とジャグ配列を区別する意味なんてなおさら無いだろ
C/C++の話をしてるところにトンチンカンなこと言って割り込んできた言い訳がそれかよ 要件違うんだから区別する意味あるだろ
その調子だと配列もハッシュ関数がidなハッシュマップだから区別する必要ないとか言い出しそう 元の話って速度の話じゃなかったのか？
ジャグ配列か多次元配列かは明確に速度が変わるから、考える意味はあると思うぞ
あとAtCoderはvector<vector<int> >をジャグ配列と呼んでる https://atcoder.jp/contests/APG4b/tasks/APG4b_t 抽象的なデータ構造だそうだからどちらが速いかはその言語によるぞ 抽象的ってのは言語仕様に依存しない程度の意味じゃないんか
どの言語のジャグ配列も多次元配列より遅い、は真だと思うけど(もちろん多次元配列が無い言語はあるので、一次元配列で代用するものとして) >>454 検証結果マジか、シーケンシャルアクセスできるなら掛け算必要な方が遅いということかな
添字が範囲内なのかのassertなども含めると逆転しうるのか……
検証出してくれるのは助かる にしてもそもそもvector<vector<T>>をジャグ配列と呼ぶことに噛みつくこと自体がイミフじゃね？ >>458
なるほどな
こういうのがあるから速度比較は難しい >>454
流し読みしたけどこの記事クオリティ低いから鵜呑みにするのはちょっと早計かな
3x2と2x3とかいうクソ小さい行列で実験してなんの意味があんのかよくわからんかった どこにUnityでC#動かしてる競技プログラミングサイトがあんだよ
「速さを気にする言語じゃないから」じゃないとか知ったかぶりはやめよな >>462
それはそうだね、この記事だけじゃ微妙
でもまあ
"C# 多次元配列 ジャグ配列 速度"
とかでぐぐればいろんな検証結果出てくるし、いくつか見れば「多次元配列」は早いというわけじゃないのはなんとなくそれっぽいと思えるっしょ C#は速さ気にしまくってるけど多次元配列は誰も使ってないし、あえて高速化するならSpan<T>で1次元扱いしたらいいから多次元配列は永遠に遅そう 自演きっついなこのスレ
なんだろう黄色を騙る茶色無職が常駐してんのかな ワッチョイがｱｳｱｳｳｰSaで文体が単芝使いの奴ってD問題で間違いを指摘されて暴言吐いてかつ浮動小数点数の話でも自分の間違いを一向に認めなかった奴と同一人物っぽいんだけど、もうスレのテンプレにNG推奨として追加した方が良くない？
前まではこんな奴居なかったし だから無理矢理移住させると治安悪くなるって言ったのに 端末使い分けてるか飛行機飛ばしてるっぽいんだけど、単芝使う+煽り文体+(今回の件でどっちが間違ってるかは置いといて)自分の間違いを絶対に認めようとしないって時点で同一人物なんだよなあ 明らかに煽ることが目的のやつがいると思ったら個別にNGすればいいと思ってて、スレとして誰かをパージするようなことはしなくていいと思うんだよな
技術的な話に全く関係のないことを連投するやつが現れたらちょっと考える必要はあるが、全然まだそういうレベルじゃないだろ？ 議論になるなら良いんだけど、前例からもわかる通り間違ってることを堂々と発言した挙句に明白な根拠有りで誤りを指摘されても自分の誤りを認めず暴言を吐き始めるのが厄介だと思った
まあ今回の言い争いには直接絡んでないけどNGしとくわ また論破されるから追い出すってかっこ悪すぎない？w 前回で茶色になるようなレベルって自分で書き込んでるのにどこからそんな自信が湧いてくるのやら
それでいて寒色煽りしてるのも謎 論破されて自作自演で嘘の噂流すのかっこ悪すぎない？w このスレ、発言から青～黄が5人くらいは確定で居るからなぁ
某レッドコーダーも見てるっぽいし、下手な煽りは返り討ちにあう 返り討ちにあって追い出そうとするのかっこ悪すぎない？w 明日のABCはARCよりかあ
やっぱり企業コンオンサイト予選はARC-likeな問題で選抜したいという思想はありそうだね 中盤はいつもよりも難し目らしいからギリギリDが解けるかどうかみたいな層は明日厳しいかもね
キーエンスのD青EF黄程にはならないと思うけど 緑から水色の初心者から中級者の間の層が狩られそうね 「終盤は難しくない＝普段のABCと一緒」って意味だと仮定すると、中盤がARCで後ろはマニアック高度典型という、ただの昔の企業コンARCなんだよな
だったらU2800 ratedでもよくね？って思ってるけど、そこまですると初心者層が萎縮して参加しないかもしれなくて怖いんだろうか 企業コンは参加者数も稼がなきゃいけなくて大変だなって話 週1回コンテスト前の30分～1時間だけ過去問題Bを1～2問解いて本番するだけにしてから苦行ストレスがほとんどなくなりました
今日はC初見問題だけど自力で考えて30分台でC解けたので満足
C問題最速で45秒でACとかテンプレ用意しててコピペレベルなのでしょうか？
Dなんて一応毎回問題だけはチラ見するけど何やったって自力で解法思いつかないから
もう開き直って毎回Cまで解いていつか茶色に成れればいいや コンテスト中は順位表から読み取れる内容以外は他言に無用らしいから掲示板にはあんまり書かないほうがいいぞ D嘘解法ぽいけど閃いたと思って暇つぶしに提出したらAC3TLE40WA3ってことはそこそこいい線行ってたぽい？ ABCFの4完
やっぱりDに手を出さなきゃ良かった >>489
ヒントになった途端通報されるかもしれないので注意
今回の場合、試験中に「Dが難しい」と叫んでいると取られかねない >>489
コンテスト中にSNSとか5chにコンテストのこと書き込むのは真面目にやめた方がいいよ D問題で区間総和÷K=0で閃いたと思ったけど条件が足りなかったみたい C問題で当たり前のようにunion findとかが出てきてビビった
勉強せんとなあ 解説見たらやっぱり何やってもこんなのコンテスト中に解けないやってなりますわ
おとなしくCまでを確実に解く練習を毎週末するだけでいいや 先週もだけどC問題で出るグラフ問題はACLのDSUに慣れさせようとする作問者の意図を感じます
解説もACL使ったら軽いと露骨に明示されてたから多分普及させたいんだろうなと もう来週の問題も作成済みでACL使うグラフ問題シリーズが来週も出そう
とか言ってると来週はグラフ出すのやめたりするかな
ここ見てる？ unionfind、初中級のアルゴリズムの本にのってない気がする、atcoder高度すぎ 参加回数が規定数に満たないってことなんですが
今回ABCまで解けてレート380点とパフォーマンス７40点で差が360点くらいあるんですが
規定回数超えたら茶色に成れますかね？
茶色に成れたらもう満足なんですが C問題で下記のようなコードで提出してACだったのですが
解説と違ったのですが解法として合ってますか？
（事前にいつものACLのDSUで入力済みとして）
sum = 0;
foreach (g, d.groups()) { sum += g.size() - 1; }
cout << M - sum; あってる、もっというと以下でいい
auto g = uf.groups();
int ans = m - (n - g.size()); UnionFindは、中身の理解と計算量解析自体は簡単ではないかもしれないけど、ブラックボックス化して使う分にはとても単純だから、まずはそういうものだと思って把握しといて損はないよ Gはゼータ変換メビウス変換の要領でやれると思ったけど毎回頭がこんがらがる
いつかのARC-Dでもこういうゼータ変換メビウス変換の変種が出てた気がするけど、そのときもきつかった Eを最初セグ木でmin取ろうとしたらTLEして致命傷で済んだ >>509
ありがとうございます
また嘘解法だったかと不安でしたが安心出来ました
ただDは解説配信見てもさっぱりでした union find は「プログラミング・コンテスト・チャレンジブック、第2版、2012」に載っていたような？ 競プロ本じゃなくて一般的なアルゴリズム本には載ってなさそうではある >>515
セジウィック＆ウエイン
CLRS
浅野孝夫
の本に書いてありました。 >>515
Kleinberg & Tardosの本にも書いてありました。 ありがとう
よく考えたらクラスカル法をまともに実装すりゃセットで出てくるから普通の学術書でバンバン出てくるものか
すまん、適当なこと言ったわ 昨日のEx見てるがそれぞれのパーツはそんなに難しくなくても、コンテスト中に詰めるのは相当な情報処理能力要るなこれ
最上位は既に知ってる部分が多いから思考をショートカットして解けてる（部分問題はKUPCで既出）のか、初見でも化け物みたいな処理能力があるから解けるのか enumerative combinatoricsで式クソデカ数え上げの練習をしよう 信者では無くないか？
どっちについても炎上するから関わりたくない、が直接反応されたから返答はしたように見える
AtCoderユーザーは暇空寄りだから、どちらかと言うと暇空側の立場を取るのが正解だし
本当は無反応が最善のはずだから、リプ返した時点で暇空応援の気持ちはありそうだけどな ＞AtCoderユーザーは暇空寄り
そうなんだ…ショック chokudai定期的にいらんことに首突っ込むよな 最近やたらとイキってる陰謀論界隈の教祖様だろ
中立っていうならリプ返さないでほしい
心底気持ち悪い なんでミュートじゃなくてブロックするんやろなぁ。SNSの使い方下手すぎん 暇空応援公言は普通にショックだわ
あの界隈を胡散臭いと思わない感覚は怖い ABC232E Rook Pathなんだけど、
解説だと、ゴール(x2,y2)の位置で場合分けしてるんだけど、
スタートとの位置関係で分かれるんじゃないの？
シミュレーションしてみたらそんな挙動。
計算は同じになるんだろうけど ↓上級編がでますね。
アルゴリズム実技検定 公式テキスト［上級〜エキスパート編］
中村謙弘、ｔｓｕｔａｊ >>532
値が同じところで分けるとそうだけど、
多分解説は値が同じところで分けてるわけじゃなくて答えが計算しやすいように分割してるだけ
（集合内のfの和でgを定義してる）
このあたり確かに文章の流れがミスリーディングだね 公金の使われ方とか言って暇空は応援するのに
五輪談合で逮捕者出てる電通から金貰ってるのはいいの？
私女だけど男の人のダブスタ悲しい ロシアと強いつながりがある競技プログラミングコミュニティ ロシア批判に消極的に見えるのは
男子校理系的なキモさの極地って感じ >>535
今ホットなのは暇空の方だしなぁ
話題性のある方に言及するのは普通でしょ？ アルゴリズム実技検定 公式テキスト［上級〜エキスパート編］
中村謙弘、ｔｓｕｔａｊ
↑予約注文しました。 https://codeforces.com/gym/102978/problem/A
なんか、こういう総数は簡単なんだけどもうちょい細分化したものを数えたいときに新しい変数とかを導入するテクニック的な まあ情報増やす感じよね
自然数の代わりに、[n]_q = 1+q+...+q^(n-1)というqの多項式を考えみる
そうすると普段の数え上げで出てくる概念についてもq-類似というものを考えることができて、q-類似はオリジナルより細かい情報を持っている
例えば普通の階乗は順列の数え上げだけど、そのq-類似であるq-階乗[k]_q! = [k]_q [k-1]_q ... [1]_qは、r次の係数が転倒数rの順列の数え上げになっている
どうしてそうなるかは挿入DPの要領だね
1を代入する、つまり係数の総和を取ればオリジナルの階乗を復元できもする さらにq-二項係数というのもあって、binom(n, k)_q = [n]_q/([k]_q [n-k]_q)なんだけど、r次の係数が、r個の区別できない球をk個の区別できない箱に分ける（箱の容量は最大n-k個の球を収容可能）場合の数になってる
同じ意味だけど「grid上のpathで区切る領域の面積がrのpathの場合の数」の方が直感的にわかりやすいかな
https://scholarship.claremont.edu/cgi/viewcontent.cgi?article=1194&context=hmc_theses
すぐに役に立つ概念かわからないけど、数え上げの精密化と考えると面白い >>545
訂正：path→lattice path >>543
とかいろいろ書いておきながら普通にこれ俺にとって難しくて解答読んでも自信ない
まずVを無視した数の割り振りが、境界線の数え上げに対応してて、それぞれの境界線を適宜微妙にずらすことで非交差路の数え上げに帰着してLGV公式で解ける
さらにLGV公式で使う行列の各要素（すなわちある始点からある終点への行き方の数え上げ）を改造して、ある点pより右下を通過することが確定するところを通ったらx倍、点p自体を通ったら0倍みたいなルールでxの一次式を作り、Lagrange補間の要領で行列式の多項式を計算してV次の係数が答え的な感じ？
比較的典型性の高い数え上げを多項式で細かく分けて、係数から欲しい情報取り出すというのはまさにって感じに見える どちらかというと、q-二項係数がFq上n次元ベクトル空間からk次元部分空間を選ぶときの数え上げになってるって話の方で存在を認識してたな
係数を見るというより、何かを代入して情報を取り出すタイプ 実装には詳しくないが、(1-q^n)/(1-q)みたいな疎な多項式の除算にできることを利用して高速化できる感じなのか？ q-二項係数を分割の数え上げで解釈する話も部分ベクトル空間の数え上げで解釈する話も証明見たら見たらせやな感あるが、この2つのどこがどう対応づいているのかあんまよくわからんな またAGCやばそうな配点だ
endagorionってどんな問題出すんだ？ C++17が多数派だと思うのですが
C++20が未だに対応されない理由って何なのでしょうか？
本業が忙しすぎてそこまで手が回らないとか？
費用対効果が低くて恩恵を得られる人が少ないとか？
過去問まで対応させるとなると多すぎて単純に面倒だからとか？
上記全部当てはまりそうだから仕方ないか・・・ >>552
AtCoderなら、近いうちに言語アップデートが入るからそこで追加されるのでは？ >>553
そうなんですか？
知らなかったです
ありがとうございます
もしよろしければ言語アップデートのソース元ってありますか？ Bは面倒そうなので飛ばしてC
解法はすぐに思いついて実装に手間取って30分で提出したが
1つだけREになるコーナーケース？が分からずに時間切れ
残り15分くらいで一瞬Bやりかけたけて問題見たけど
CのREが分からないイライラを引きずって萎えたやる気出ないので
順位表見てたけどやっぱ今回のBCは難易度高かったぽい？
毎回こんなの1分2分で解いてる人いるけど
どんだけテンプレ用意してるんだろう
最速AC時間からすると自分のテンプレから探してコピペする時間としか思えない Eまで脳死で解いていく問題セットでしたね(´・ω・`) Convex hull trickEDPCで調べたばかりだったのに存在を忘れてた Fえらく簡単だなと思って実装してみたら想定の数倍厄介な問題だったな >>555
基本的にはみんな普通に問題文読んでコード書いてるだけだ
極まってる赤色のひとだとこれぐらいの考察速度でコードを書く
（まあ、このひとに限っては更にコードゴルフもしてるからかなり変態っぽいけど）
https://www.youtube.com/watch?v=su1QrfVkZK4 >>560
A問題ならまだ見て書くで分かる気がしますが
B,C問題をコピペじゃなくて1分,2分台で読んで書いてACって既に人間と思えないんですけど
上位様方達は凄いんですね Bは読解めんどくさいけど、レ点の存在を知ってればだいぶ思考節約できるし、ある程度上級者ならソラで書いても1, 2分で解けるんじゃないか 今回のGみたいな出現頻度低めの高度典型忘れた頃に出題されるから中々身に付かない Exは除原理で立式して母関数使って整理するときれいな除算になるのか
Exは結構な数の問題がFPS講座になっている気がする Bってグラフの説明いるの？
あれをまじめに読んじゃったせいで時間無駄にした 厳密に書くにはあれが一番なのかもしれないが、それはそれとして、やる操作に対して記述量が多すぎて驚く >>565
ありがとうございます
ヒントが冒頭って意味でしょうか？
ヒントじゃなくて頭が悪いってことならそのとおりなので異論はありません >>563
vectorの宣言だけどvst(N)じゃなくてvst(M)にすべきなんじゃないか
逆にRE1個で済むんだな >>570
＞＞あたま
のヒントで気づいて
それでACなりました 思い込みと言うかこんな些細なミスに気づかずに1時間半も悩んでてて1完でメンタル壊れますね
REが解決できなくてドツボにハマる典型だと思いますが
すぐにBに着手してればもしかしたら解けてたかと思うと残念です
今日はBを今から解いてみて寝ます 確かにF青、G黄ぐらいが理想ではあるけど、一色上振れぐらいはいいんじゃないかな
FもGも難問って感じはしなかったけどやっぱりあの場合分けはキツいのかな 来週またTOYOTAだからABCの難度壊されるのか
オンサイトの枠なんかARCで好きに争っといてくれ 昔の企業コンARCの問題と比較すると普通にトヨタはARCでいい気がするんだよな >>573
無事B問題30分ぐらいで解けました
予想通りACLのDSU使えました
3回連続は無いだろうと思ってたのに
やっぱこっち先にやればよかったトホホ AGCの配点5-8-8ってA問題から青〜黄色の激重セットになりそうだな >>554
AtCoderの言語アップデートに関して 2023年版
https://atcoder.jp/posts/966
です アップデート自体がいつになるかはわかりません… >>579
ありがとうございます
丁度今さらっとシート見終わってここに戻って来たとこでした アプデ前後にC++20で使える便利情報などが出回りそう >>549
そうだね、1-q^nは性質がよくてありがたい
たとえばq-二項係数なんかはbinom(n,r)_q = Π_{i=1}^{r} ((1-q^(n-i))/(1-q^i))と表せてlogを取ると
log binom(n,r)_q = Σ_{i=1}^{r} log (1-q^(n-i)) - Σ_{i=1}^{r} log (1-q^i)
なわけだけど、log (1-q^i) = - Σ_{k=1} q^ik / k（ここで疎であることが効く）を利用し、
log binom(n,r)_qをN次まで求めるのならばO(NlogN)で求められる（調和級数）
binom(n,r)_q = exp(log binom(n,r)_q)もexp取る操作がNewton法でO(NlogN)でできて、最終的にはO(NlogN) (1-q^n)/(1-q)で定義されたq-数の積で表されるようなものならこの方針でほぼ対応できるんじゃないかな >>581
https://qiita.com/Chippppp/items/620d2e5229f5c7e93f0c
もうまとめてくれてる人いるね
競プロでよくお世話になりそうなのはnumbers,bit,autoあたりかなの印象 言語アプデでGoとか相当良くなるんじゃないかな
Generics使えるようになるし 例のQiita記事覗いたけど20代の主婦ってワードでちょっとびっくりしちゃった 周りにそういう生き方してる人いないので >>586
最後のはもろにq=2のq-二項係数だね
Π_{i=0}^{N-1} (2^M-2^i)/Π_{i=0}^{N-1} (2^N-2^i)
= Π_{i=1}^{N} (1-2^(M-i+1))/(1-2^i)
= binom(M, N)_2
丁度>>548に書いてある話かな、q=2以外のF_qでも同じような議論ができる
問題の誘導がお手本のようなq-二項係数の導出方法になっていると思う
あとすまん、>>582は指数ミスってるね、 Π_{i=1}^{r} ((1-q^(n-i+1))/(1-q^i))が正しい >>584
それ見てatcoderはC++20対応まだなのかなって思ったんですよね
以前C++やる前にpython触ってたのでrangeなどの配列操作に慣れてたので
なんでC++こんな面倒なんだろうって思ってました
自分はC++20のrangeが便利そうだなって思ってます
テンプレで自作関数用意しちゃえばなんでも大差ないんでしょうけど
やっぱSTLや標準機能で動いてるって安心ですよね 今日のwriterロシアの人みたいだけどなんでatcoderでの出題なのかな 実験したらパスカルの三角形が出てきたから色々調べて何とかlucasの定理まで辿り着けたんだけどこれA問題で知識として要求されるレベルなのか Lucasって言うと大袈裟に聞こえるけど再帰的な構造を見つけてくださいねってだけじゃね？ >>589
競プロだとコード長制限の観点からも嬉しいですね
テンプレもりもり書いてると結構すぐ超えちゃうので >>590
海外でも難問と言えばAGCという評判だから、難しいセットをAGCに投稿しようと思う外国人はいると思う こういう人を見ると凄く勿体無く感じる
何故、中卒なのかは分からないけど1年ちょいで青コーダーになれるだけの地頭があるなら、勉強をすれば東大や京大にだって余裕で受かるだろうに
【AtCoder】中卒の主婦が青コーダーになったおはなし【競技プログラミング】
https://qiita.com/mayocorn/items/4edff486428240864808 どういう学歴を辿るかは本人の自由だろうし、余計なお世話ではないか >>588
あーこれだこれ
俺が知ったのはABCのEx問題かなんかだったが、解説でこのゆきこの問題と同じような感じで導出してた覚え 東大生が～とか中卒が～とか何を話すにもわざわざ学歴を書いてイキらなきゃいいだけだぞ ガチのフルコミットする奴(子なし主婦やニート)が増えれば青＝東大の相場は崩れる気がする
まあ子供育てる予定があって自分が東大レベルの学力を狙える根拠が1つでもあるならとりあえずやってみる、というのは子育て戦略として面白いし普通に優良 青=東大なんて言ってるの学歴厨しかおらんよ
マ板のゴミみたいな文化をこっちに持ち込むな 凄いのは凄いって言えばいいのに他所から「勿体ない」って言うのは傲慢よ ABCの3完が精一杯でBやCが解けないこともたまにある灰色なのですが
ARCって参加して0完でもパフォ少し出ることあるから参加したほうが良いって本当ですか？
ARCのAすら解けないから毎回参加してなかったのですが
なんかスコア稼ぎみたいでズルっぽいので躊躇するけど
もし本当なら0完参加もありかも？ 何もせず稼げるとしてそれが嬉しいなら自分でやってみたらいんじゃね 某所で見かけた問題（どこの問題かは規約の関係で言えない）なんだけど、いくら考えてもわかんなかったから誰か教えてほすぃ
N 個の正整数 L_1 ～ L_N が与えられる。ここで以下の二つの「操作」から好きな方を選ぶことを繰り返す。
・L の要素を任意に一つ選び、X 減らす。
・L の要素を任意に Y 個選び、それぞれ 1 減らす。
L の全ての要素を 0 以下にするには最低何回の操作が必要か？
1 <= N <= 100000
1 <= L_i <= 100000
1 <= X <= 100000
1 <= Y <= N
（制約条件はこれであってるはずだけどもし記憶違いだったらゴメン） 出展不明の問題には解答してはいけません
不正に荷担することになるかもしれません それがどこの問題か知ってるけどその問題を公開することは許されてるわけ？許されててもダメだと思うけど マジか、伏せとけば大丈夫かと思ったわ
じゃあ諦めるわ かなりムズい気がするな
このスレではどのみち解けなさそう そんなに難しくはないけど、確かに解答したくはないな……
自力で頑張ってくれ Lは昇順にソート済みとする
まず後者の操作だけ考えるとmax(L_N,ceil((L_1+...+L_N)/Y))が下界で実は達成可能（この値は1回の操作で必ず1以上減らせる）
となると前者の操作は値の大きい方からやるべきで前者の操作回数を全探索することにすると二乗logにはなるがこの先がわからん >>618
シミュレーションの際に同じ値はまとめれば毎回最大値が1以上減るからステップ数抑えられるか
その間の算数はk個に操作するとして
k+max(m,ceil((s-x*k)/Y))
という式の最小化
面倒だから雰囲気だけだけど多分最小と最大とmaxの中身が丁度等しくなるとこくらいを調べれば十分なはず >>606
レーティングって長期的推移でみるものだから高々1個実力外で稼げたものは所詮あぶく銭にすぎないしパフォ目的ならオススメはしないかな
チャレンジしたい！って心意気ならすご〜くいいと思います >>622
ARC過去問覗いて見てそっ閉じしました
問題文や解説すらさっぱり理解出来ないので
せめてA問題が理解出来るくらいまでは参加は諦めます Cまではとっつきやすかったね
chineristさんの回だからまた相当な難問が来るかと恐れていたけど B問題は実家DP的ななにかを予想して遷移考えたけど、思ったより普通の算数で解けたな
Cは制約がゆるすぎて逆に解きにくかった
こんなこと言うと競プロに過学習してるっぽくてよくないんだが >>624
見たぞ2
少なくとも3人factorioスレ見てるやつが居るな 寝起きでARCのA問題見たらちょっと閃いた気がしたので
20分くらいですぐにサンプルACしたので提出したら見事にWAでしたｗ
流石にARCだからコーナーケースが仕込まれてるとは思いましたが
考えても何も思いつかないのですぐに解説見たけど理解するのに1時間くらい掛かりました
多分本番やってたらWAにドはまりしてストレスでメンタル壊れてたと思うので
精神衛生的に不参加で良かったです
最速提出で2分台の方のコード2つ見ましたが
まるでコーナーケースを知ってるかのようなコードでしたね
問題を読んでコーナーケースまで把握したコードを2分台で提出してACするってことは
典型問題として類題知ってるってことでしょうか？
本当に初見で直感で2分台なら凄すぎます
でも5分以内ACも20人くらいいるからわかる人には分かるのかな 2分はともかく、30分かけて良いなら解けなきゃダメだと思うよ
長さ15くらいまでのテストケース全生成は幅優先探索やるだけABC-Cくらいの難易度なので、これを作って手元で確かめれば条件なんて自明 想像しているようなそっくりな問題を解いたことがあるみたいな話ではないけど（多分上位層は初見でも2分で解ける）、何個かの要素に分解できるところはあるかな
・偶奇に注目、二つ裏返すということは1は偶数個じゃなきゃダメ
・自明な下界を考える、2つ以上離れた1のペアを作れれば達成できる
・1が2個のときはコーナーケースっぽい、特に小さいケースについてはなるべく注意した方がいい
こういうのをできる人は無意識に一瞬でやってるから、何をいまさら言語化しているんだって感じだろうけど ある意味ARC典型みたいなところがあるかな
Cも自明な下界を考える問題だったし、Bは貪欲にある数まで下から埋めたあと分配する問題で、賢い筋を一つ見つけて他の筋を枝刈りするタイプの問題が多い AはARC-Aに置かれてると条件は基本的にシンプルになるけどたまに場合分けを要求されるみたいな雰囲気を感じ取れる(いつかのこどふぉで全く同じコーナーケースに注意すべき問題もあった)し、Bも条件の厳しいものからあらかじめ決めておいて残りは重複組み合わせ等で簡単に処理するっていう考え方をARCで何回か既に見たからARC典型みたいなのは問題を解き進めてるうちに身につくと思う
Aのパリティとか不変量とか上界下界に注目するみたいな典型考察も含めて(鉄則本とかにも書かれてるくらい典型だからもう既に知ってる人の方が多そうだけど) >>634
貴重な情報ありがとうございます
ARC-Aクラスの難易度はまだ無理ですが
ABC-Cならなんとか解けることもあるので
＞＞問題を解き進めてるうちに身につく
ことを信じて自力で解ける範囲で少しづつやってみます 緑だけどARCは不出場になった、青以上じゃないと時間の無駄になる気が 昨日のC、類以度いくつ達成できそうかは手元で実験してすぐ分かったけど、
すべてのケースで条件満たす構築が結局コンテスト中にできなかった
どうやって思いつくのあれ 類以度が2以上になるのはどういうときかを考えたら思い付いた パスの場合1通りしか答えないからその理由考えて適当に一般化 パス上でオリジナルの数字とPで変換して出てくる数字で被りがあるとうざそう→適当に木を二分割して移し替えればよくね？→頂点数の偏りが少ない分割がほしいから重心を使う
パス上でオリジナルの数字とペアとPで変換して出てくる数字のペアの相対的な前後関係が一致してるとうざそう→重心からの位置関係がオリジナルと反転してればよくね？
想定解はちゃんと読んでない 400点のARC-Aは厳しい問題な可能性が高いな
なんなら500点のARC-Bより人によってはとっつきにくい
300点のARC-Aはそこまで異常問題ではないことが多いはず
ABC-Cよりはずっとムズいけど Eまで早解き出来てFもO(N)で求められる式の導出までは出来たのにそこからの式変形がダメだった 勿体無い Gは貪欲でよさそうなことにさえ気付ければ実装も楽でかなり解きやすいな Fもいわゆる自明な上界問題っぽいし、今回も結構ARCチックだった
地味にDもこの位置では難しいのかも？と思ったけど結構みんな解けてるね Gの貪欲が証明できん
これしかないだろと思って投げたから通りはしたが 俺も証明してない
とりあえず、深さ2ぐらいまでf(x,n)（n個の部分木と接続したままxを作るときの最小コスト）みたいなのを考えたらnがなるべく小さいほうがいいことに気付いて、またxで単調減少しそうだから、どうせ親にも性質が伝播するんだろうなあみたいな考えでやった F非想定解とはいえ畳み込みやらFPSやらをやればO(N)の式を高速化出来たっぽいしちゃんと履修すべきだったな
自分は普段はFくらいまでしか解けないからまだ要求されないもんだと思って後回しにしてたけどこういう時に殴れないの勿体ない DのサンプルだけACしたけど
そりゃ提出しても愚直解だとTLEですよね
解説見たけどこんな条件気づける気がしない
考え方の方向性は間違ってないけどここまでが自力の限界ぽい 知識を取り入れてABCでレート上げるのはARC/AGCでレート上げるより楽なので、どんどん高度な知識を取り入れていいと思うな >>652
Dは典型ではあるからこれを機に知っておくといいと思うよ
(N/GCD(N,D))*Dで初めてNで割ったときあまり0のところに戻ってくる
こういう操作はかなり頻出だと思う OEIS使う裏技は知ってたけどwolfram alpha使う裏技もあるんだな
wolfram alpha の計算式にはガンマ関数とかsqrt(pi)が出てきたから自分で更に式変形する必要はあるけど今度から使えそうな場面では試してみよう ありがとうございます
解説見ても頭に入ってこないというか難解過ぎて咀嚼出来ない？ので
時間のある時に落ち着いてじっくり考察してみます D、解説が難しいし何の役にも立たないので理解する気力がわかない・・・ wolfram alphaを使うプレースタイルだとΓ(1/2) = √πみたいな知識も役に立つのかな
総合格闘技感があって面白い Dは例えばN = 15, D = 6としよう
〇××××××××××××××
一旦、x+1に移るルールを無視して、4移動してマーキングするというルールで考える
〇×××××〇××××××××
〇×××××〇×××××〇××
〇××〇××〇×××××〇××
〇××〇××〇××〇××〇××
〇××〇××〇××〇××〇××
〇××〇××〇××〇××〇××
と、間隔3の場所を延々と巡ることになる
NとDが他の値でも似たようなことが起きて、この間隔が実はGCD(N,D)で簡単に出せる >>659
ミス、4移動じゃなくて6移動
で、実際のルールでは、マーキング済みのところについたら1ズレるわけだけど
実はいつも最初は0に戻ってくることが分かって、
〇〇×〇××〇××〇××〇××
って感じ
上のと同じ動き方で1と間隔3で離れている場所が全部埋まる
〇〇×〇〇×〇〇×〇〇×〇〇×
全部埋まった後に1に戻ってきて今度は2に移って同じことをする 何の役に立つかというと、直接的に役に立つ気はしなくて、頭の体操感あるかなあ
でもこういう比較的複雑ではない方のアルゴリズムに慣れておくと、複雑なアルゴリズムを頭の中ですぐイメージできるような気がするね Dのax-by=0みたいな式を立てた上でgcd(a,b)で全体を割ることで互いに素であることが利用できるようになって一般解が求まる、みたいなのはABCのD、Eくらいで何回も出題されてるだけでなく受験数学でも典型ではありそう 例えば今回のEまではパターンマッチングで瞬殺だけどそれだと寒色止まりだしつまりはそういうことだ >>661
あ、すまん、文章のパースミスってて、D問題が何の役にも立たない話かと思った
解説で理解できないって話ね Gも貪欲でいいという点で確かにARCっぽいのかな？ 微積分も知らずに青まで行ける方がヘンだと思うので特殊関数も出すべきじゃ >>659
分かりやすい解説ありがとうございます
こういう図解が解説に無い時に
解説の文章にある数式（今回だとgcd(n,d)など）から
自力で何をしているのかシミュレーションを想像するまで辿り着けないんですよね
時々図解がある解説見るとスッと頭に入ることあるのでそういう時は助かります
単純に競プロや難易度に必要な基礎学力や経験が足りてないんだとは思います 過去問題だとほぼ解説動画あるので大体解説動画見てますね Dは@kyopro_friends氏がtwitterに図説を上げてるよ
あと解説放送も今やってるよ
最近はコンテスト翌日ぐらいにやってることが多い >>669
ありがとうございます
＞＞最近はコンテスト翌日ぐらいにやってることが多い
それは知りませんでした
お忙しいので動画無いのかなとか思ってました
あと@kyopro_friends氏さんってatcoder内部の方ですか？
やっとAB問題埋め全完了して
C問題を順番にやろうと思ったけどテーマがバラバラなので集中出来ないと思ったので
鉄則本を少しづつ進めつつそのテーマに沿ったtagに集中するようにしたら
勉強がやりやすくなった気がします
ただ時間が中々取れないので週末だけだと覚えたと思ってたこともすぐに忘れてしまう
生まれつき記憶力のある人が羨ましい フレンズさんは作問バイトの一人のはず
内部の人ではないけど作問には関わってる バイトも雇用契約を結んでる従業員なんだから、立派な内部のひとだろ
バイトを外部のひと扱いにしたら世の中が大変なことになるぞ 必要なのはAIのエンジニアであって、競プロerなんて時代遅れだよ
今後は機械学習を開発する力を面接でも重視する
そういう方針にするからこそレガシーエンジニアのレイオフを思い切ってやれてる chatGTPに使われてるtransfomerは全く教プロと関係ない。
強化学習はヒューリスティックで活用できる人がいるかもくらいで、ノーマルコンテストには縁がない。 >>671
やはりそうでしたか
解説動画が出る前に要点がまとめられていて図解があって分かりやすくて良いですね
これ見てすぐに理解できないならまだその問題を解くレベルに達していないと判断しやすいです GCJが無くなるってことはどういうことなんでしょうか？
Googleが教プロは将来的に継続する程の費用対効果が得られないと判断したという解釈とか？
上位入賞者に米国人がいなくて海外勢特に中国人だらけだから面白くないとか？
ChatGPTに対抗する為にコストやリソースをそっちに集中したいとか？ すべてありえそうだけど最大の理由は「そもそも採用に力を入れていない」でしょうね
レイオフしまくってるし >>679
なるほどですね
昨年からだと世界的に数十万人レイオフですか
上位数%の優秀な人しかいらないってことなのかな コロナ禍にIT投資が過熱して採り過ぎちゃったし
いまは急に市況が悪くなって人件費と今後しばらくのリターンが見合わないから、解雇するんすよ
日本にいるとそれほど意識しないかもしれないけど
世界的にはこれから長い長い不景気に突入する空気感 寂しいけどGoogleがもう普通に兢プロに価値見出してないだけだと思うよ フレームワークとライブラリが充実してきたので
あまりレベルの高い仕事はなくなってきたという感じか ARCギャンブル初参加して約50分くらいでまぐれのA解けてラッキー
最速の人1分20秒と毎度のことながら驚愕
Bも行けそうかと手を付けたけどやはり難解過ぎて頭から湯気が出そう
残り時間も無いし解法も思いつかないので順位表見てたら
B飛ばしてCやってる人が多かったから多分Bは考えて解くのは難しいのだろう
Cも覗いてみたけど典型のテンプレ持っていれば解けるんだろうな
準備してなかったけど迷路探索のテンプレで
全探索してY隣接の最大値更新して間に合うのかな
でも流石にARCだから高速化を考えないと解けないようになってるのかな
時間切れまで暇つぶしの感想書いてみた C、Bよりも簡単だった気がする(Bは罠が多すぎてWA複数回踏んだ)
Cの上位互換みたいな問題が数ヶ月前のABC-Gで出題されてたしそれ思い出したらすぐだった 普段のARCと比べると解きやすいが、AとBはコーナーケース踏んで死んだ Cの解法は典型的な思考法ではあるが、典型のテンプレ持ってるから解けるみたいな話じゃないぞ >>687
おっしゃる通りでございますね
解説見て無理だと悟りました
これはどんなに勉強しても理解出来るレベルに達する内容じゃないです
解説見て理解出来ないんだから本番で思いつくはずがない やっと入茶出来たみたいです
まぐれARC1完で+60以上出てラッキー
直近がABC3完でも+5前後とかだったからびっくり
なんかもう入茶出来たから満足しちゃった writerの人の印象から勝手にグラフアルゴリズムや最適化回になるかと思ったけど、数え上げメイン回だった
Fがそういうものなのかな？ >>691
おめでとう
典型パターンに習熟していないうちはARCの方がパフォーマンスが跳ねやすいと思う 鬼のように数え上げを出してくる某writer以外は出題分野そんな偏らない気がする
なんとなく個性は見えるけど >>693
ありがとうございます
まぐれギャンブルで貰った+60なので
ABCずっと参加してC落としたりすればすぐに適正に収束すると思いますので
400切らないように頑張ります >>695
今日のA解けたんならABC-Cは慣れれば安定して解けるようになると思う Bの全てXかつK=0のケースが3つも入ってるっぽいんだけど注意力勝負すぎるしK>=1でも良かっただろとは思う
全てXとYを例外とさせるのはまだわかるけど >>697
ありがとうございます
色々な勉強法あると思いますがマイペースが大事ぽいので
ストレスにならない程度に気長にコツコツやってみます 前半はコーナーケースを詰める力そのものを聞いてるんだろ、それ無かったらやるだけだし
自分もBは4ペナしたけど、この問題のコンセプト自体は否定しないぞ
好きか嫌いかなら嫌いだが シンプルな問題設定と非自明なコーナーケース、もはやARC典型 2、3分でスモールテストケースでの愚直実験一通り回せるぐらいの腕力が欲しいところだな ABC3完は出来ましたがみんなAC速すぎてパフォーマンスが出ないですね
参加してる人のレベルが高いというか
諦めて参加しなくなった人が多いのかな
参加人数も1万人いた頃に比べたら今アクティブ7千人弱くらいだし
Dって過去問か他コンステストで類題ありましたか？
C飛ばしてD速い段階でACしてるのにその人達がC解けないって意味が分からないから
もしかしたら有名な典型問題だったのかなと Fまでの早解きゲーになっちゃったけどF1100人近くも通すもんなんだな
下振れた時が怖いしこれくらいの正答数のG、EXなら解ける域に早く達したい Exでこんなにきれいに重心分解がそのまま出るとは意外だった Gの方が考察の難易度的に難しいと思うけど、重心分解は知識レベルとしては高度という判断なのかな 今回のFはEと同じくらいの難易度だな
500点同士と600点同士で同程度の難易度の珍しいコンテスト >>704
Dはかなり典型的なDPの問題だから類題はたくさんあるけど、Cより解きやすくなるってことはない気がするかなあ
まあでも問題の相性はあるからね こんなん重心分解でしかないやろで投げたけど、ちゃんと証明してなかったな >>709
そうなんですね
DPはチラ見したことありますが数問やって全く理解出来なかったので保留してます
まだ累積和とか二分探索すらよく分からないので鉄則本が全然進まない状態です
気長に理解できそうなとこからやってみます xorやandやorの相互変換もたまに効く典型の印象
あと1bitの場合andが普通の積と一緒になるのも畳み込みと併用することを考えるとありがたいね >>711
EDPCというコンテストの一番簡単なやつから理解していくのがいいかな
DPは慣れるまでが結構難しくて、慣れたらABCだとそんなに頭使わなくて済むようになる D問題最初誤読して「全てのカードの表面に書かれてる数が異なる」って思って一瞬焦ったけどこの場合も解けたりする？既出っぽい気もするけど >>713
ありがとうございます
今やりかけのもの終わったらまた少しDP覗いてみます >>715
とりあえずグラフを考えて、カードをA_iとB_iをつなぐ辺とみなす
このグラフの各連結成分を見て、なもり木なら閉路部分の割当で2通り、木になってるんなら木DPでうまく数え上げて、それ以外は0通りみたいな感じにして、総積を取る感じか？
なんか既出感がすごいな >>717
カードの表裏をグラフの辺に帰着させて連結成分ごとに頑張るみたいな考え方で確かに出来そうだし典型的な考え方な気もするからこの設定の場合もABC-E、Fくらいに置いてあれば違和感無いな
今回はABC-Dだったからすぐ誤読に気づけたけど Fで出て青diffのどこかって雰囲気の問題に見える DP練習問題などいくつか試してみましたがほとんど理解出来ませんでした
シンプルな典型問題を解説写経ACするだけの繰り返しになっていて
初見の問題を見る都度解法が全く思いつかないしDPを全く組めません
コピペしても通るような典型くらいしかAC出来ませんので
本番初見問題では役に立たないと思います
EDPCは解説の入力が省略されていたり
写経してもDPや入力の配列の添字が分からずその間違いでWAやRE多発してしまいます
解説をコピペしても通らないものもあってかなり時間ロスしました
アルゴ式は導入問題くらいは図解も毎回あって分かるのですが
応用問題になると解説が概要とコードだけなので何故そうなるのかさっぱり理解出来ませんでした
多分相当長いこと典型をやり続けてひたすら慣れるしか無いのでしょうが
時間対効果というか達成感が全く無くストレスが貯まる一方でモチベが続かないので
やはりDPは後回しにすることにします
DPが理解できずに苦労したとか覚えるの大変とは聞いていましたが
やってみてそのとおりだと痛感しました 解説を見ても理解できないDP練習問題ってなんだ？気になる 「判りませんでした。私は頭が悪いです。わーんわーんわん」って泣き言いう前に分からないとことか問題を貼ろう 多分初めのうちは、どういう時にDPを使ったら良いのか分からないって感じだと思うんだけど、
自分は昔「2^nの全探索が無理ならDP」って覚えた(最近だとABC291Dとかもこれ 他にもたくさんあると思う)
2^nの全探索の処理を考えたら、添字に何持たせたら良いのか出てくる気がする
bitDPとか区間DPなどの○○DPは初めのうちにやると混乱するから、まずは↑を出来るようにすると良いと思う
あと、dp配列の定義をきちんと決めることが大事で、ふわふわしたままコードを書くと当然上手くいかない
例えば「dp[i][j]: [0, i)でj個選んだ時の最大値」みたいにコードを書く前にきちんと決める
(dp[i]は「[0, i](閉区間)の答え」とするよりも「[0, i)(開区間)の答え」とした方がコードが綺麗になることが多い)
後は問題をたくさん解けば慣れるはず DPは、状態をまとめて管理したり、操作した結果部分問題に帰着するって考えるとわかりやすいと思う
たとえばそれぞれについて選ぶか選ばないかで 2^N 通りあると、選ぶ・選ばないを決めると 2 つの新しい部分問題に分かれて、
その結果を合成する必要があるけど、結局見るべき「状態」の種類は少ないからメモ化して突破できる～って感じ
添字はfor文の端っこを意識するとバグりにくくなると思う EDPCはHがクソ簡単だからそこから始めるのも手だと思う
部分問題の合成結果が最終的な答えになるって感覚がわかりやすいし >>726
EDPCだとA～Iまで試してみて自力で解けたのはCとHの2問だけでした
他の練習問題などでやった記憶があってそれをコピペしたら動いたってだけでした
なので何故そのようなDPを組んで正解が出るのか理解してるとは言えない状態です
つまりEDPCほぼ全てで解説を見ても理解できないということです
>>728-730
丁寧なアドバイスありがとうございます せっかく丁寧なアドバイス頂いていて恐縮なのですが
NGして無視してるとは言えどうしても目に入ってしまう非人間的な誹謗中傷もストレスになってますし
自分は頭が悪くて理解できないこと自体がストレスになっているので
DP含めて競プロ全般理解出来ないものは素直に諦めることにします
それでも解けそうで解けないものが解けた時は嬉しかったり
分かる範囲のものを勉強している時は楽しいので
マイペースで出来るものだけでも少しづつ試してみます
あと知人が誹謗中傷で亡くなっています
昨今のニュースなどでも誹謗中傷で亡くなる方も多いと見聞きします
誹謗中傷してる方は軽い気晴らしのつもりなのでしょうが
間接的に殺人に加担してることを理解して欲しいです このカスなに被害者ぶってんだろね
自分が荒らしと自覚してないんだな 喧嘩するなって
ここは競プロスレだろう？
競プロの話だけしようや このスレの荒らしは高度アルゴリズム関連を一切呟かず、延々と他者を下げるから分かりやすいのよな
個人的にはDPは漸化式、が高校数学の延長になって一番分かりやすかった、配る方が立式できないのがネックだけど……
貰う方なら、例えばEDPC-Bならdp(0)=0, dp(i)=∑[j=max(0, i-K), i-1] dp(j)+|h_i-h_j|と書けば後はコードにするだけだし 貰うってf(x)をaだけ平行移動するとf(x-a)的な添字の難しさを感じる 自分も「貰うDP+累積和」よりも「配るDP+imos法」の方が添字ミス減る気がする 俺はプログラマだから、DPは順番が違うだけでメモ化再帰とほぼ同じ、ってのが最初にしっくりきたな
関数型言語をやってると再帰はごくごく当たり前に理解できてるからね
まあ漸化式だとか再帰だとかいろんなイメージ付けをしていくことでDPへの理解が深まっていろんなのが解けるようになっていくもんだと思うわ 俺も再帰でシミュレーションすれば答出るけど時間足りないって時に
配列に答置いとけばいいんだっていうのが最初だったな 自分は更新順序とか何の値が既に確定してなくちゃいけないかとかを考えるのがだいぶしっくり来たかな 基本は漸化式(特に受験数学の確率漸化式)みたいな気持ちだけど更新順序が非自明な時はメモ化再帰でやると楽みたいな EDPCで初見で解ける問題があるだけ上等じゃねえの
ただ、解説読んで理解できないのは今後あらゆる問題で差し支えるから、それはどうにかした方がいいな
まずEまでは理解できるようにした方がいい vscodeがバグってて何も出来ない
急になんでだろ 幾何が分からなさすぎてExに逃げてしまった、競プロ脳…… Cは典型でしょうか？
典型だとして何というジャンルになるのでしょうか？数学の典型？
これ知らずに初見で考えてわかる人凄いですね 結局6完
久しぶりの幾何でπをcos(-1)とかしてて時間ロス Gみたいな細かい要素はそんなに難しくないけど複合してめんどくさくなってるタイプのDP好き >>751
何か二つの積がN以下みたいな条件の時に、片方は√Nまでしか探索しなくて済むというのはかなり頻出の典型だよ Eは推移閉包の問題だったけど、これに関連する発展的な話題で思い出すのはDilworthの定理かな
他には何かあったっけ C問題、手元で動かしてみたら明らかに2秒越えてるのにダメ元で提出してみたら500msで通った A * Bの結果を数え上げておくとN - (A * B)を利用してすぐ答えがでるからそう解いた 今回のDiff体感よりも0.5〜1色低いくらいな気がするんだけどやっぱり環境が整ってきて参加者の実力がインフレしてるのかな 挫折して離れる人がいて
残って実力が伸びる人がいるので
どんどん濃度が濃くなってる気がします
新規はすぐに離脱して強い人しか残らないスパイラルみたいな感じ？ ぶっちゃけそれはあるよね
新規の人が来ないとある色に上がる難易度が上がっていくと思う
ただ、現状のABCだったらまだ時間を十分にかければ特殊な才能がなくてもレートを上げていけるゲームではあるかな？ うわあ～
AB2完で灰色に降格ｗｗ
vscodeバグって40分ロスしたとはいえキツイですね
時間あってもこの問題じゃ解法思いついてないか
まぁARCのラッキーボーナス+60貰ってたのでこれが適正帯ということでしょう
一瞬でも茶色になって茶色の実力があると勘違いした自分が恥ずかしいです
毎回ABC3完でも+5前後なので
たまにC落としてAB2完でガクっと削られることを繰り返すようなペースだと
一進一退で茶色に成れないかもしれない >>764
灰色→茶色は努力でなんとかなると信じてやってますが
それすら厳しいかもしれないんじゃないかなと思い始めています そんな卑屈になることはないと思うけど、コーディング環境とかの問題は再発防止して平均的なレートを上げていこう ＞＞再発防止
IntelliSenseが効かなくなって何度再起動しても数分後にエラー吐いてPC暴走気味で意味不明でした
IntelliSenseが効かないだけでコードは書けたのでABはそれで提出しました
その後急にまたIntelliSenseが効いていたのでコンテスト終了まで使って今再起動何度しても大丈夫なのですが
原因不明なので様子見するしかない状態です
＞＞平均的なレートを上げていこう
そうですね
マイペースでもコツコツやるしか無いですね
まずはC問題までを確実に解けるように数をこなすようにします
DPや苦手なものは後回しにして解るものだけやってみます 最悪に備えてエディタは2つは用意しておくといいかもね 繰り上げり連絡きたけど最高でも6完までの人がToyotaコンの決勝に行ってもいいものかしら ホモじゃないんだなァ……
お前がメスになるんだからなぁ というかパフォ予測渋いけど前みたいにバグってるだけだよね？ やっぱりMoやるだけだと、かなりの人が解けるようになってるな D,方針はすぐわかったけど色のインデックスつけたグラフを探索して１時間以上通せなかったり罠が・・・ Dは色いらんのかーい！ｗってところが逆に解きづらい可能性がある 全く使わない入力がある問題を見たのはABC126以来かな こどふぉとかだとまあまあ見かける気はする
まあカモフラージュとしては良い案だと思う 本番ではCをDPだと思い込んで苦戦して結局時間切れのAB2完で-4ポイント
HW左上から右下への全通りの作り方が分からず
DFSとbitとnext聞いたことあるけど本番で実装に使うという発想が湧かないのが痛い
いつまた出題されるかわからないけどこいうものを随時テンプレ化することをみんなやってるのかな
本番後D問題は見てもさっぱり分からないので解説動画でDSUでも解けると聞いたので
自分の提出済みのグラフ関連のコード漁ってたら先週の問題の応用でいけそうと思って
先週のD問題に追加3行の計算とロープの色入力追加だけで解けちゃった
ただ解説見るとあっけなく解けることもあるけど
初見の問題だとまず解法が思いつかないし
何を勉強すれば良いのか分からないのはいつものことで
ひたすら過去問解いてコンテストに参加するしか無いの繰り返しなんだろうな
成長の実感が無い期間がしばらく続きそう >>792
> DFSとbitとnext聞いたことあるけど本番で実装に使うという発想が湧かないのが痛い
全探索の時はその2つを真っ先に思い浮かべればいい
C問題までは計算量考えない全探索でほぼほぼ行ける
問題をたくさん解くというのはこういうことを学ぶことで別に別にたくさん解かなくても学べる
今日は2つ学んだから成長したぞ
今まで時間内に解けなかったC問題がいくつか解けるようになったはずだ 制約から全探索が間に合うかどうか確認しておくといいよ
実装については類題解いて慣れるしかないと思うけど >>793-794
ありがとうございます
このスレにいる方って本当にポジティブな方が多くて励みになります >>794
Cでアップアップしてるやつにそれができないことを知りながら誰でもできるみたいな感じでマウント取るんじゃねえよ寒色のくせに >>792
今回のC問題みたいなのについてはテンプレ化は難しいと思う
とはいえ、DFSによる全探索は大体どれも似たようなパターンでは書けるから、何個か類題解いてみて自分に合った型を身に付けられるといいかな ChatGPT昨日の問題全部解きやがった
2021年までのデータしかないんじゃなかったのかよ どこまで行っても補助輪がついてる競プロ界の中でテンプレがどうこう言う話なのかなあ？ テンプレというか、この手の移動が「W-1回の右移動とH-1回の下移動」の順列と一対一対応するのが典型では（ABC034-C とか） ありがとうございます
>>797
これを機会にDFSに触れてみます
>>800
本質を言語化して頂いて助かります B問題未証明で適当に通した人多そうだしあまり好きじゃない
誤差とかも嫌だし DFSで解けるらしいというヒントだけで初見のC問題をDFSで実装して解けたけど4時間半掛かりました
すぐに分からないものを出来るまでやった方が良いみたいなことをどこかで見聞きしたので試してみたけど
もの凄い疲労感とちょっとだけ達成感
さっさと解説ACでどんどん数こなすのとどっちが効率良いんでしょうね
問題やその人の好みってことだと思いますが・・・ 解説ACするかは、記憶力に自信があるかじゃないかな
頑張って自力で解いた経験が無いと覚えられないならちゃんと取り組むべきだし、解説を次々開いても一読しただけで暗記できるなら解説ACの方が効率が良い
まぁ解説ACつっても典型要素のエッセンスはちゃんと復習してるけどな
あなたの場合、そもそも解説を読むだけではどこが典型か理解できないみたいだから、ちゃんと問題に取り組む時間を設けないとダメだと思う 明らかに向いてなさそうだが競プロやってる理由はなんなんだ？ この界隈、全体的にネット上の立ち回りが下手くそ
特にトッププレーヤー おぼえると言う意味が分からない
考えられない、理解してないと言うことだろ 293C、どうやって書いてもREが出ます。
サンプルの2題だけ通ってあとは全部REになります。
何が原因だと思われますか？
他の提出車を見てもREばっかりで ここが次スレということです
みなさんよろしくお願いいたします ここはガイジスレの次スレって聞いたんですけどガイジがいないように見えます
私がファーストガイジになっていいですか？ >>810
サンプル以外全部REってレベルで通らないときは、自分で適当な入力を手で作ったりランダムな入力を生成するプログラムを書いたりしたら手元で再現できる確率が高い >>810
HとW間違って配列外参照してないか確認してみるとか
サンプルはH=Wしかないし >>817
これをまともだと思ってるやつがいるあたりこっちも相当ヤバい 制約から全探索が間に合うかどうか確認しておくといいよ
実装については類題解いて慣れるしかないと思うけど
普通にまともじゃね？
これで「この文章は出来て当然だと言わんばかりに煽ってる」って思うか普通？ Cすらできない初心者に言うならどう見ても煽りだろw C問題辺りからループの計算量を把握する必要がある問題が出始めるのでC問題で苦戦している層に対してのアドバイスとして1文目はまぁ妥当
実装が難しいって言う書き込みに対して実装はいろんな問題をやりながら慣れるしかないって回答してるから2文目は妥当
やっぱ普通じゃね？ Cでアップアップしてるやつにそれができないことを知りながら誰でもできるみたいな感じでマウント取るんじゃねえよ寒色のくせに
プログラマーが問題
つかこいつのほうが煽りカスだろ
ブラウザ一致してるから自演だし C問題ができないってことは灰色だぞ？
それに計算量ができて当然みたいな言い方を妥当と言い張るのはどう誰が見ても煽りだよw
意図的に言ってるやつに何言っても無駄だがな
アドバイスするなら見積もり方くらい教えてやれや
寒色の癖にマウント取ってんじゃねえよ 当然って言い方そもそもしてないだろ...
〇〇したほうがいいよ(〇〇出来て当然って読み取るのはおかしいでしょ) 当然って言い方そもそもしてないだろ...
〇〇したほうがいいよ(〇〇出来て当然)って読み取るのはおかしいでしょ
カッコの位置ミスった🤗 マウント、とか寒色のくせに、とかは大抵自己紹介だから、つまり煽りカスなんでNGしておくと良いぞ
……と思ったがレスバが最初から目的っぽいな、5ch内なら氏名特定攻撃も来ないだろうし 効きすぎて笑う
いくら言葉を繕って逃げ道を用意しても本性が隠せないやつはすぐ尻尾出すから意味ないぞw やっぱこれくらい殺伐としてないと居心地悪いわ
ワッチョイ付きだからって妙に行儀良かったからな つーか携帯回線と家回線切り替えたくらいで自演に望むなよ
家回線chrome+携帯回線mateってかんじで回線とブラウザ両方変えたほうが自演通るぞ ﾜｯﾁｮｲ←回線会社固有、回線ごとに変化しない
初めの2文字←携帯だとあんまり変わらない
次の2文字←固定回線だとあんまり変わらない
最後の4文字←ブラウザと端末の種類による、過疎スレだとここが一致=自演 あとsoftetherを使うと5-ipくらい併用できるからもっと自演できるぞ😉
今回は俺の勝ちだったがお前がレスバレベルを上げたらまた戦おう ﾜｯﾁｮｲの仕組みすら知らないのを見るにどうせ普段から例のID無しスレで自演してるような奴だろうし相手にしなくても良いよ もしかしてお前の言う自演って、wi-fi使える場所と使えない場所でワッチョイ違うこと言ってんの？
自演慣れしてることを自白していくスタイル笑うw まぁそれはどうでもいいとして>>830に反論くれや >>848
自演君何言ってんのw
お前がアオラーだってことは証明されたじゃん
まだ言い逃れできると思ってんのヤバくね？w 俺が馬鹿になればなるほどみんな理知的で輝いてるように見える アオラーっていう謎造語言い出して話がどんどん自演と煽りの方向に行ってるけど俺の主張は最初から794は悪意的に解釈されないってだけだけど ガイガイガイガイガイガイガイガイガイガイガイガイ
おはようございます😃 早稲田大学 Twitter名さかえまな atcoder 名 na_kombu 真中紗枝
教育学部 25歳 早稲田大学 Twitter名さかえまな atcoder 名 na_kombu 真中紗枝
教育学部 25歳 競プロスレなんてレートが高い方が正義だから、レスバで勝ちたかったらレートの高さを証明すれば終わりなんだよな
まぁ灰色アオラーには無理だろうけど 会場のSSID、4.2Ghzと書き間違えてるのを二重線で消して2.4Ghzに書き直してて草
印刷し直さないのかい 数百人もいるのに無限に飲み物食べ物が補充されるのが太っ腹でいいね 競プロやってる知り合いもいないしイベントも興味ないから辞退したけど飯だけ食いに行けば良かったか 今回Gまで簡単というか典型めで良かったけどオイラーツアーのライブラリ持ってなくて一から書いてたら橙パフォ逃しちゃった
というかGこんなに解かれるもんなんだインフレしすぎ Gはかなり既出感の強い問題だからね
vaidation用の問題みたい Ex、指数時間アルゴリズムのスライドに何か載ってないか探しに行ったけど、特に収穫はなく Fは例の食塩水の問題が結構印象に残ってたからすぐ方針に辿り着けたけどABCだとやっぱりほぼ既出問題ばかりになるから精進が大切だな Eでバグりまくって見てなかったFやったら5分で解けた… multisetを使うDがレート380とか信じられないんだけど・・・ >>885
multiset使わなくても解けるよ
ACしたほとんどの人使ってないんじゃない？ Eまでほぼ愚直に実装する問題だったのはだいぶ珍しい気がする
Eみたいな問題はバグが怖いからあまり好きじゃないけど WA出しまくりの6完ですわあ...(´・ω・`)クエリ処理で前も同じミスしたのよね もともと寒色になんの価値も無いのでGPT使われようがなんの問題もないね GPT4で5完水パフォか
これは使ってる人が水だからあんま意味ないけど
茶ぐらいの人が使ってもパフォ上がるんだろうか https://qiita.com/autotaker1984/items/2929937cd1fea6137d1f
AtCoder終了のお知らせ
前回は質問を工夫して何度かやり取りと手直ししたら3.5でも一時間で7完だったからお前らよりよほど優秀 優先度付きキューとか今日日灰色でも標準装備だろうし余裕でAIに指示出せるな
AtCoder崩壊近しなのか？(´・ω・`) 寒色diff程度の簡単めな問題なら解法分かってる状態で質問繰り返してしかも手直しまでしたら解けるに決まってるんだよな
解法が分かってない状態でも自分よりも高いパフォが出せるようになるかが問題 GCJとTCOが終わったり、ABCで大半のユーザがAIに負けるようになってもまだみんながんばってね 灰とか茶の人が実際に使ってみたレポートが欲しいんだけど、自分がガチでやるより良い成績が出る可能性があるとなるとなかなか使いたくないのかな AGCのA安定して解けるようになったらヤバいけど考察不得意そうだからまだ大丈夫そう
ABCのド典型問はどんどん解かれそうだけど GPT4もそのうちAPI公開されるし
誰かが完全自動化ツール作って放流したら終了だね 逆に機能のGなんかは一発で解けてもおかしくない気がするけど、意外とまだ典型習熟度高くないね >>894
なんで解けるに決まってんだよw
問題読ませただけで「ここではMoのアルゴリズムが使えます」とか「答えを固定して二分探索します」なんて言うAI他にあるか？ >>901
そうだから質問を繰り返してAIを導く必要があって、導き方を既に知ってるなら最早AIじゃなくて人間が解いてるのと変わらないのではって話をしてるんだけどどういうツッコミ？ >>902
日本語読めないのか？
AIが問題解決に最適なアルゴリズムを提案してんだよ
人間じゃなくてだな >>903
上の方で貼られた記事のE問題までの話をしてんのね
社長のchatGPT縛り配信の話かと思った >>904
何を言ってるんだ
7完達成しやがったという話を先週ここに書いたんだよ
今週5完の記事が出たから蒸し返した 蒸し返したらそんなの当たり前とか言うトンチキが出てきたから呆れてるとこだ
当たり前のわけねえだろ >>906
当たり前っていうのはAIを適切な解き方に誘導したらそれに沿って解いてくれるのは当たり前って話をしていたつもりだった(3.5の時はこうしないと簡単な問題以外は解けなかった)
chatGPTがバージョン4になった今どういう風に解いてくれるのかは把握してないし先週のABCで7完したという話も初耳 Moのアルゴリズム提案してくれたやつは問題を読ませた“だけ“ではなくて質問である程度誘導してたとは思う
（もちろんそれで提案してくれるのはめちゃくちゃ凄いが） >>907
まだ誘導とか言ってるのか
100回読むか小学校からやり直せよ レスバしたいだけのｱｳｱｳｳｰの人、結構みっともないからやめた方がいいよ ほんと、そういうくだらないのはツイッターでやれよな すまん
初心者なんだがIQが低すぎてこの問題が解けない
一つだけクリア出来ないテストケースがあるみたい
N以下の自然数でXの倍数またはYの倍数であるものはいくつあるか？
入力
N X Y
制約
1≦N≦10^6
1≦X＜Y≦10^6
コード
#include<bits/stdc++.h>
using namespace std;
int main() {
long long n,x,y;
cin>>n>>x>>y;
if(y%x==0) cout<<n/x<<endl;
else cout<<n/x+n/y-n/(x*y)<<endl;
} 誰かどの辺が間違ってるか教えて
なんでACできないんだろ 総当たりして誤るテストケースを自分で見つけるスキルを身につけることも重要 ありがとうございます
たしかに、最小公倍数でいいですね
IQがゴミすぎるんで競プロ止めます コンテスト開始前に突如延期は酷いやサーバーの問題だから仕方ないけど おそらくGTPにヒューリスティックを除くatcoder的なスキルはほとんど使われていない、使われてるのはニューラルネット、内積、最適化、強化学習など。何故か整数ばかりのパズル最適化は見当違いも良い所。
競プロは役に立たない。 役に立つと思ってやるもんじゃないって既に無限回言われてるだろ何を今更 AtCoderJobsのランクがほぼ無意味になるな >>926
> ニューラルネット、内積、最適化、強化学習
この並列笑えるな、内積はセンスある 競プロ以前に高校数学すらまともに勉強してなかったんだろうな
AI開発に全く従事してないような奴の妄言 >>930
トランスフォーマーの核なので強調してみたのじゃｗ
>>931
DSだけどどう温かい目で見てもABCの問題の大半は役に立たない。ガチ。 お前がディープステートだったのか
ついに正体を表したな 内積でqueryとkeyのある種の類似度を計算して重みとして利用するのはそうなんだけど、まず磨くようなスキルではないのではないかという
離散最適化が主なのはそうだけど、実質的には連続緩和して解くような問題もままあるので、連続最適化をしてないとも言えないし 問題
N 枚のカードが横一列に並べられています。左からi 番目のカードには整数Aiが書かれています。
カードの中からいくつかを選んで、合計がちょうどS となるようにする方法はありますか。
制約
1≦N≦60
1≦Ai,S≦10000
入力は全て整数
入力
N S
A1…AN 質問です
これって動的計画法を使う問題ですよね
dp[i][j]をiまでのカードのなかで合計がjとなるようなカードの組み合わせが存在するかと考えても上手くいかないです
ほとんどのテストケースではACが取れるので全く検討違いというわけではないと思うのですが、有識者の目から見て間違ってる部分はありますか？
#include<bits/stdc++.h>
using namespace std;
using ll = long long ;
using bl = bool ;
#define Rep(i,a,b) for(ll i=a;i<=b;i++)
int main() {
ll n,s,A[69];
bl dp[69][10009];
cin>>n>>s;
Rep(i,1,n) cin>>A[i];
dp[0][0]=true;
Rep(i,1,s){
dp[0][i]=false;
}
Rep(i,1,n){
Rep(j,0,s){
if(dp[i-1][j]==true) dp[i][j]=true;
elif(dp[i-1][j-A[i]]==true) dp[i][j]=true;
else dp[i][j]=false;
}
}
if(dp[n][s]==true) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
} 自分でテストケースを作成して色々とやって見たのですが上手くいかないです >>937
全然ちゃんと確認してないんだけどj-A[i]で範囲外参照してそう
環境にもよるけど、 #define _GLIBCXX_DEBUG を入れると範囲外参照関連のデバッグはしてくれるから便利だよ(実行時間が遅くなる場合もあるから提出する時は外れるようにすると良い)
まあこういう遷移はめちゃくちゃ良くあるし慣れたらデバッグしないでも殆どミスらなくなると思う >>939
ありがとうございます。
Ai＞jであるときとそうでないときで場合分けしたら上手く出来ました。 >>940
ありがとうございます
elifの部分もまちがえていましたか 配列外参照の仕様に関してはまだちゃんと理解していませんが、939のレスをヒントにして解決することが出来ました。 質問
N個の正整数の最小公倍数を求める問題で分からない部分がありました。
コード1ではACが取れなかったのですが、コード2に変えてみたところACを取ることが出来ました。
数学的にはコード1もコード2も違いがないと思うのですが、何がいけなかったのでしょう。
頭を捻っても全く分かりません。 コード1
#include<bits/stdc++.h>
using namespace std;
ll Gcd(ll a,ll b){
while(a>=1 && b>=1){
if(a>b) a=a%b;
else b=b%a;
}
if(a!=0) return a;
return b;
}
int main() {
ll n,A[100009],g,l;
cin>>n;
Rep(i,1,n) cin>>A[i];
l=A[1];
Rep(i,2,n){
g=Gcd(l,A[i]);
l=(l*A[i])/g; ←変えたところ
}
cout<<l<<endl;
} コード2
#include<bits/stdc++.h>
using namespace std;
ll Gcd(ll a,ll b){
while(a>=1 && b>=1){
if(a>b) a=a%b;
else b=b%a;
}
if(a!=0) return a;
return b;
}
int main() {
ll n,A[100009],g,l;
cin>>n;
Rep(i,1,n) cin>>A[i];
l=A[1];
Rep(i,2,n){
g=Gcd(l,A[i]);
l=(l/g)*A[i]; ←変えたところ
}
cout<<l<<endl;
} l*A[i]がlong longの最大値を超えてオーバーフローするのでは 今度からChatGPTに聞けよ
質問丸々手直しせずコピペして聞いたらこんなふうに答えたぞ
コード1とコード2は、最小公倍数を求めるアルゴリズムとしては等価です。しかし、2つのコードは演算の順序が異なります。
コード1では、(l*A[i])/g という式を用いて最小公倍数を更新しています。これは、 l と A[i] の積を g で割った商を最小公倍数としていることを意味します。
一方、コード2では、 (l/g)*A[i] という式を用いて最小公倍数を更新しています。これは、l と A[i] の積を g で割った余りを最小公倍数に加えたものとしています。この操作により、 l と A[i] の積が l と A[i] の最小公倍数になるように調整されています。
なぜコード2がコード1よりも正確であるかは、データ型の問題に関係しています。コード1では、(l*A[i])/g という式を用いることで、最小公倍数が ll 型で表現可能な範囲を超えてしまう可能性があります。一方、コード2では、 (l/g)*A[i] という式を用いることで、最小公倍数が ll 型で表現可能な範囲内に収まるようになっています。つまり、コード2は、最小公倍数が大きな値になる場合でも正確に計算できるようになっているということです。
以上のような理由から、コード2がより優れた実装方法と言えます。 別に元々質問が多くて困っているようなスレではないし、ここで聞く分には構わないと思うけど、ChatGPTの性能すごいね
ただ、誤ったことも自信満々に言うから、まだまだ初学者向けのサービスではないと思う ここで聞いたら「省略したところに原因が書いてある」と言うやつがいるから書いたんだよ
原因は書いてないな
書いてあるのは制約だ ちなみにbingで「N個の正整数の最小公倍数を求める問題はAtCoderのどれ？」と聞いて返ってきたのが次の返事
AtCoderの「数学とアルゴリズム」コンテストにある「017 - Least Common Multiple of N Integers」¹が、N個の正の整数A_1, A_2, ..., A_Nの最小公倍数を求める問題です。制約は、2 ≤ N ≤ 10^5, 2 ≤ A_i ≤ 10^18で、問題の答えは10^18以下です。¹
この問題は、AtCoderの「数学とアルゴリズム」コンテストにあるもので、N個の正の整数A_1, A_2, ..., A_Nの最小公倍数を求める問題です。¹¹:[AtCoder](https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_q)
ソース: Bing との会話 2023/3/22(1) 017 - Least Common Multiple of N Integers. https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_q アクセス日時 2023/3/22.
(2) AtCoder 版！マスター・オブ・整数 (素因数分解編) - Qiita. https://qiita.com/drken/items/a14e9af0ca2d857dad23 アクセス日時 2023/3/22.
(3) AtCoder 版！マスター・オブ・整数 (最大公約数編) - Qiita. https://qiita.com/drken/items/0c88a37eec520f82b788 >>956
制約は原因じゃないぞ
むしろ制約があるためllに収まるから真逆だ 口論したいわけじゃないんだが
制約が原因という表現で別に間違ってないやろ >>952
>>953
ありがとうございます
理解出来ました
次からはchatgtpに質問して解決できなかったらここで質問します >>959
間違ってる
電車が来てる時に線路内に入ってはいけないという制約があるとする
それを見ずアホが線路内に入って死んだとする
そいつが死んだ原因は制約か？
違うだろ
この質問の場合も制約があるから間違ったんじゃなく、制約がなくても間違ったんだぞ
10^9までの自然数という制約が無かった場合は条件分岐が必要になるがあるためにそれはしなくていい
制約は問題を簡単にしてるだけで難しくはしてない 制約次第では上のコードでもあってるんだから制約が原因だろ
まあほんとに意味のないやり取りなんでこれ以上は相手しないが 日本語わかんないやつはChatGPTより下だぞ
議論じゃなくお前の間違いを教えてやってんだから口答えすんな ChatGPTはお前らより賢いから正しく言葉を理解して正しく答えたぞw
成約を見ないことで不正解になった場合、それは成約が原因と言える？
制約を無視してしまったことによって誤った結果が生じた場合、それは制約ではなく主にあなた自身が原因です。制約は、現実的な制限を示すものであり、それらを考慮しないことは、問題を引き起こす可能性があるためです。ただし、制約が明確でなく、十分に説明されていなかった場合は、誤解が生じる可能性があります。その場合、制約を理解しようと努力する必要があります。結局のところ、誤りを修正するためには、問題を引き起こす可能性のある要因を正確に特定し、それを修正する必要があります。 こっちは自分のことをガイジだと認識してないガイジが湧くから大変だねえ 自分が正しいと思ってる間は無茶苦茶な強弁するのに証拠を突きつけられたら自演して人格攻撃に移りなおかつ自演のやり方の講義までするというガイジはいつになったら自分をガイジと認識できるんだ？w 制約上オーバーフローしうることがWAの原因なんだから、制約も、その制約によってオーバーフローするようなコードを書いたことも、それぞれ原因と言っても別にいいだろ
マジでしょうもねえ… アホなのか？
回答の制約じゃなく質問の制約だそ？
原因はそれを考慮しなかったことに決まってんじゃんw
日本語読めないのかよ
ChatGPTですら読めるのにw ほんとに何言ってるのかわからんわ
自分の中では理屈が通ってるんだろうけどどう通ってるのか想像することさえ難しい 何言ってるのかわからんのは自分の頭が悪いからと早くきづけるようになれるよう祈ってるよ
わかんなきゃChapGPTに聞け
正確に理解してるから まあ要するにお前の言語能力は原始的なAI以下ということだ 読解力でAI未満てそれ何ならAIに勝てるの？
もしかして数学で勝てるつもりなのか？ 暴れてる奴もChatGPTなんだ怒らないでやってくれ そんな賢くないだろw
暴れてるやつは日本語ろくに読めないんだからw 日本語の言語能力が低く日本人にとってはありがいんだろうな。 チョクダイが焦ってるけどAIの流れとまらんだろ
上流と趣味以外はオワコン コーディングテストとしてjobsに関係ある層がほぼ消えるワケじゃからのぉ、ワシもrated参加はやめるのじゃ 集合でラッセルのパラドックスを考えるガイジも集合しろ 教プロはもうおしまいです
GCJとTopCoder Openという最も有名な最強の競プロerが競う大会は終了です
ABCもChat AIに無双されます
初心者も上級者も楽しめない競技になります ちょくだいの最近の投稿見ると焦りが隠しきれてないな
まぁ絵師みたいなもんか ライト層はAIで良いじゃんってなるから競技人口増えなそう ボケ防止としてはかなり有用じゃ、コンテストの体がないとやる気がせん 老人ってドーパミンがあんま出ないんじゃない？
だから競技にする必要ないんじゃね
数独問題集みたいにモクモクとやらせれば十分だろ A～E5完
Dで方針間違えすぎてGまで取りかかれず Eそんなに難しいか？と思ったけど、確かに微妙に典型度低いかもしれんな 3000人も解けてるけどこのD相当難しい、GTP4も解けてなかったし B4乗ループ最初は思いつかなくて面倒そうだなって思ってchatGPTに投げたら全然違うプログラム書いてきてキレてた >>998
同じくDで爆死。数字ごとのパリティまでは
気がついたのだが、長さNのビットベクトル
を10個作ってなんとかしようとしてしまった。
縦と横を入れ換える頭の柔軟性がなかった。 このスレッドは１０００を超えました。
新しいスレッドを立ててください。
life time: 89日 10時間 23分 46秒 5ちゃんねるの運営はプレミアム会員の皆さまに支えられています。
運営にご協力お願いいたします。
───────────────────
《プレミアム会員の主な特典》
★ 5ちゃんねる専用ブラウザからの広告除去
★ 5ちゃんねるの過去ログを取得
★ 書き込み規制の緩和
───────────────────
会員登録には個人情報は一切必要ありません。
月300円から匿名でご購入いただけます。
▼ プレミアム会員登録はこちら ▼
https://premium.5ch.net/
▼ 浪人ログインはこちら ▼
https://login.5ch.net/login.php レス数が1000を超えています。これ以上書き込みはできません。
