◎正当な理由による書き込みの削除について： 生島英之 とみられる方へ:競技プログラミング総合スレ 65 YouTube動画>1本 ->画像>7枚
動画、画像抽出 ｜｜
この掲示板へ
類似スレ
掲示板一覧 人気スレ 動画人気順
このスレへの固定リンク： http://5chb.net/r/tech/1672026457/ ヒント： 5chスレのurlに http ://xxxx.5chb .net/xxxx のようにb を入れるだけでここでスレ保存、閲覧できます。
!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
http://2chb.net/r/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軸がどの方向か明記されていない場合どうすれば良いのでしょうか
>>3 プラス効果実感できそうなのが青くらいというのはそうなのかもしれない
茶色以上だったら、ないよりはある方がマシって場面はたくさんあると思うけどね
こんなのセルフプロモーション力次第だから、そこがヘタクソだと何色でも…というところがあるかな
>>8 本持ってないので確認できないけど、確かに普通数学では左右がx軸、上下がy軸方向で書かれることが多いからちょっと混乱する人もいるかも
問題見た限り、答えに影響しないのでどっちで書いてもいいってことで、逆に書いたんじゃないかな
ちなみに競プロだと配列の添字の関係で逆に書く場合のメリットもあるんだよね（この問題はそのメリットも別にないけど）
明記されてない場合はほぼ答えに影響しない場合だから、勝手に自分の中で決めればいいと思う、影響するんなら質問タブから聞こう
>>11 ごめん、思い切り多次元配列使うから普通にメリットあったね
軸の方向なんてだいたいどうでもいいよ
>>11 ＞＞答えに影響しないのでどっちで書いてもいいってことで、逆に書いたんじゃないかな
ありがとうございます
業務プログラミングでも画像処理やってるとたまに軸の順番が入れ替わるから困る
googbyeみたいに定期的にall ratedコン出せるのすごいよな
質問
apg4b終わった時点でも人によってどのくらいの行間を読めるか違うから一概に言えない
新しい本だから今取り組んでる人が多いという理由で鉄則本かなあ
AtCoder Problemsで自分のレートに近いdiffの問題解いていくのが結局一番着実だったりする
蟻本完璧に咀嚼しきれたら青～黄色はいけると思うしアレは中級者向けでしょ
結局本とかで勉強するよりも自分の実力ちょい上の問題を解きまくる方が効果あるのは事実
黄色より上は知識とは別体系の技能だから、本読んでどうこうって感じの世界ではないかな
蟻本は難易度的には、第2章が普通に初心者向けの内容だし、初心者でも読めるでしょ
おじさんが学生の頃は螺旋本読んで蟻本読んだら青になれた
・数学の得意不得意
そうそう、初心者向けじゃない競プロの本なんてないけど、地力の違いでどれがフィットするかはちょっとずつ変わるよねえ
数学そんなに得意じゃない場合、大学数学の場合の数や整数の参考書が役に立つこともある
あ、大学数学じゃなくて大学受験な
>>30 蟻本も人によってはくどくなくてちょうどいい入門書だからね
数学は特に得意でも不得意でも無いよ
運営がワールドワイドならそれも可能だろうけどこれはしゃーねえべ(´・ω・`)ぽれはお盆の時期とか出たくないのに逆にコンテスト生やしてくるし
俺も正月はいいや、暇だけど実家だから回線悪い(´・ω・｀)
整数と場合の数だと大学への数学のやつかな
初等整数論とか組合せ論の初歩についてあまり詳しくないけれど、
プログラミングコンテストにもいろいろあって、競技プログラミングのアルゴリズムという分野のコンテスト（具体的にはAtCoderのABC、ARC、AGCは全部そう）は、整数、組合せ論の問題が離散数学の一部として出題されるので、もろに成績に関係する
組合わせ論・数論の精選とかパーフェクトマスターみたいな数オリ用対策用の参考書って競プロにも役立つの？たまに買ってる人見かけるけど黄色以上で効くのかな
繁野麻衣子著『ネットワーク最適化とアルゴリズム』を買いましたが、積読状態です。
いつだったか、数オリ高度典型の幾何がAGCかARCに出てて話題になったからごくたまに効くんじゃないか
>>47 未読なので目次見ただけだけど、この本のアルゴリズムは全部競プロで頻出だと思うので、知らない知識を摂取するって意味だとどれも役立ちそうかな？
>>44 ,48,50
ありがとうございました。
>>50 読んでみます。
純粋な学術書は体系的すぎて競プロで使うには多く説明しすぎてることもあるから、効率がいいかはわからんな
最悪計算量と何ができるか知ってるだけでも競プロでは使えるな
なかなか灰色から上がることが難しそうですね...
和を積に変換
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ではなかなか使用機会ないだろうな
データ構造に載せるモノイド、頑張れば多項式か行列に帰着できる説
半束とかはモノイドだけど多項式や行列にはならなくないか
適当に和に相当する演算を導入して半環の積にできんかとか考えたけど無理か
あまり半束であって束じゃない例について考えたことなかったけど根付木の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 だけ間違えてるやつ一覧みたいのって取ってこれるんかな？
同じようなテストケース通し具合のコードを持ってくるサービスあった気がする
>>84 >>85 もしかして: AtCoder Companions
言語仕様の勘違い由来のバグ取りはかなり気付くの難しいから、初心者がそういうの見つけるのに使えそうだな
今年こそ青に定着したいのに三が日何もやってねえ...(´・ω・`)
正月で生活リズムが整っちゃってこどふぉに出られなくなっちゃった
Hello 2023普通に良コンテストだったぞ
えAtCoder Companions有能すぎるんだけど. これ何でテンプレ入ってないん?
TL少し長めの問題なら、10^9回計算する解法でも通るんだね（想定解法じゃなかったけど）
重複組合せの式nHrで、整数のオーバーフローをできるだけ避けて計算したいのですが
>>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の解説読んでもわけわからん
Dで素因数分解出来ることが保証されてるのが頭から抜けてたせいで絶対想定解じゃないだろって思いながら無駄にミラーラビン素数判定法とか使ってしまった
素因数分解出来ることっていうより素因数分解の一意性か
問題は全然クソじゃないと思うけど、i=1,2,…,⌊N^(1/3)⌋のうち、N が i で割り切れるような最大の i って書き方が何か変で、i=2,…,⌊N^(1/3)⌋のうちNを割り切る最小のiと言った方が正しいような気がする
G、本質パートからしてボリュームあるのにさらに任意ｍod二項係数使うんかいって思ったけど、想定解は全然使ってなかった
>>105 ちなみに、そのやり方でTLEしないと思うんだけど、N^(1/3)までで探索打ち切った？
あー、二乗の計算時間もだめだってのか。効率化難しいな。
Dは想定回じゃなくても、いろんなテクで解けるし、みんないずれかの解法にサクッとたどり着いてる感じだな
>>113 なんかその書きぶりだと、もしかしてj^2 = N/iになるようなjも探索で出した感じ？
Eが素直なDFSすぎてDと逆でも良いだろとは思った
Eはむしろ個人的には意表を突かれた感じでギョッとした
>112
>>119 >必ず1個の解が見つかるはずで、解が見つかったら打ち切ったら良いんだから、N^(1/3)までカウントアップしないと思ったんだ。だから、N^(1/3)で止めるロジックは無意味だと思ってる。
確かにそれはそう、ナンセンスな質問ですまない
O(N^(1/2))になってたのがTLEの原因っぽいね
EやFはサクッと解けたけど、おれもDはちょっとギョッとしたよ
Ex、Polya の原理や包除原理知ってても簡単に見えないし、ABCで出した理由は有名問題だからなんかな
というか、GみたいのもOEISにあるのな
なんちゃらのフルイ使わないでやったらTLEして
ついこないだライブラリ作ったポラード・ローの高速素因数分解でDをしばき倒せたので良かった
Dは簡単すぎて本当にこれでいいのか何度も見直したんだが
そうじゃなくて小さい方が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
幅優先探索も深さ優先探索も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))の方が速いと思えるんですか？
浮動小数点数は値がデカいとスッカスカになって、例えば一定以上の大きさの奇数を表せなかったりするのが怖いんだよな
>>166 そっか、n の値を別の変数 m とかにコピーして、ループ内では m の方を素因数で割っていくイメージだったのですが（その場合 n は不変なのでコンパイラがちゃんと仕事をしていれば sqrt の計算は1回のみ）、i * i <= n で上限チェックをしているコードはループ内で n を変えていく想定なわけですか。
ARC対策に去年初めのARCの問題を考えてみたら、当時解けたのに今解けなくて笑えない
正月ボケで開催日を間違えて今年最初のABCを見逃してしまいました
C、判定も分割方法もわかったけどそこから回答例出す方法思いつかなかった...
Bは無理だと思って捨てたけど
むしろ、奇数偶数さえ押さえてれば1の場所だけで良いのか。
C後ちょっとだったけど500人近くも解いててびっくり
C問題はslopetrick系かな？と思ったけど式書いてみたら本当に単純な一次関数でびっくり
俺がその場で考え出した超スパゲッティなunion-findでD問題何とか通してやったぜ
やっぱ日頃から精進してないとABCまででも苦戦しますね
dic = {}
for i in range(int(input())):
D...
そういえば今度応用情報受験するんだけど、競プロ勢（といっても俺はガチ初心者レベルだが）
>>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は完全二分木の頂点を配列上で管理する話で、発展的な知識で思考をショートカットできる系の問題と言ってもいいかもしれんな（これぐらいなら再発明するやついっぱいいるだろうが）
>>202 自分は法則探しに時間使ったので、ある意味力業の方が早かったかもしれません。
>>194 AtCoderは日本で現役最強格の人や、世界的にも最強に近かった日本人選手が運営で作問作業のコアな部分に携わってるから出られなくて、ランキングにいない
それを差し引いても、中国や東欧の方がやや強いけど
>>204 過去のABの比じゃなく難解だったので飛ばして
C→B→Aの順で解きましたが
全条件を組み込みするのは絶対に嫌だったので
何か法則があるんだろうなと捏ねくり回してたら2倍か2倍+1に気づいたので
if文1行で解けましたが解説見ると知ってる人や上位の方が1-2分で解けるのも納得です
考えて解く問題より知ってるかどうかって問題が多い気がしますが
どちらにしてもD問題の壁が高過ぎるのは変わらないので
DNAとかIQなど持って生まれたもので精進レベルではどうにもならない感が半端無いなと思います
二分木の配列実装を知らないレベルでIQやDNAを云々するのは結論を急ぎすぎ
AtCoder青色くらいまでは本一冊程度の知識を身に付けていますか？で終わりなんだよな
努力でどこまでできるかについては諸説あるが、知識がないうちは自分が知識あれば解けるかどうかすらも分からんもんで、最初のレートの伸びが悪くても一旦勉強してみてから考えてもいいんじゃないか
最初天才にしか見えなかった解き方が、有名でありきたりな定石の変種に過ぎなかったなんてよくあることよ
少なくともD問題くらいまでに関しては毎回かなり典型的な知識しか要求されないし問題も素直なものが多いからそのレベルだとセンスとか関係なく訓練すれば迷わず書けるようになると思う
それとレートの伸びが早くて天才に見える人も、中学受験とか数学オリンピックで競プロの役に立つ思考パターンを予めたくさんインプットされてるのがデカいんじゃないかって話もあるからな
AtCoderの社長の人の本を少し読みましたが、アカデミックな香りが全くしません。
弱い相関はあるだろうが、基本別の能力だぞ
アルゴリズムや関連理論を知っていることと時間内にアルゴリズムを問題に適用できるかは別だしな
>>214 作問者はそういう経歴を辿ってるひとだらけだから傾向は偏っている
アカデミックな研究者が作問してたらもっと別な傾向になるだろう。新しく発表されたアルゴリズムを元ネタにした作問とかしそう
そうなった場合"精進＝アルゴリズム系の論文を読み漁る"になった可能性もあるのか...
まあレート競争するのが楽しいって体質なら、そうなったらそうなったで普通に論文も楽しく読めちゃう可能性あるけどな
暖色コーダーは割と気軽に論文読んでるしな
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が無いんだよな
C#は多分こんな感じ
>>227 pow関数使って26の累乗を求めるアプローチだと
整数型にキャストしないとWAが出るのです
>>233 10の16乗の桁数くらいだと1ずれるんですよね
>>234 3つだけWAになって何これ？ってなりました
その問題特有の性質じゃなくてc++だとpow関数がdouble型を返す仕組みになってることが原因だから問題の本質とは関係ない
225,226の言ってる事が理解できて勉強になった
C++の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問題でも自分の誤りを認めずに暴言吐いてた奴と同一人物だから無視でいいよもう
そういやそんなやついたな
競技プログラミングの鉄則で勉強してるけど本当に才能ゲーすぎるな
みんなが初見で解ける問題なんて本に載せても意味ないやん
なんか毎週こんなことやってる自分が急に虚しくなってきた
初見で解法が思いつかない
BとCでつまづいたせいでD解けなかった
Fまで解けた割にパフォ渋いんだけど参加者数の問題？
Bはnnのケース忘れてた
>>268 なんかpredictor変かもしれんね
>>272 前回も表示バグってた気がするしそうだと信じたい
>>260 ,265
マジレスしておくと、ある程度のレベルまでは間違いなくガチ暗記ゲーだからね
異常な天才は競プロ対策してなくても解けまくれるかもしれんけど、普通のひとにとっては暗記ゲー
そしていろんなことを暗記しまくると(理解度が深まってくると)、応用もどんどん効いて難しい問題も解けるようになる
まあ大学受験とかでも同じだろ
基礎を暗記してからようやく応用ができるようになる
やっとF自力ACできた
>>277 CD程度の問題を見て解法が思いつかず何やっても無理だと悟って
あまりの自分の無能さに嫌気がして
悪態をついた愚痴にマジレスしてくれる優しさに救われます
暗記ゲーにしては範囲が広すぎるし
勉強することを精進だと自分に言い聞かせてましたが
毎回理解出来ないものを永遠と写経するだけになっていて
初見で解法が思いつかないことが苦痛とストレスになって
病みそうなレベルなので
精神衛生的にも少し教プロから距離をおくつもりです
>>281 まあ、プログラミングというより数学の競技だと思っておけば安心するだろうね
大学受験数学は当然として、中学受験数学で学ぶようなテクニックが活用できたりするし、
そういう受験数学のエリートがさらにアルゴリズムをめっちゃ勉強して競い合うのが競技プログラミングだ
もし中学受験とかやってないのに、そういう連中に追いつき越えたいなら、そういうエリートがやってるよりもはるかな修練が必要だよ
まあそういうエリートは数学的な問題を解くのが大好きだから現時点の瞬間的な修練量でさえなかなか超えられないだろう
アルゴリズムやデータ構造というより数学そのものの勉強も必要になってくるしね
「競技」プログラミングが十分な勉強と対策をしなくてもできるなら、もうそれは競技じゃないんよ
今日のARCで大事なのは700点の難度だよなあ
ABCだったら初見力なんてそんなに大事じゃなくて、ちょっと変形された問題が解けることが重要だと思うんだよな
ただ、瞬発的に解法を発想できないのは仕方ないにしても（知識不足だと発想の引き出しがないからそりゃ無理）、解説を読む段階になったら時間を掛けてでも書いてあることを理解するように心掛けないと類題を解けるようにならないと思うぞ
800点はブレで結構解きやすいこともあるけど900点はきっちり難しい印象がある
昨日のG残り時間少なくて諦めてたけどEかFくらいに置かれてたら印象変わってそう
ABCは自分の中では結構E<F=G<Exみたいな印象があるかなあ
それと6問ABC時代のF（600点）は今のGより難しかったような気がするね
質問
llは1をlong longとみなすってこと
<<はシフト演算子と言って、数値の各bitをずらす働きがある
正解してたんだけど、
D1見つけてそれ使って比較出来るところまでは気付けたのにマージソートにまで辿り着けなくて勿体ない
お、ナメクジから初めてようやく茶色になれた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を比べる時
>>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!とかにあったけど……今回は種類数が多いから辛いんだよな
ウェーブレット木/行列って競プロでどれくらい使える？
>>321 2-SATより上、セグ木より下くらいの頻度で使える
正直言ってACLに匹敵する実用性がある
遅延セグ木はもう誰でも知ってそうなデータ構造と化してるけど、WMは有用性の割にまだそんなに広まってないよな
ABC97 B Exponentialについて教えていただけませんか？
for文のインデントがおかしくなってますね(汗)
>>324 pが3以上の場合も考える必要があります
sqrt(i)%1に思うことはあるけど、その前にまず誤読してないか？
>>326 >>327 完全に勘違いしてました(汗)
ありがとうございます。
プログラムだかソフトウエアだか忘れたけど、ひろゆきみたいに上から目線で君臨しているやつまだいるの？
しゃくとり法について質問
解答例の通りに実装すれば計算量がO(N)で済むと書いてるけど、解答例だとN-1回ループのfor文の中にwhile文が入ってるんだけど、これで本当に計算量がO(N)で済むの？
頭が悪すぎて解説読みこんでもわかんね
Ri＝nである場合、そもそも増やさないから全体の計算量はO(n)で済むんだね
まあそんなもんでしょ
蟻本と螺旋本の電子版がセールで500円になってるの神すぎる
記憶違いでなければ蟻本ってとうの昔に更新しなくなったPKUに則ってたと思うんだけど、新しい版では書き換えられてたりするの？
これ見ると東大生でも大半が緑色以下なんだよな
参加者のレベルがあまりに高すぎてエリートでも灰～緑程度のレベルで燻ってる
これから、AtCoderに参入する人はこの事実を知っておいた方がいいわ
青より上までいけるのは東大生でも極わずか
こっちはまだ少しましかな
これのほうがいいか
しかも、これは1年半以上前のデータだからな
今は当時よりも参加者のレベルが上がってるから、東大生であっても緑まで行くのは相当苦戦するかも
Fラン大学とかだと茶色も無理なんじゃないか
https://docs.google.com/spreadsheets/u/0/d/1_rtU2geWnkZyOBYXyvPtcyn9GRfucd7GGFQqoGM5fZE/htmlview 東大生が多いのは事実だけど全員が競プロに本気出してるわけではなくて適当にやってる人や合わなくて緑以下で辞めるような人もカウントされちゃってるから競プロに取り組んだ時間も結構重要よ
そうだよ
ていうか競プロなんて役に立たないんだから、時間を注ぎ込んでないほうが賢くて偉い
前回茶色になれて、今回Dで解けた。
だめだーdpどう使うのか思い付かん
Cは楽な方法思いつかなかったから
自分もFで1時間以上椅子を温めていた
またCで誤解法でACしちゃったかも？
>>355 4 3
1 2
1 3
1 4
とかはNoだけど、それだとYesになるかな
>>355 次数が3以上の頂点を含む木だとダメだから嘘解法では
>>355 木だったらだめだな
というかこれ落とすテストケースないのか…
>>355 解説の1つ目の例で間違いなのになんで通るのかw
EとかはSAISしたあとにLCPテーブルとセグ木を組み合わせる例の典型知ってればすぐ思いつくし、知識ゲー感あるな
あちゃー
C次数3以上の頂点を含む木のテストケースすら入ってないってガバガバすぎる
>>362 ABCはいつも知識ゲーだぞ
例えばセグ木とかローリングハッシュとかをコンテスト中に自分で発明できるひとなんてほとんどいないし
Gみたいに座圧とデータ構造組み合わせる問題は思い付いてから書ききるまでが長くてストレス貯まる
Gみたいに座圧とデータ構造組み合わせる問題は思い付いてから書ききるまでが長くてストレス貯まる
他の解法何も理解してないけどEはTrieが一番楽だと思ってる
Trieの方を先に思いついたがポインタアクセスの定数倍が怖くてやらなかった
Eはソートすると両隣と比較するだけで済むけどTrie解法の方を知らない
>>371 解説に載ってるケースだから落としたいに決まってる
ワイもtrie木の存在を知らないまま再発明してた
今週は
今週は
>>371 連結じゃないパターンとかはちゃんと入ってるのに解説の図にも載ってるようなシンプルな例外が含まれてないの謎だよね
Exって小さい方から追加してワーシャルフロイド的にやればできるよなーって思ってそこから進まなかったけど、そのまんまなんだね
まあ次数の方の条件はあんまり見逃さないと思うけどな
参加者がミスりやすい連結判定ではあるけど、解説で必要十分条件を整理しているのにテストケースに反映されていないのを見るとうーんとなってしまう
極端なテストケースを含めてない問題って意外とあるのかな
C++なら通るってのは珍しくない
ABCのC以下なら有り得るがD以上でそんなことあるか？
昨日のExもbitset高速化が本質なところを、C++で愚直にO(N^3)やっても通るらしいし（勝手にコンパイラがベクトル化してくれてbitset高速化と等価な処理をしてくれる）、後半の問題でも非想定愚直解が通ることは普通にある
そういうのは大体コンパイラが運良く賢い最適化を適用できたときだから、狙って出すのはそんなに簡単じゃない
コンパイラの気持ちになればベクトル化効きそうなコード書くのはそんなムズくないと思う
他で類題が出たときにAtCoderはテストケースが弱いとよく言われている気がする
このwriterのARC-A問題毎回めちゃくちゃ難しくない？
Aを未証明で通したけど解説見たら全然違うことやってたから自分の解法が正しいのか分からん
Aはたしかに難しめだったけど、ARCで類題を見たことある気がする
コンセプトだけならAよりCの方が簡単な気がする
Aも天才って感じの問題じゃないけどな
Bがやたらと解きやすかったからAのやりにくさが際立ったのもある
A問題diff1500超えは笑う ARC最高記録かな
前半も難しかったけど、任意色コーダーもお手上げのEFもすごい
このまま開催が少ないと文句言われてるagc にすれば良かったよね
TwitterのTLに昨日のABCの感想が混ざってるせいで、E問題F問題解けたみたいなツイートがたまに流れてきて驚く
Twitterで解決しなかったのでここで質問
解答の場合分けを全部網羅できるかって話ならまあできてそうじゃないか
コンテスト中に実験や検証の目的で手元でテストケースを生成するという話なら、そこまで条件絞れてる時点でもうテストケース生成要らんレベルで解けてるだろ感あるが
仮に無限個のテストケースを一瞬でジャッジできるとして、1≦A_i≦2e5で作った2e5^N通りのテストケースと1≦A_i≦4で作った4^N通りのテストケースは任意のコードに対して同じAC/WAの結果を返すという主張です
任意の、は流石に過激主張か(57が入力に含まれているとpanicするコードなんかは落とせない)
想定解の場合分けをするコードの出力なら一致する
そりゃ想定解を書きゃ一致するだろ
まあ偶数が奇数の種類数が3以上ある場合に挙動が変わって不正解を吐き出すような嘘解法って特に思いつかんよな
>>415 意図が不明瞭なんだが、要するにコンテスト中のテストケースとして十分か知りたいのか？
すなわち自然に生えてくる嘘解法を落とすには十分かみたいな
任意の場合分け系解法に対して、みたいな話なら一致しないコードをいくらでも構成できるから偽だが
あれだわ、こっちで証明書くから正しいか正しくないかだけ教えて欲しい
>>418 場合分けに偶奇いずれかの種類数が3以上のときに生じるような情報を使っている場合は、4元に置き換えた時点でYes/Noの出力が変わることがあるので偽なんじゃね
場合分けに使っていい情報をある程度制限すれば真になりそうだが
まだ全然理解してないけどプログラムを入力からソーティングネットワークへの関数だと思ってる？
>>418 偶奇は要素に対する条件だからソーティングネットーワークは話が違う気がする
位置に対する条件だったらわかるけど
プログラムは全ての(i,j), 1<=i<j<=Nに対し「最初位置iにあったものと位置jにあったものが交換可能」かを定め、それを元に判定を行うものであるという仮定がある？
全然話についていけてないけど、場合分け系解法の定義がはっきりすればもうちょっと議論しやすくなりそう
多次元のデータを扱う過程でvectorだとMLEするのに全く同じサイズで代わりに生配列を使ったらメモリ制限余裕でクリアしたんだけど、これってvectorの方がより多くの情報を保持してるってこと？
vectorは配列サイズより大きな領域を確保してpush_backに備えるから
多分だけど、
要素数を保持するメンバ関数.size()も悪さに加担してそうだけど色々原因が絡んでそうだな
vector<vector<T>>は多次元配列じゃなくてジャグ配列だよ
ジャグ配列という言葉を覚えたてでドヤりたいのか知らんけどC++で区別する意味ねーぞ
？
よく「C言語に多次元配列はない、あるのは配列の配列だけだ」なんて聞くけど、じゃあ「真の多次元配列」ってなんなのさ
一般的な多次元配列というのはこれ
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++のvector<vector<T>>はジャグ配列であって、当然多次元配列としても使えるがパフォーマンスは落ちるよね？ってだけなんだがそんなに変か？
>>438 大丈夫か？
ポインタの配列の話なんか誰もしてないぞw
多次元配列は一種類しかないから区別の必要はないと書いたよな？
あ、そうかそうか
レッドコーダーの人は、プログラミング言語についても詳しい人ばかりですか？
第一級オブジェクトじゃないと何が起きるの？
抽象的なデータ構造としての配列の話をしてるのにC/C++の配列と混同してないか？
言語無関係な抽象的データ構造で多次元配列とジャグ配列を区別する意味なんてなおさら無いだろ
要件違うんだから区別する意味あるだろ
元の話って速度の話じゃなかったのか？
ジャグ配列か多次元配列かは明確に速度が変わるから、考える意味はあると思うぞ
あと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すればいいと思ってて、スレとして誰かをパージするようなことはしなくていいと思うんだよな
議論になるなら良いんだけど、前例からもわかる通り間違ってることを堂々と発言した挙句に明白な根拠有りで誤りを指摘されても自分の誤りを認めず暴言を吐き始めるのが厄介だと思った
また論破されるから追い出すってかっこ悪すぎない？w
前回で茶色になるようなレベルって自分で書き込んでるのにどこからそんな自信が湧いてくるのやら
論破されて自作自演で嘘の噂流すのかっこ悪すぎない？w
このスレ、発言から青～黄が5人くらいは確定で居るからなぁ
返り討ちにあって追い出そうとするのかっこ悪すぎない？w
明日のABCはARCよりかあ
中盤はいつもよりも難し目らしいからギリギリDが解けるかどうかみたいな層は明日厳しいかもね
緑から水色の初心者から中級者の間の層が狩られそうね
「終盤は難しくない＝普段のABCと一緒」って意味だと仮定すると、中盤がARCで後ろはマニアック高度典型という、ただの昔の企業コンARCなんだよな
企業コンは参加者数も稼がなきゃいけなくて大変だなって話
週1回コンテスト前の30分～1時間だけ過去問題Bを1～2問解いて本番するだけにしてから苦行ストレスがほとんどなくなりました
コンテスト中は順位表から読み取れる内容以外は他言に無用らしいから掲示板にはあんまり書かないほうがいいぞ
D嘘解法ぽいけど閃いたと思って暇つぶしに提出したらAC3TLE40WA3ってことはそこそこいい線行ってたぽい？
ABCFの4完
>>489 ヒントになった途端通報されるかもしれないので注意
今回の場合、試験中に「Dが難しい」と叫んでいると取られかねない
>>489 コンテスト中にSNSとか5chにコンテストのこと書き込むのは真面目にやめた方がいいよ
D問題で区間総和÷K=0で閃いたと思ったけど条件が足りなかったみたい
C問題で当たり前のようにunion findとかが出てきてビビった
解説見たらやっぱり何やってもこんなのコンテスト中に解けないやってなりますわ
先週もだけどC問題で出るグラフ問題はACLのDSUに慣れさせようとする作問者の意図を感じます
もう来週の問題も作成済みでACL使うグラフ問題シリーズが来週も出そう
unionfind、初中級のアルゴリズムの本にのってない気がする、atcoder高度すぎ
参加回数が規定数に満たないってことなんですが
C問題で下記のようなコードで提出してACだったのですが
あってる、もっというと以下でいい
UnionFindは、中身の理解と計算量解析自体は簡単ではないかもしれないけど、ブラックボックス化して使う分にはとても単純だから、まずはそういうものだと思って把握しといて損はないよ
Gはゼータ変換メビウス変換の要領でやれると思ったけど毎回頭がこんがらがる
Eを最初セグ木でmin取ろうとしたらTLEして致命傷で済んだ
>>509 ありがとうございます
また嘘解法だったかと不安でしたが安心出来ました
ただDは解説配信見てもさっぱりでした
union find は「プログラミング・コンテスト・チャレンジブック、第2版、2012」に載っていたような？
競プロ本じゃなくて一般的なアルゴリズム本には載ってなさそうではある
>>515 セジウィック＆ウエイン
CLRS
浅野孝夫
の本に書いてありました。
>>515 Kleinberg & Tardosの本にも書いてありました。
ありがとう
昨日のEx見てるがそれぞれのパーツはそんなに難しくなくても、コンテスト中に詰めるのは相当な情報処理能力要るなこれ
enumerative combinatoricsで式クソデカ数え上げの練習をしよう
信者では無くないか？
＞AtCoderユーザーは暇空寄り
chokudai定期的にいらんことに首突っ込むよな
最近やたらとイキってる陰謀論界隈の教祖様だろ
なんでミュートじゃなくてブロックするんやろなぁ。SNSの使い方下手すぎん
暇空応援公言は普通にショックだわ
ABC232E Rook Pathなんだけど、
↓上級編がでますね。
>>532 値が同じところで分けるとそうだけど、
多分解説は値が同じところで分けてるわけじゃなくて答えが計算しやすいように分割してるだけ
（集合内のfの和でgを定義してる）
このあたり確かに文章の流れがミスリーディングだね
公金の使われ方とか言って暇空は応援するのに
ロシアと強いつながりがある競技プログラミングコミュニティ
ロシア批判に消極的に見えるのは
>>535 今ホットなのは暇空の方だしなぁ
話題性のある方に言及するのは普通でしょ？
アルゴリズム実技検定 公式テキスト［上級～エキスパート編］
https://codeforces.com/gym/102978/problem/A なんか、こういう総数は簡単なんだけどもうちょい細分化したものを数えたいときに新しい変数とかを導入するテクニック的な
まあ情報増やす感じよね
さらに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やばそうな配点だ
C++17が多数派だと思うのですが
>>552 AtCoderなら、近いうちに言語アップデートが入るからそこで追加されるのでは？
>>553 そうなんですか？
知らなかったです
ありがとうございます
もしよろしければ言語アップデートのソース元ってありますか？
Bは面倒そうなので飛ばしてC
Eまで脳死で解いていく問題セットでしたね(´・ω・`)
Convex hull trickEDPCで調べたばかりだったのに存在を忘れてた
Fえらく簡単だなと思って実装してみたら想定の数倍厄介な問題だったな
>>555 基本的にはみんな普通に問題文読んでコード書いてるだけだ
極まってる赤色のひとだとこれぐらいの考察速度でコードを書く
（まあ、このひとに限っては更にコードゴルフもしてるからかなり変態っぽいけど）
VIDEO >>560 A問題ならまだ見て書くで分かる気がしますが
B,C問題をコピペじゃなくて1分,2分台で読んで書いてACって既に人間と思えないんですけど
上位様方達は凄いんですね
Bは読解めんどくさいけど、レ点の存在を知ってればだいぶ思考節約できるし、ある程度上級者ならソラで書いても1, 2分で解けるんじゃないか
C問題でACが28/29でREが1つだけ残ってて分からないのですが
コードのどこがおかしいか分かりますか？
テストケースが公開されていないので思いつかなくて・・・
自作関数などは省略してます
今回のGみたいな出現頻度低めの高度典型忘れた頃に出題されるから中々身に付かない
Exは除原理で立式して母関数使って整理するときれいな除算になるのか
Bってグラフの説明いるの？
厳密に書くにはあれが一番なのかもしれないが、それはそれとして、やる操作に対して記述量が多すぎて驚く
>>565 ありがとうございます
ヒントが冒頭って意味でしょうか？
ヒントじゃなくて頭が悪いってことならそのとおりなので異論はありません
>>563 vectorの宣言だけどvst(N)じゃなくてvst(M)にすべきなんじゃないか
逆にRE1個で済むんだな
>>570 ＞＞あたま
のヒントで気づいて
それでACなりました
思い込みと言うかこんな些細なミスに気づかずに1時間半も悩んでてて1完でメンタル壊れますね
確かにF青、G黄ぐらいが理想ではあるけど、一色上振れぐらいはいいんじゃないかな
来週またTOYOTAだからABCの難度壊されるのか
昔の企業コン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とか相当良くなるんじゃないかな
例の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問題かなんかだったが、解説でこのゆきこの問題と同じような感じで導出してた覚え
東大生が～とか中卒が～とか何を話すにもわざわざ学歴を書いてイキらなきゃいいだけだぞ
ガチのフルコミットする奴(子なし主婦やニート)が増えれば青＝東大の相場は崩れる気がする
青=東大なんて言ってるの学歴厨しかおらんよ
凄いのは凄いって言えばいいのに他所から「勿体ない」って言うのは傲慢よ
ABCの3完が精一杯でBやCが解けないこともたまにある灰色なのですが
何もせず稼げるとしてそれが嬉しいなら自分でやってみたらいんじゃね
某所で見かけた問題（どこの問題かは規約の関係で言えない）なんだけど、いくら考えてもわかんなかったから誰か教えてほすぃ
出展不明の問題には解答してはいけません
それがどこの問題か知ってるけどその問題を公開することは許されてるわけ？許されててもダメだと思うけど
マジか、伏せとけば大丈夫かと思ったわ
かなりムズい気がするな
そんなに難しくはないけど、確かに解答したくはないな……
Lは昇順にソート済みとする
>>618 シミュレーションの際に同じ値はまとめれば毎回最大値が1以上減るからステップ数抑えられるか
その間の算数はk個に操作するとして
k+max(m,ceil((s-x*k)/Y))
という式の最小化
面倒だから雰囲気だけだけど多分最小と最大とmaxの中身が丁度等しくなるとこくらいを調べれば十分なはず
>>606 レーティングって長期的推移でみるものだから高々1個実力外で稼げたものは所詮あぶく銭にすぎないしパフォ目的ならオススメはしないかな
チャレンジしたい！って心意気ならすご～くいいと思います
>>622 ARC過去問覗いて見てそっ閉じしました
問題文や解説すらさっぱり理解出来ないので
せめてA問題が理解出来るくらいまでは参加は諦めます
Cまではとっつきやすかったね
B問題は実家DP的ななにかを予想して遷移考えたけど、思ったより普通の算数で解けたな
>>624 見たぞ2
少なくとも3人factorioスレ見てるやつが居るな
寝起きでARCのA問題見たらちょっと閃いた気がしたので
2分はともかく、30分かけて良いなら解けなきゃダメだと思うよ
想像しているようなそっくりな問題を解いたことがあるみたいな話ではないけど（多分上位層は初見でも2分で解ける）、何個かの要素に分解できるところはあるかな
ある意味ARC典型みたいなところがあるかな
AはARC-Aに置かれてると条件は基本的にシンプルになるけどたまに場合分けを要求されるみたいな雰囲気を感じ取れる(いつかのこどふぉで全く同じコーナーケースに注意すべき問題もあった)し、Bも条件の厳しいものからあらかじめ決めておいて残りは重複組み合わせ等で簡単に処理するっていう考え方をARCで何回か既に見たからARC典型みたいなのは問題を解き進めてるうちに身につくと思う
>>634 貴重な情報ありがとうございます
ARC-Aクラスの難易度はまだ無理ですが
ABC-Cならなんとか解けることもあるので
＞＞問題を解き進めてるうちに身につく
ことを信じて自力で解ける範囲で少しづつやってみます
緑だけどARCは不出場になった、青以上じゃないと時間の無駄になる気が
昨日のC、類以度いくつ達成できそうかは手元で実験してすぐ分かったけど、
類以度が2以上になるのはどういうときかを考えたら思い付いた
パスの場合1通りしか答えないからその理由考えて適当に一般化
パス上でオリジナルの数字とPで変換して出てくる数字で被りがあるとうざそう→適当に木を二分割して移し替えればよくね？→頂点数の偏りが少ない分割がほしいから重心を使う
400点のARC-Aは厳しい問題な可能性が高いな
Eまで早解き出来てFもO(N)で求められる式の導出までは出来たのにそこからの式変形がダメだった 勿体無い
Gは貪欲でよさそうなことにさえ気付ければ実装も楽でかなり解きやすいな
Fもいわゆる自明な上界問題っぽいし、今回も結構ARCチックだった
Gの貪欲が証明できん
俺も証明してない
F非想定解とはいえ畳み込みやらFPSやらをやればO(N)の式を高速化出来たっぽいしちゃんと履修すべきだったな
DのサンプルだけACしたけど
知識を取り入れてABCでレート上げるのはARC/AGCでレート上げるより楽なので、どんどん高度な知識を取り入れていいと思うな
>>652 Dは典型ではあるからこれを機に知っておくといいと思うよ
(N/GCD(N,D))*Dで初めてNで割ったときあまり0のところに戻ってくる
こういう操作はかなり頻出だと思う
OEIS使う裏技は知ってたけどwolfram alpha使う裏技もあるんだな
ありがとうございます
D、解説が難しいし何の役にも立たないので理解する気力がわかない・・・
wolfram alphaを使うプレースタイルだとΓ(1/2) = √πみたいな知識も役に立つのかな
Dは例えばN = 15, D = 6としよう
>>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が無くなるってことはどういうことなんでしょうか？
すべてありえそうだけど最大の理由は「そもそも採用に力を入れていない」でしょうね
>>679 なるほどですね
昨年からだと世界的に数十万人レイオフですか
上位数%の優秀な人しかいらないってことなのかな
コロナ禍にIT投資が過熱して採り過ぎちゃったし
寂しいけどGoogleがもう普通に兢プロに価値見出してないだけだと思うよ
フレームワークとライブラリが充実してきたので
ARCギャンブル初参加して約50分くらいでまぐれのA解けてラッキー
C、Bよりも簡単だった気がする(Bは罠が多すぎてWA複数回踏んだ)
普段のARCと比べると解きやすいが、AとBはコーナーケース踏んで死んだ
Cの解法は典型的な思考法ではあるが、典型のテンプレ持ってるから解けるみたいな話じゃないぞ
>>687 おっしゃる通りでございますね
解説見て無理だと悟りました
これはどんなに勉強しても理解出来るレベルに達する内容じゃないです
解説見て理解出来ないんだから本番で思いつくはずがない
やっと入茶出来たみたいです
writerの人の印象から勝手にグラフアルゴリズムや最適化回になるかと思ったけど、数え上げメイン回だった
>>691 おめでとう
典型パターンに習熟していないうちはARCの方がパフォーマンスが跳ねやすいと思う
鬼のように数え上げを出してくる某writer以外は出題分野そんな偏らない気がする
>>693 ありがとうございます
まぐれギャンブルで貰った+60なので
ABCずっと参加してC落としたりすればすぐに適正に収束すると思いますので
400切らないように頑張ります
>>695 今日のA解けたんならABC-Cは慣れれば安定して解けるようになると思う
Bの全てXかつK=0のケースが3つも入ってるっぽいんだけど注意力勝負すぎるしK>=1でも良かっただろとは思う
>>697 ありがとうございます
色々な勉強法あると思いますがマイペースが大事ぽいので
ストレスにならない程度に気長にコツコツやってみます
前半はコーナーケースを詰める力そのものを聞いてるんだろ、それ無かったらやるだけだし
シンプルな問題設定と非自明なコーナーケース、もはやARC典型
2、3分でスモールテストケースでの愚直実験一通り回せるぐらいの腕力が欲しいところだな
ABC3完は出来ましたがみんなAC速すぎてパフォーマンスが出ないですね
Fまでの早解きゲーになっちゃったけどF1100人近くも通すもんなんだな
Exでこんなにきれいに重心分解がそのまま出るとは意外だった
Gの方が考察の難易度的に難しいと思うけど、重心分解は知識レベルとしては高度という判断なのかな
今回のFはEと同じくらいの難易度だな
>>704 Dはかなり典型的なDPの問題だから類題はたくさんあるけど、Cより解きやすくなるってことはない気がするかなあ
まあでも問題の相性はあるからね
こんなん重心分解でしかないやろで投げたけど、ちゃんと証明してなかったな
>>709 そうなんですね
DPはチラ見したことありますが数問やって全く理解出来なかったので保留してます
まだ累積和とか二分探索すらよく分からないので鉄則本が全然進まない状態です
気長に理解できそうなとこからやってみます
xorやandやorの相互変換もたまに効く典型の印象
>>711 EDPCというコンテストの一番簡単なやつから理解していくのがいいかな
DPは慣れるまでが結構難しくて、慣れたらABCだとそんなに頭使わなくて済むようになる
D問題最初誤読して「全てのカードの表面に書かれてる数が異なる」って思って一瞬焦ったけどこの場合も解けたりする？既出っぽい気もするけど
>>713 ありがとうございます
今やりかけのもの終わったらまた少しDP覗いてみます
>>715 とりあえずグラフを考えて、カードをA_iとB_iをつなぐ辺とみなす
このグラフの各連結成分を見て、なもり木なら閉路部分の割当で2通り、木になってるんなら木DPでうまく数え上げて、それ以外は0通りみたいな感じにして、総積を取る感じか？
なんか既出感がすごいな
>>717 カードの表裏をグラフの辺に帰着させて連結成分ごとに頑張るみたいな考え方で確かに出来そうだし典型的な考え方な気もするからこの設定の場合もABC-E、Fくらいに置いてあれば違和感無いな
今回はABC-Dだったからすぐ誤読に気づけたけど
Fで出て青diffのどこかって雰囲気の問題に見える
DP練習問題などいくつか試してみましたがほとんど理解出来ませんでした
解説を見ても理解できないDP練習問題ってなんだ？気になる
「判りませんでした。私は頭が悪いです。わーんわーんわん」って泣き言いう前に分からないとことか問題を貼ろう
多分初めのうちは、どういう時にDPを使ったら良いのか分からないって感じだと思うんだけど、
DPは、状態をまとめて管理したり、操作した結果部分問題に帰着するって考えるとわかりやすいと思う
EDPCはHがクソ簡単だからそこから始めるのも手だと思う
>>726 EDPCだとA～Iまで試してみて自力で解けたのはCとHの2問だけでした
他の練習問題などでやった記憶があってそれをコピペしたら動いたってだけでした
なので何故そのようなDPを組んで正解が出るのか理解してるとは言えない状態です
つまりEDPCほぼ全てで解説を見ても理解できないということです
>>728-730 丁寧なアドバイスありがとうございます
せっかく丁寧なアドバイス頂いていて恐縮なのですが
このカスなに被害者ぶってんだろね
喧嘩するなって
このスレの荒らしは高度アルゴリズム関連を一切呟かず、延々と他者を下げるから分かりやすいのよな
貰うってf(x)をaだけ平行移動するとf(x-a)的な添字の難しさを感じる
自分も「貰うDP+累積和」よりも「配るDP+imos法」の方が添字ミス減る気がする
俺はプログラマだから、DPは順番が違うだけでメモ化再帰とほぼ同じ、ってのが最初にしっくりきたな
俺も再帰でシミュレーションすれば答出るけど時間足りないって時に
自分は更新順序とか何の値が既に確定してなくちゃいけないかとかを考えるのがだいぶしっくり来たかな
基本は漸化式(特に受験数学の確率漸化式)みたいな気持ちだけど更新順序が非自明な時はメモ化再帰でやると楽みたいな
EDPCで初見で解ける問題があるだけ上等じゃねえの
vscodeがバグってて何も出来ない
幾何が分からなさすぎてExに逃げてしまった、競プロ脳……
Cは典型でしょうか？
結局6完
Gみたいな細かい要素はそんなに難しくないけど複合してめんどくさくなってるタイプのDP好き
>>751 何か二つの積がN以下みたいな条件の時に、片方は√Nまでしか探索しなくて済むというのはかなり頻出の典型だよ
Eは推移閉包の問題だったけど、これに関連する発展的な話題で思い出すのはDilworthの定理かな
C問題、手元で動かしてみたら明らかに2秒越えてるのにダメ元で提出してみたら500msで通った
A * Bの結果を数え上げておくとN - (A * B)を利用してすぐ答えがでるからそう解いた
今回のDiff体感よりも0.5～1色低いくらいな気がするんだけどやっぱり環境が整ってきて参加者の実力がインフレしてるのかな
挫折して離れる人がいて
ぶっちゃけそれはあるよね
うわあ～
>>764 灰色→茶色は努力でなんとかなると信じてやってますが
それすら厳しいかもしれないんじゃないかなと思い始めています
そんな卑屈になることはないと思うけど、コーディング環境とかの問題は再発防止して平均的なレートを上げていこう
＞＞再発防止
最悪に備えてエディタは2つは用意しておくといいかもね
繰り上げり連絡きたけど最高でも6完までの人がToyotaコンの決勝に行ってもいいものかしら
ホモじゃないんだなァ……
というかパフォ予測渋いけど前みたいにバグってるだけだよね？
やっぱりMoやるだけだと、かなりの人が解けるようになってるな
D,方針はすぐわかったけど色のインデックスつけたグラフを探索して１時間以上通せなかったり罠が・・・
Dは色いらんのかーい！ｗってところが逆に解きづらい可能性がある
全く使わない入力がある問題を見たのはABC126以来かな
こどふぉとかだとまあまあ見かける気はする
本番ではCをDPだと思い込んで苦戦して結局時間切れのAB2完で-4ポイント
>>792 > DFSとbitとnext聞いたことあるけど本番で実装に使うという発想が湧かないのが痛い
全探索の時はその2つを真っ先に思い浮かべればいい
C問題までは計算量考えない全探索でほぼほぼ行ける
問題をたくさん解くというのはこういうことを学ぶことで別に別にたくさん解かなくても学べる
今日は2つ学んだから成長したぞ
今まで時間内に解けなかったC問題がいくつか解けるようになったはずだ
制約から全探索が間に合うかどうか確認しておくといいよ
>>793-794 ありがとうございます
このスレにいる方って本当にポジティブな方が多くて励みになります
>>794 Cでアップアップしてるやつにそれができないことを知りながら誰でもできるみたいな感じでマウント取るんじゃねえよ寒色のくせに
>>792 今回のC問題みたいなのについてはテンプレ化は難しいと思う
とはいえ、DFSによる全探索は大体どれも似たようなパターンでは書けるから、何個か類題解いてみて自分に合った型を身に付けられるといいかな
ChatGPT昨日の問題全部解きやがった
どこまで行っても補助輪がついてる競プロ界の中でテンプレがどうこう言う話なのかなあ？
テンプレというか、この手の移動が「W-1回の右移動とH-1回の下移動」の順列と一対一対応するのが典型では（ABC034-C とか）
ありがとうございます
>>797 これを機会にDFSに触れてみます
>>800 本質を言語化して頂いて助かります
B問題未証明で適当に通した人多そうだしあまり好きじゃない
DFSで解けるらしいというヒントだけで初見のC問題をDFSで実装して解けたけど4時間半掛かりました
解説ACするかは、記憶力に自信があるかじゃないかな
明らかに向いてなさそうだが競プロやってる理由はなんなんだ？
この界隈、全体的にネット上の立ち回りが下手くそ
おぼえると言う意味が分からない
293C、どうやって書いてもREが出ます。
ここが次スレということです
ここはガイジスレの次スレって聞いたんですけどガイジがいないように見えます
>>810 サンプル以外全部REってレベルで通らないときは、自分で適当な入力を手で作ったりランダムな入力を生成するプログラムを書いたりしたら手元で再現できる確率が高い
>>810 HとW間違って配列外参照してないか確認してみるとか
サンプルはH=Wしかないし
>>817 これをまともだと思ってるやつがいるあたりこっちも相当ヤバい
制約から全探索が間に合うかどうか確認しておくといいよ
Cすらできない初心者に言うならどう見ても煽りだろw
C問題辺りからループの計算量を把握する必要がある問題が出始めるのでC問題で苦戦している層に対してのアドバイスとして1文目はまぁ妥当
Cでアップアップしてるやつにそれができないことを知りながら誰でもできるみたいな感じでマウント取るんじゃねえよ寒色のくせに
C問題ができないってことは灰色だぞ？
当然って言い方そもそもしてないだろ...
当然って言い方そもそもしてないだろ...
マウント、とか寒色のくせに、とかは大抵自己紹介だから、つまり煽りカスなんでNGしておくと良いぞ
効きすぎて笑う
やっぱこれくらい殺伐としてないと居心地悪いわ
つーか携帯回線と家回線切り替えたくらいで自演に望むなよ
ﾜｯﾁｮｲ←回線会社固有、回線ごとに変化しない
あとsoftetherを使うと5-ipくらい併用できるからもっと自演できるぞ😉
ﾜｯﾁｮｲの仕組みすら知らないのを見るにどうせ普段から例のID無しスレで自演してるような奴だろうし相手にしなくても良いよ
もしかしてお前の言う自演って、wi-fi使える場所と使えない場所でワッチョイ違うこと言ってんの？
まぁそれはどうでもいいとして
>>830 に反論くれや
>>848 自演君何言ってんのw
お前がアオラーだってことは証明されたじゃん
まだ言い逃れできると思ってんのヤバくね？w
俺が馬鹿になればなるほどみんな理知的で輝いてるように見える
アオラーっていう謎造語言い出して話がどんどん自演と煽りの方向に行ってるけど俺の主張は最初から794は悪意的に解釈されないってだけだけど
ガイガイガイガイガイガイガイガイガイガイガイガイ
早稲田大学 Twitter名さかえまな atcoder 名 na_kombu 真中紗枝
早稲田大学 Twitter名さかえまな atcoder 名 na_kombu 真中紗枝
競プロスレなんてレートが高い方が正義だから、レスバで勝ちたかったらレートの高さを証明すれば終わりなんだよな
会場のSSID、4.2Ghzと書き間違えてるのを二重線で消して2.4Ghzに書き直してて草
数百人もいるのに無限に飲み物食べ物が補充されるのが太っ腹でいいね
競プロやってる知り合いもいないしイベントも興味ないから辞退したけど飯だけ食いに行けば良かったか
今回Gまで簡単というか典型めで良かったけどオイラーツアーのライブラリ持ってなくて一から書いてたら橙パフォ逃しちゃった
Gはかなり既出感の強い問題だからね
Ex、指数時間アルゴリズムのスライドに何か載ってないか探しに行ったけど、特に収穫はなく
Fは例の食塩水の問題が結構印象に残ってたからすぐ方針に辿り着けたけどABCだとやっぱりほぼ既出問題ばかりになるから精進が大切だな
Eでバグりまくって見てなかったFやったら5分で解けた…
multisetを使うDがレート380とか信じられないんだけど・・・
>>885 multiset使わなくても解けるよ
ACしたほとんどの人使ってないんじゃない？
Eまでほぼ愚直に実装する問題だったのはだいぶ珍しい気がする
WA出しまくりの6完ですわあ...(´・ω・`)クエリ処理で前も同じミスしたのよね
もともと寒色になんの価値も無いのでGPT使われようがなんの問題もないね
GPT4で5完水パフォか
https://qiita.com/autotaker1984/items/2929937cd1fea6137d1f AtCoder終了のお知らせ
前回は質問を工夫して何度かやり取りと手直ししたら3.5でも一時間で7完だったからお前らよりよほど優秀
優先度付きキューとか今日日灰色でも標準装備だろうし余裕でAIに指示出せるな
寒色diff程度の簡単めな問題なら解法分かってる状態で質問繰り返してしかも手直しまでしたら解けるに決まってるんだよな
GCJとTCOが終わったり、ABCで大半のユーザがAIに負けるようになってもまだみんながんばってね
灰とか茶の人が実際に使ってみたレポートが欲しいんだけど、自分がガチでやるより良い成績が出る可能性があるとなるとなかなか使いたくないのかな
AGCのA安定して解けるようになったらヤバいけど考察不得意そうだからまだ大丈夫そう
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回読むか小学校からやり直せよ
レスバしたいだけのｱｳｱｳｳｰの人、結構みっともないからやめた方がいいよ
ほんと、そういうくだらないのはツイッターでやれよな
すまん
誰かどの辺が間違ってるか教えて
総当たりして誤るテストケースを自分で見つけるスキルを身につけることも重要
ありがとうございます
コンテスト開始前に突如延期は酷いやサーバーの問題だから仕方ないけど
おそらくGTPにヒューリスティックを除くatcoder的なスキルはほとんど使われていない、使われてるのはニューラルネット、内積、最適化、強化学習など。何故か整数ばかりのパズル最適化は見当違いも良い所。
役に立つと思ってやるもんじゃないって既に無限回言われてるだろ何を今更
AtCoderJobsのランクがほぼ無意味になるな
>>926 > ニューラルネット、内積、最適化、強化学習
この並列笑えるな、内積はセンスある
競プロ以前に高校数学すらまともに勉強してなかったんだろうな
>>930 トランスフォーマーの核なので強調してみたのじゃｗ
>>931 DSだけどどう温かい目で見てもABCの問題の大半は役に立たない。ガチ。
お前がディープステートだったのか
内積でqueryとkeyのある種の類似度を計算して重みとして利用するのはそうなんだけど、まず磨くようなスキルではないのではないかという
問題
質問です
自分でテストケースを作成して色々とやって見たのですが上手くいかないです
>>937 全然ちゃんと確認してないんだけどj-A[i]で範囲外参照してそう
環境にもよるけど、 #define _GLIBCXX_DEBUG を入れると範囲外参照関連のデバッグはしてくれるから便利だよ(実行時間が遅くなる場合もあるから提出する時は外れるようにすると良い)
まあこういう遷移はめちゃくちゃ良くあるし慣れたらデバッグしないでも殆どミスらなくなると思う
>>939 ありがとうございます。
Ai＞jであるときとそうでないときで場合分けしたら上手く出来ました。
>>940 ありがとうございます
elifの部分もまちがえていましたか
配列外参照の仕様に関してはまだちゃんと理解していませんが、939のレスをヒントにして解決することが出来ました。
質問
コード1
コード2
l*A[i]がlong longの最大値を超えてオーバーフローするのでは
今度からChatGPTに聞けよ
別に元々質問が多くて困っているようなスレではないし、ここで聞く分には構わないと思うけど、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の原因なんだから、制約も、その制約によってオーバーフローするようなコードを書いたことも、それぞれ原因と言っても別にいいだろ
アホなのか？
ほんとに何言ってるのかわからんわ
何言ってるのかわからんのは自分の頭が悪いからと早くきづけるようになれるよう祈ってるよ
まあ要するにお前の言語能力は原始的なAI以下ということだ
読解力でAI未満てそれ何ならAIに勝てるの？
暴れてる奴もChatGPTなんだ怒らないでやってくれ
そんな賢くないだろw
日本語の言語能力が低く日本人にとってはありがいんだろうな。
チョクダイが焦ってるけどAIの流れとまらんだろ
コーディングテストとしてjobsに関係ある層がほぼ消えるワケじゃからのぉ、ワシもrated参加はやめるのじゃ
集合でラッセルのパラドックスを考えるガイジも集合しろ
教プロはもうおしまいです
ちょくだいの最近の投稿見ると焦りが隠しきれてないな
ライト層はAIで良いじゃんってなるから競技人口増えなそう
ボケ防止としてはかなり有用じゃ、コンテストの体がないとやる気がせん
老人ってドーパミンがあんま出ないんじゃない？
A～E5完
Eそんなに難しいか？と思ったけど、確かに微妙に典型度低いかもしれんな
3000人も解けてるけどこのD相当難しい、GTP4も解けてなかったし
B4乗ループ最初は思いつかなくて面倒そうだなって思ってchatGPTに投げたら全然違うプログラム書いてきてキレてた
>>998 同じくDで爆死。数字ごとのパリティまでは
気がついたのだが、長さNのビットベクトル
を10個作ってなんとかしようとしてしまった。
縦と横を入れ換える頭の柔軟性がなかった。
このスレへの固定リンク： http://5chb.net/r/tech/1672026457/ ヒント： 5chスレのurlに http ://xxxx.5chb .net/xxxx のようにb を入れるだけでここでスレ保存、閲覧できます。 TOPへ TOPへ
全掲示板一覧 この掲示板へ 人気スレ |
Youtube 動画
>50
>100
>200
>300
>500
>1000枚
新着画像 ↓「競技プログラミング総合スレ 65 YouTube動画>1本 ->画像>7枚 」 を見た人も見ています：・競技プログラミング総合スレッド@数学板 競技プログラミング総合スレ 66 (478) 競技プログラミングにハマるプログラマのスレ 195 競技プログラミングにハマるプログラマのスレ 69 競技プログラミングにハマるプログラマのスレ 62 競技プログラミングにハマるプログラマのスレ 64 競技プログラミングにハマるプログラマのスレ 45 競技プログラミングにハマるプログラマのスレ 85 競技プログラミングにハマるプログラマのスレ 95 競技プログラミングにハマるプログラマのスレ 205 競技プログラミングにハマるプログラマのスレ 35 Windows Azure プログラミング 総合スレ2 (99) プログラミング言語ランキング総合【TIOBE】 プロトコル ネットワークプログラミング質問総合 競技プログラミングについて語るスレ 競技プログラミングにハマるプログラマのスレ ヒッキーの競技プログラミングするスレ 3完 競技プログラミングにハマるガイジのスレ 94 競技プログラミングにハマるガイジのスレ 93 競技プログラミングにハマるプログラマのスレ 31 競技プログラミングにハマるプログラマのスレ 92 競技プログラミングにハマるプログラマのスレ 28 競技プログラミングにハマるプログラマのスレ 38 競技プログラミングにハマるプログラマのスレ 33 競技プログラミングにハマるプログラマのスレ 93 競技プログラミングにハマるプログラマのスレ 184 競技プログラミングにハマるプログラマのスレ 213 競技プログラミングにハマるプログラマのスレ 194 競技プログラミングにハマるプログラマのスレ 98 競技プログラミングにハマるプログラマのスレ 41 競技プログラミングにハマるプログラマのスレ 57 競技プログラミングにハマるプログラマのスレ 81 競技プログラミングにハマるプログラマのスレ 82 競技プログラミングにハマるプログラマのスレ 83 競技プログラミングにハマるプログラマのスレ 73 競技プログラミングにハマるプログラマのスレ 89 競技プログラミングにハマるプログラマのスレ 58 競技プログラミングにハマるプログラマのスレ 99 競技プログラミングにハマるプログラマのスレ 76 競技プログラミングにハマるプログラマのスレ 78 競技プログラミングにハマるプログラマのスレ 39 競技プログラミングにハマるプログラマのスレ 77 競技プログラミングにハマるプログラマのスレ 40 競技プログラミングにハマるプログラマのスレ 80 競技プログラミングにハマるプログラマのスレ 97 競技プログラミングにハマるプログラマのスレ 83 競技プログラミングにハマるプログラマのスレ 26 競技プログラミングにハマるプログラマのスレ 51 競技プログラミングにハマるプログラマのスレ 46 競技プログラミングにハマるプログラマのスレ 87 競技プログラミングにハマるプログラマのスレ 88 競技プログラミングにハマるプログラマのスレ 70 競技プログラミングにハマるプログラマのスレ 54 競技プログラミングにハマるプログラマのスレ 84 競技プログラミングにハマるプログラマのスレ 128 競技プログラミングにハマるプログラマのスレ 133 競技プログラミングにハマるプログラマのスレ 199 競技プログラミングにハマるプログラマのスレ 161 競技プログラミングにハマるプログラマのスレ 167 競技プログラミングにハマるプログラマのスレ 14 競技プログラミングにハマるプログラマのスレ 178 競技プログラミングにハマるプログラマのスレ 153 競技プログラミングにハマるプログラマのスレ 157 競技プログラミングにハマるプログラマのスレ 130 競技プログラミングにハマるプログラマのスレ 166 競技プログラミングにハマるプログラマのスレ 17
01:31:38 up 65 days, 2:30, 0 users, load average: 7.95, 8.99, 9.41
in 0.080188035964966 sec
@0.080188035964966@0b7 on 062114
