◎正当な理由による書き込みの削除について： 生島英之とみられる方へ:
競技プログラミング総合スレ 66
動画、画像抽出 ｜｜
この掲示板へ
類似スレ
掲示板一覧 人気スレ 動画人気順
このスレへの固定リンク： http://5chb.net/r/tech/1679465982/
ヒント：5chスレのurlに http://xxxx.5chb.net/xxxx のようにbを入れるだけでここでスレ保存、閲覧できます。
!extend:checked:vvvvv:1000:512
!extend:checked:vvvvv:1000:512
!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/ ※前スレ
競技プログラミング総合スレ 65
http://2chb.net/r/tech/1672026457/ VIPQ2_EXTDAT: checked:vvvvv:1000:512:: EXT was configured
VIPQ2_EXTDAT: checked:vvvvv:1000:512:: EXT was configured
優勝ですと言いながらSNSに食べ物の写真を上げるのは面白いと思ってやっているのですか
d問題パリティと言われてみればなるほどだけど
2500人も解けてるの凄いなぁ…
凄いというより、みんなatcoder特有のノリに慣れてきただけとしか思えない
トップ層で今回作問に携わってないのに「崖ができるのは解けないユーザーが悪い」とか言ってマウント取るのなんなんだろ
ABCでE~F黄diffなら不満出るのは必然だし正当では
本当にトップ層かどうかは置いといてTwitterの競プロ界隈()なんてそんなもんだから気にしなくて良いでしょ
崖があるとパフォーマンスの計測が微妙になるから好ましくないことではある
今回のAのFA gpt使ったコードなんだね
その人1分以内でAとCACしてるしCまでで問題文が簡潔だったら任せても良さそうな感じか
Cまではもう諦めるとして、D-FでGPTでACを避ける作問をするとより難しくなるんじゃないだろうか
どうせチョクダイここ見てるんだろ
問題文を画像で提供すればキーボードを叩く時間がかかるからAIの爆速解答は防げる
視力障害の人も防いでしまうから読み上げ音声も同時提供だな
動画ならなお良し
アプリ作成にはアルゴリズムだけじゃなくこういうソリューションも必要だぞ
あと読み上げはすぬけ君がボソボソ言うんじゃなくその辺の安い声優やVtuberに頼むか音声合成な
何も反論できなくていつもの瀕死の人格攻撃
悔しそうで草
やっぱ自分でも無理筋だと分かっているしょうもない暴言でレスバがしたいだけのやつだったか
無理筋じゃなくて裏筋刺激してよ、(*´Д`)ﾊｧﾊｧ
効いてて草
論破されて悔しいのにまったく反論できないってどんな気持ち？w
AIやばすぎて今のトップレベルはともかく始めたやつとか茶緑あたりはやる気なくなるんじゃないかこれ
これからのプログラミングはペアプロになるだろうからatcも許容すると思ったけど、コーディングテストで価値があるのがCくらいまでなのと、そこまでは絶対手動でかけるべきだから、画像とかにするんですかね。
最近、スクショどころかカメラで撮影しても全く映らない動画とかあるし。
その理論だと将棋とか誰もやりたがらない気がするけどそういうのあったんすかねやっぱ
画像になったらここでそれを否定した無能がどう発狂するか楽しみ
数え上げ方はかなり典型的だけど一昔前なら水色下位くらいはあった気はする
競技プログラミング（主にatcoder）で計算量を問われず無視できるならその問題のレベルどれくらい落ちる？
色一つ下になるくらい？
計算量無視して良いなら全問題が茶色以下だと思うが、そういう話ではなく？
>>35 つまり計算量無視ならatcoderの問題はどれも実装は簡単てこと？
計算量で難しくしてるようなもんてことになんの
愚直全探索でいいならほとんどの問題は茶色ぐらいの実装ゲーになりそうだね
他は知らんがatcoderは計算量削減が全てのゲームじゃないの？
実装ゲーもあるが、指数時間や階乗時間計算量許してしまうと大体根底から問題が破壊される気がするな
中高大学受験生様の息抜きとしてもアピールしたいから実装系問題が増えるのはNG
ほぼ愚直全探索で間に合うみたいな実装系メインの問題は基本茶色以下になるけど、再帰とかバックトラックDFSとかが絡んできて問題も面倒だと水色程度にまではなるかな
無限が出てくる期待値 mod 系はどうしようもないことがありそう
それこそ e とか
確率問題はそれこそモンテカルロで無限の精度を出せないか？
無限の時間がかかるけど、計算量無視していいから余裕だし
よく考えたら無限回の確率 mod 998244353は無理だったわ
そういうのはdiff高いな
まあ答えが単純な有理数で分母の大きささえ評価できればその理屈は成り立つな
e は p+q/e+r/ee とかいう形してるから一筋縄ではいかなさそう
連分数的な計算できたりするのかな
近頃のお店の支払いはif文が100個ぐらいありそう
支払い方法が何十通りもあるし
組み合わせて支払えることもあるし
ポイントの付き方とか複雑だし
ABC168C問題について質問
中心角を求めてから余弦定理を使うところまではわかったんだが、肝心な実装ができない
このコードの問題ってどの辺かな
テンプレは省略しています
#include<bits/stdc++.h>
using namespace std;
int main() {
ll A,B,H,M;
cin>>A>>B>>H>>M;
ll m=5*H;
ll l=min(abs(m-M),60-abs(m-M));
if(l==30){
cout<<A+B<<endl;;
return 0;
}
if(l==0){
cout<<abs(A-B)<<endl;
return 0;
}
dl pi=acos(-1);
dl ans=sqrt(A*A+B*B-2*A*B*cos((dl)l/30*pi));
printf("%.12lf\n",ans);
}
ありがとうございます
短針のずれを考慮して実装し直します
iqが低すぎてそこまで頭が回りませんでした
無事実装できました
やっぱり競プロはIQゲーだと思います
そうだよ、IQゲーだよ
というか算数のパズルだから、中受してるひとが有利
だから上位者は筑駒や灘だらけだろ
はーい、ガイジのみなさん、こちらに集合してください
おれも競プロのおかげでイベルメクチンを使ってコロナを乗り越えることができたわ
G問題、凸包の上側と下側を抜き出すのにかなり時間がかかってしまったね
ライブラリ化してもいい気がする
ゴリってワクチン打ってない陰謀論者なのに、飲み会に呼ばれるしオンサイトにも出てるんだ。羨ましーーー！
GPTはそのうち画像や音声データも読み込めるようになるって既に発表されてるぞ
今日のこどふぉで「放物線と直接が共有点を持つかは判別式の正負で判定できる」っていう受験数学典型が出題されたけどこんなものも出るんだ 懐かしい
むしろ競プロは受験数学の知識だけで解けるべきじゃない？
ワーキングメモリが足りなくて再帰で複雑なことされると理解に時間かかるんだけど、皆さんなにか工夫してます？
あんなの慣れだろ
まぁ、細かい事言うと描く対象が木の時はこんな感じグラフの時はあんな感じみたいな
数列の漸化式みたいに一定の公式みたいのあるんだけどさ
atcoderでおかしいと思うのは、Dまでで再帰の出現頻度が異常に少ないこと。
最後に見たの半年以上前なような。
アホみたいに単純になりがちなのと、中高生が取り組みにくいのが要因か。
あ、ごめんDまででってことか
わけのわからん制限つけるね
再帰で解けるものは山程あるのに使ってないってだけだろ
再帰呼び出しじゃないがi++は再帰的な式と言えるかな
むしろ再帰は慣れるとワーキングメモリが少なくても書ける部類のコードになる
関数の引数に対する処理と、終了条件の二つに気をつければいいだけ
全体像を追うんじゃなくて、あくまでもその関数を一回実行したときの処理だけ考える
木がBSTか判定するコードなんですけど、こういうのって頭の中で全部イメージできます？
このロジックも自分で初見では組めなかったんですよね
def validateBST(root):
def isValid(root, minVal, maxVal):
if root is None:
return True
if not (minVal < root.data < maxVal):
return False
return isValid(root.left, minVal, min(maxVal, root.data)) and isValid(root.right, max(minVal, root.data), maxVal)
return True if root is None else isValid(root, -float("inf"), float("inf"))
知的障害とかおありでしょうか？わかりますよ？
<=のほうがよくね、minとかmaxは余計だね、とか
ある頂点に対して、2つの子それぞれを根とする部分木の情報が定まってれば、その頂点について簡単に判定できる
数学的帰納法の考え方というか、局所的には簡単な処理できるってことがわかるとそんなに大変じゃなくなる
>>89 より良い書き方があるならコード見たいです
Pythonだと慣れてるので嬉しいです
ガイジ同士仲良くしろよw
仲良くしようと頑張ってそれなのかw
>>94 minとかmaxって関数のことですよね？
これないと上位ノードより大きい値が左の下位ノードに存在することを許しちゃいませんか？
もしかして自演でやり取りしてるんじゃないかと思うくらいどっちも頭悪いな
if not (minVal < root.data < maxVal):
return False
がある時点で明らかにその下の行では
min(maxVal, root.data)) == root.data
じゃない？
>>98 leetcodeにもそういうコードありました
もう一回やり直してみます
ありがとうございました
余計なものの中に最後の一行についての言及がないということは二人()ともあのif文は要ると思ってるんだろうな
>>103 あっそっかぁ……
二分探索木判定とかしたいときあるか？
>>106 平衡二分木の実装をデバッグする時くらいかな
たしかに最後のifもいらねーじゃん
ガイジが集まれば強力なガイジになれそうだな
ガイジは低レベルなところでワヤワヤやってただけだろw
まずお前は素人の質問を見てマウント取らないようにするところから始めたらいいと思うぞガイジw
誰でも見た瞬間わかることをさも有能ムーブで語るのは流石に見てるだけでイタいから
毎日壊れたレコードみたいに戯言つぶやいてないでガイジスレに帰れよw
お前らもこっちきな😘
あっちは何を書き込んでもいいぞ🤗
幅優先探索の計算量が O(N + M)（N は頂点数, M は辺数）ですが、
N と M は異なる種類の変数です。
計算量は、 O(N + M) ですと言われてもピンときません。
普通は、 N << M だと思うので、 O(M) でいいような気がします。
例えば、連結グラフの場合、 N - 1 ≦ M ですよね。
辺が重複しない、という前提を入れるならそうですよね
O(N + M) ですと教えてもらって何が嬉しいですか？
この情報をどう利用しますか？
計算量の話をする時って何も断りを入れなければ最悪計算量か平均計算量に決まってるのに普通じゃない時の話を持ち出してるのはどういう人種なんだ
すまん、明らかに間違ったことかいてたわ
辺が重複しないじゃなくて、連結グラフという前提ならそうですよね
計算量の話って
満足な時間内にできるかどうかの議論でしか役に立たないよね
かかる時間が見積もれると嬉しいだろ
O(M)でないものをO(M)って書いていいことにはならないけど
幅優先探索はそもそもΩ(N+M)なケースが無いと思うからO(M)って書いて欲しいが、N=O(M)は自明じゃないと思うぞ
N頂点0辺のグラフだってあるし
すまん嘘書いた
幅優先探索って最初に距離配列を作るからO(N+M)で合ってたわ
チョクダイ毎日AI下げしてるな、これくらい上流層でも脅威なんだな
赤レベルが解けるようになるのは10年以上かかるだろうけど、
コーディングテストとして売り物になる層はすでにほぼ終了だし、E,Fまで解けるようになったらほとんどの参加者の自力解答は無意味ということに。
GPT前提の問題作りか、時間をかけた試行錯誤は苦手だろうからヒューリスティック重視とかになっていくんじゃないだろうか。
ヒューリスティックもある程度のレベルまでは行きそうだけどな
24時間コードを書かせ続けることもできるし
始めて一年の茶色のおっさんだけどAIに負けるレベルになったと聞いてモチベだだ下がり。俺みたいなやつ多いと思うよ。
そりゃ参加者減ったら焦るわな
AIに負けるって言うがChatGPTは競プロ用にチューニングしたプログラミングAIじゃないぞ
こいつができるのは問題を読むことと何を求められてるかを把握すること
つまり日本語(あるいは英語)を読解するAIだ
要するに人類が負けてるのはプログラミング能力じゃなく読解力と記憶力なんだよ
今に見てろこいつらあらゆる分野でゲームと動画に浸かったお前らに国語力の差を見せつけてくるから
暖色レベルへの到達はあったとしてもかなり先だろうし競技としては成立するだろうけど緑～水色くらいなら近い将来到達しそうだし新規参入と寒色停滞勢の参加率は減るかもね
競プロってゲームでやってるのかと思ってたからAIに負けてやる気なくなるってのはよくわからん
ARC/AGCの中盤以降に競プロの本当の楽しさがあるという主張は否定しないが、ABCの前半も競技として楽しんでいた層の方がマジョリティで、そういう層が競プロの裾野を広げていた側面もあるから、コンテンツとしてダメージを受けざるを得ないと思うわ
企業もスポンサーをするのは基本ABCだし、Jobsで見られているのもレベル的にABCでの実力がメイン
>>146 競技を楽しんでるのに競技そのものが成立しなくなったら嫌だろ？
Project Eulerみたいな感覚で問題に取り組んでいるんなら大丈夫だが、そういう人は初心者層ほど少ない
>>148 他の人らがAI使って解答してるかもしれないと思ってしまうってこと？
>>149 バレる可能性が低く対策不能なチートが蔓延ったオンラインゲームは壊れるやろ
ただのオンラインゲームでさえそうなのに、一応AtCoderはJobsみたいな実利的に意味のあるものと繋がってるから、みんな使うようになるんじゃねーの
開き直ってAIバトルにしても、投稿速度ゲームになりそうだし
みんな使わないにしても、使ってるやつにレートを吸われることでモチベの減退はあるだろうな
>>150 まあそういう人はスポーツすればいいよ
アルゴリズム解くのが好きとか純粋に知識欲の高い人が残るんだろうね
>>152 その辺の人でも楽しめる競技になる道は閉ざされそうで悲しいな
元々運営にそういうモチベなさそうだったが（金のために仕方なくやってる感満載だった）
ノーレートで、食事したり飲みながら今までほぼ開かなかったF,GとかをchatGTPに聞いたり調べたりしながらやるのも楽しいぞい。解きたくない問題は解かなくても良いし。
ワーシャル・フロイドアルゴリズムについて質問です。
最終的に任意の2点間の最短距離を入れるための2次元配列は、
代入演算子の左右で共通のものが使われています。
それでも、問題がないのはなぜですか？
ワーシャル・フロイドアルゴリズムは、全ての頂点間の最短距離を求めるためのアルゴリズムです。このアルゴリズムは、動的計画法の一種であり、一度計算された結果を再利用することで、計算量を減らすことができます。
具体的には、アルゴリズムの初期段階で、すべての頂点の間の距離を表す2次元配列を作成します。この配列は、アルゴリズムの途中で更新されますが、代入演算子の左右で共通のものが使われるため、問題はありません。
なぜなら、アルゴリズムの途中で更新される値は、それ以前の値に依存しているため、代入演算子の左右で共通の2次元配列を使用していることによって、更新された値が正しく計算され、以前に計算された値が失われることはありません。
つまり、更新された値は、以前に計算された値に基づいて正確に計算され、以前に計算された値が配列内に保持され続けるため、代入演算子の左右で共通の2次元配列を使用することは、アルゴリズムの正しい動作に影響を与えないということです。
ものすごくもっともらしい嘘つくから知らないことを聞くのはおすすめしないぞ
ワルシャワ・フローラル法を知ってる？
はい、ワルシャワ・フローラル法は、グラフの最大マッチングを求めるアルゴリズムの一種です。このアルゴリズムは、ハンガリー人数学者であるエドモンド・ワルシャワと、ポーランド人数学者であるタデウシュ・フローラルによって開発されました。
ワルシャワ・フローラル法は、ハンガリー法と同様に、最大マッチング問題を解決するために使用されます。このアルゴリズムは、二部グラフに適用されます。アルゴリズムの基本的な考え方は、各未マッチング頂点について、その頂点を始点とする増加路を探し、その増加路に属する辺のマッチングを反転させることです。
ワルシャワ・フローラル法は、ハンガリー法よりも効率的であることが知られていますが、完全グラフでは最悪の場合の計算量がO(n^4)であるため、実用的ではありません。しかし、一般のグラフに対しては、最大マッチングを高速に計算することができるため、実際には広く使用されています。
正確なことを答えさせるために、プロンプトエンジニアリングをがんばりましょうね
素朴な整数演算のコードを書いたため、特定のテストケースのときにコードの途中で
整数がオーバーフローするような場合、一般的なコードの書き方の処方箋みたいなものは
ありますかね
例えば「整数の配列から適切な要素を取り出して期待される和を作れ、そういう要素が
ない場合はエラー値を返せ」みたいので、配列要素はどれもオーバーフローに近い整数、
和は配列内の最小要素よりちょっとだけ大きい値（なのでエラー値の場合）、とか....
競プロならlong longを使うだけ
実務ならオーバーフローした時に例外が発生するようにしてそれをキャッチ
『アルゴリズム実技検定公式テキストエントリー～中級編』
最小全域木を求める、「プリムのアルゴリズム」について説明があります。
こうすれば、求まるという説明はあるのですが、なぜ求まるのかの説明がありません。
みなさんは、こうすれば求まるという情報だけで十分で、それで満足しますか？
それとも、ちゃんと証明まで自分で考えるか、誰かが書いた証明を読みますか？
>>163 なるほど。確かに例えば入力がintならlong longを使えばとりあえず大丈夫そう
ちなみにC++ですが、例えばintのオーバーフローを例外で処理するのはどうしたら....
C++でオーバーフローを検出する方法はいくつかありますが、一般的なものは以下のようになります¹²³。
- 演算前に範囲チェックを行う。例えば、a + b がオーバーフローするかどうかは、a > INT_MAX - b か a < INT_MIN - b で判定できる。
- 符号なし整数を使う。符号なし整数のオーバーフローは定義されているので、演算後に結果が元の値より小さくなっていないかチェックすればよい。
- boostライブラリのsafe_numericsを使う。これはオーバーフローを検出するための特別な型を提供しており、オーバーフローが発生した場合に例外を投げる。
(1) Detecting signed overflow in C/C++ - Stack Overflow.
https://stackoverflow.com/questions/3944505/detecting-signed-overflow-in-c-c アクセス日時 4/9/2023.
(2) c++ - How do I detect unsigned integer overflow? - Stack Overflow.
https://stackoverflow.com/questions/199333/how-do-i-detect-unsigned-integer-overflow アクセス日時 4/9/2023.
(3) c - How to check if overflow occured? - Stack Overflow.
https://stackoverflow.com/questions/7683685/how-to-check-if-overflow-occured アクセス日時 4/9/2023.
gccの__builtin_add_overflowとか__builtin_mul_overflowを使う
github.com/kenkoooo/pastbook-source-code/blob/master/chukyu/python/chapter06/section11/6-11-1.py
↑のファイルはプリムのアルゴリズムで最小全域木問題を解くコードです。
ファイル中の以下の箇所がなぜ必要なのかが分かりません。
一見すると、キューの中には、marked の値がFalseのノードしか入っていないように思うのですが、
実際には、Falseのノードも入ることがあるようです。（以下の箇所をコメントアウトすると
パスしません。）
# 辺につながる頂点 i もすでにマークされていた場合、
# 操作をスキップする
if marked[i]:
■■■■continue
一部、間違えましたので訂正します。↓
↑のファイルはプリムのアルゴリズムで最小全域木問題を解くコードです。
ファイル中の以下の箇所がなぜ必要なのかが分かりません。
一見すると、キューの中には、marked の値がFalseのノードしか入っていないように思うのですが、
実際には、Trueのノードも入ることがあるようです。（以下の箇所をコメントアウトすると
パスしません。）
# 辺につながる頂点 i もすでにマークされていた場合、
# 操作をスキップする
if marked[i]:
■■■■continue
この部分は、既にマークされた頂点に対応する辺をスキップするために必要です。
確かに、キューには基本的にmarkedの値がFalseのノードしか入らないように見えますが、
実際には同じノードに対して複数の辺がキューに入ることがあります。
例えば、次のようなグラフを考えてみましょう。
1 -- 2
| /
| /
3
各辺の重みはすべて1とします。最初に頂点1を選び、marked[1]=Trueとします。
次に、頂点1に隣接する辺をキューに追加します。
この時点でキューの状態は以下のようになります。
(1, 2), (1, 3)
次に、キューから最小の重みの辺を取り出し、それに接続されている頂点2をマークします。
頂点2に隣接する辺をキューに追加します。
この時点でキューの状態は以下のようになります。
(1, 3), (1, 1), (1, 3)
ここで、次にキューから取り出す辺が(1, 1)であることに注意してください。
ただし、頂点1はすでにマークされているため、この辺を使ってしまうと、最小全域木の条件を満たさなくなります。
これが、以下のコード部分が必要とされる理由です。
if marked[i]:
continue
この部分によって、既にマークされた頂点に対応する辺をスキップし、
正しい最小全域木を構築することができます。
ヒープにプッシュする前に、そのノードがマークされていないことをチェックしています。
ですので、ヒープ内には、マークされていないノードしか入れないと思うのですが。
>>171 あまり参考にならないだろうと思って読んでいたらなぜか理由が分かりました。
マークされていない状態で、同じノードが複数個ヒープに入ることがあるわけですね。
>>172 確かに、ヒープにプッシュする前にそのノードがマークされていないことをチェックしています。
ただし、ヒープにプッシュされた後で、そのノードが他の辺を経由してマークされる可能性があります。
そのため、ヒープから辺を取り出す前にもう一度マークされているかどうかをチェックする必要があります。
先程のグラフで考えてみましょう。キューがこの様になったところから解説します。
(1, 3), (1, 1), (1, 3)
ここで、最初に(1, 3)をキューから取り出し、頂点3をマークします。この時点で、キューには以下のような状態が残っています。
(1, 1), (1, 3)
次にキューから取り出す辺は(1, 1)です。この辺は、頂点1と頂点2の間にありますが、頂点1はすでにマークされています。
しかし、この辺をヒープにプッシュした時点では、頂点1はまだマークされていませんでした。
それが、例のコード部分が必要とされる理由です。
あの部分によって、既にマークされた頂点に対応する辺をスキップし、正しい最小全域木を構築することができます。
>>171 この場合でいうとノード3が2回ヒープに入るわけですね。
>>175 はい、その通りです。
最初にノード1からノード3への辺がヒープに追加され、次にノード2からノード3への辺がヒープに追加されます。
(1, 3) <-- 1から3への辺
(1, 1)
(1, 3) <-- 2から3への辺
このように、同じノードが複数回ヒープに入ることがあります。プリムのアルゴリズムでは、
すでにマークされた頂点に対応する辺を無視する必要があります。
そのため、ヒープから辺を取り出す前にマークされているかどうかをチェックする必要があるのです。
Eむずい
setとpriority queueいじくってたら通った
E二分探索でやろうとしたらハマって普通にsetで順番にみるだけだった
F解けたのに今回も解いてる人の数がF<Gなせいであまり順位伸びてないの配点何とかして欲しいわ
整数式の倍数判定のプログラム作りたいんだけどできる？
nは自然数
例1
入力:n(n+1)(n+2)
出力:6
(入力した式の倍数判定。6の倍数)
2の倍数でも3の倍数でもあるが、最も大きい数を出力
例2
入力:n^9-n^3
出力:504
>>181 nに素数をいくつか突っ込んだ値(0以外)で最大公約数とればいいんでない？
という気はするけど万年茶色脳には正しいか証明するなんてムリ
素数pの倍数かどうかはmod pが整域だから多項式は根を高々次数d個しかもたないのでp≤dだけ調べればいいよね
p^kはわからん
fが零因子⇔あるa≠0が存在してaf=0らしいから、最初にfを係数のgcdで割っとけば零因子じゃなくなって、p^k≤dだけ調べればいいと思う
mod p で何代入しても0になる多項式は例えば x(x-1)...(x-p+1) でp次を達成できて最適
mod p^n だとこれをn乗すると構成できるので（最適かは知らんが）pn次以下と評価できる
だからpnがd以下の範囲を探索すれば良いが計算量は悪いな
Fはやってみたら簡単に解けた
Gはgrundy数求めるとき単純な勘違いしてた
むー悔しい
DAGの最長パスを求める問題について質問があります。
『アルゴリズム実技検定公式テキストエントリー～中級編』に
「トポロジカルソート」の考え方が重要と書いてあります。
ですが、DAGがトポロジカルソートできるということを使っている
箇所が見当たりません。
載っている解法は、indegreeが0である頂点からの最長パスをDPにより求めるというものです。
確かに、その解法ではトポロジカルソートを明示的に実行していないように見えますが、
実際にはトポロジカルソートの考え方が含まれています。DAGの最長パスを求める際、
トポロジカルソートの概念が重要なのは、頂点の順序付けによって依存関係を解決することができるからです。
その解法で、indegree（入次数）が0の頂点からDPを用いて最長パスを求めています。これは、各頂点について、
その頂点に入ってくる辺がなくなる（依存関係が解決される）順序で処理を行っていることを意味します。
この順序付けがトポロジカルソートの結果と同じです。
indegreeが0になる頂点から処理を行い、その後、処理された頂点から出る辺を削除することで、
indegreeが0になる頂点が次々と現れます。この手順は、トポロジカルソートを実行する手順と同じです。
したがって、トポロジカルソートを明示的に行わなくても、その考え方が解法に含まれているため、
問題を解決することができます。トポロジカルソートの概念は、DAGの最長パス問題を解く際の重要な考え方であることがわかります。
DAGであれば、最長パスが存在し、それはDPで求められる。
ただそれだけのことではないでしょうか？
はい、おっしゃる通りです。DAGであれば、最長パスが存在し、動的計画法（DP）を用いて求めることができます。
繰り返しになりますが、トポロジカルソートの概念を用いることで、DAG内の頂点の順序付けが可能であり、
この順序付けに従ってDPを適用することで、最長パスを求めることができます。
DAGにoutdegreeおよびindegreeが0の点が両方とも存在することは、自明です。
もしそのような点がなければ、閉路が存在することになるからです。
トポロジカルソートなどという考え方を持ち出すまでもありません。
トポロジカルソートを明示的に実行しなくても、DAGの最長パス問題をDPで解くことは可能です。
ただし、その際に頂点の処理順序や依存関係の解決が重要となるため、トポロジカルソートの考え方が役立ちます。
トポロジカルソートを適用したDPでは、頂点の依存関係が効率的に解決されるため、計算量はO(V+E)です。
ここで、Vは頂点数、Eは辺数です。トポロジカルソートによって得られた頂点の順序に従ってDPを行うことで、
各頂点と辺に対して一度だけ計算が行われます。
一方、トポロジカルソートを適用しないDPでは、無駄な計算が発生する可能性があります。
例えば、メモ化再帰を用いたDPの場合、計算量は最悪O(2^V)になることがあります。
これは、全ての頂点に対して、それぞれを含むか含まないかの選択肢があるためです。
>>181 多項式 f(n) について計算したい
calc(f) で求めたい値を返す関数として
f が定数ならそれを返す
定数でないなら g(n)=f(n+1)-f(n)
とgを定めて
calc(f) = gcd(f(1), calc(g))
を計算すればいい、再帰の深さはfの次数で抑えられる
『アルゴリズム実技検定公式テキストエントリー～中級編』に載っている
DAGの最長パスを求めるコードでは、トポロジカルソートを陽には使っていないです。
その本持ってないからその本の解法教えて
そしたら質問の回答するよ
>>197 ソースコードは以下です：
github.com/kenkoooo/pastbook-source-code/blob/master/chukyu/python/chapter06/section04/6-4-8.py
確かに陽にトポロジカルソートはしてないね
値が確定する順序がトポロジカルソート順の逆順にはなってるけど
多分、以下のようなことを言いたいんじゃないかな
・各頂点の値を一つずつ順に確定していって、
・一度確定した頂点を再度訪れる必要がない
・そのようなことが可能な確定順が存在する
確かに考え方によっては自明とも思えるかもしれないけど、逆にそれくらいのことしか言ってないということでは
この問題の場合はメモ化再帰でトポロジカルソートを使わなくても計算量はO(N+M)です。
頂点間に循環がないため、再帰の深さが頂点数Nを超えることがなく、
各頂点に対して rec 関数が最大1回しか呼び出されないからです。
トポロジカルソートを使ってそのコードを書き換えるとこうなります。
https://ideone.com/1NbHIf >>199-200 ありがとうございました。
>>200 コードを見たのですが、
# トポロジカルソートで得られた順序に沿って最長経路を更新
for u in order:
for v in edges[u]:
length[v] = max(length[v], length[u] + 1)
の「for u in order:」でなぜ良いのかが分かりません。orderの要素を後ろから見ていかなければ
ならないように思ったのですが、そうではないのはなぜでしょうか？
for u in order:
■■■■print(u)
とすると自分が思っている順序とちょうど逆順で表示されます。
order.append(u)
を実行すると order の最大インデックスの要素の次に u が挿入されますよね。
そうだとすると、 order[0], order[1], … は queue から出てきた順に並べたものになりますよね。
多分、単純な勘違いなんですが、どこを勘違いしているのかが分かりません。
あ、分かりました。
与えられた有向グラフの辺の向きをすべて逆にしても、最長パスの長さは変わりませんね。
以下のコードは全く無駄なことをやっていますが、自分の理解通りなのはこちらのコードです：
ideone.com/gMUZDZ
すまん初めてこのスレ来たんだけど連投してるやつはネームド？
>>195 天才か
gcd(f(1),f(2),...)
=gcd(f(1),f(2)-f(1),f(3)-f(2),...)
ということか
確かに典型だが無限で思考がストップしてしまっていた
pythonで2分探索を行う bisect というものがあります。
bisect.bisect(l, a)
としたとき、 a in l であるかどうかも判定したいのですが、そのような関数は用意されていませんか？
自分で作るしかないですかね？
Pythonに2分探索で整列済みのリスト l に要素 a が含まれるかどうかを調べる関数はありますか？
もちろん、 bisect を使って、簡単に実装できますが、用意されている関数はないですか？
まあ、以下のコードでいいと思うのですが、車輪の再発明はしたくないですよね。
i = bisect.bisect_left(l, a)
if l[i] == a:
return True
else:
return False
今IT系とは全く別の職種だから転職したくてAtCoder始めたけど楽しいな
未経験で他職種に転職出来るのか分からんけど
>>216 2分探索することは確定でそこで発見できるのにそれに加えてわざわざ他の集合を使う意味とは？
>>217 最低緑以上になればJobsで転職できる可能性はあるが緑っていっぱいいるので年齢や運が絡むかもな
>>219 ありがとう
数学好きでアルゴリズムも昔やったことあったから緑まではすんなりいけたわ
今は水色目指して色々やってるけどアルゴリズム的要素より数学要素のほうが多く感じるな
年齢は25だからあと3年位がギリギリかなあと思ってる
水より緑の方が採用しやすい
ほんとに転職したいなら水まで行ったらとか思わない方がいい
>>221 今年色々あって復職したてだから転職活動するなら来年以降かもしれんわ、一応ビズリーチとか登録はしたけど
水色より緑のほうが採用しやすいのはなぜ？
今から狂気プログラミング始めるならPythonでいいかな、
以下の問題ですが、パスするまでに1日かかりました。
atcoder.jp/contests/past202004-open/tasks/past202004_g
こういうアイディアはほとんど必要がないけれども、実装するのが大変という
問題の対処方法を教えてください。
1日かかって作成したコードは以下です：
ideone.com/NY8mNY
あ、模範解答を見たら、実装するのも実は大変じゃないんですね。
>>225 > こういうアイディアはほとんど必要がないけれども、実装するのが大変という
> 問題の対処方法を教えてください。
「アイデアを出すか頑張って実装する」以外の答えが思いつかんのだが真面目に聞いてるのか？
実装大変だなーと思ったら、自分のアイディアが悪いと思ってまず間違いないですか？
というのも、模範解答を見ると実装もシンプルな場合ばかりなので。
風向風速とかの簡単で面倒な問題も初期の頃はあったなあ
最近見ないけど無いと言い切る材料もない
中国にウクライナ侵攻関連で厚い助力を求めるようだな
台湾侵攻の際には、米軍を混乱させるためにロシアは北海道に、北朝鮮は南に牽制するという話もあったしそりゃそうだよな
https://www.bloomberg.co.jp/news/articles/2023-04-14/RT3MFKDWX2PT01 中国は、プーチン大統領が１年以上前にウクライナ侵攻を命じて以来初めて、国防相をロシアに派遣する。中ロの緊密な関係があらためて示唆される。
中国の李尚福国防相はロシアのショイグ国防相の招きに応じ、16日からロシア訪問を開始する。
ショイグ氏は李氏と軍事協力および世界や地域の安全保障について議論すると語ったと、ロシアの国営タス通信は報じた。
そうですか。中国やロシア、北朝鮮の動向は世界の平和や安全に影響を与える可能性がありますね。
最新のニュースによると、米国が中国の台湾侵攻を確実視しており、日本も中国と戦火を交える可能性があるという記事がありました。¹
また、安保理が18日に北朝鮮のICBM発射について緊急会合を開催することになりました。²
ロシアはウクライナ侵攻で敗色濃厚であり、北朝鮮の核ミサイル開発にも深刻な影響を受けているという記事もありました。³
これらの情報はあなたの興味に沿っていますか？
(1) 米国が確実視する中国の台湾侵攻、そうなれば日本も中国と戦火を ....
https://jbpress.ismedia.jp/articles/-/74803?page=3 アクセス日時 4/15/2023.
(2) 安保理が18日に北朝鮮会合 ICBM発射で日米欧要請.
https://www.nikkei.com/article/DGXZQOCB150XP0V10C23A4000000/ アクセス日時 4/15/2023.
(3) 敗色濃厚のロシア、北朝鮮の核ミサイル開発にも深刻な影響.
https://jbpress.ismedia.jp/articles/-/74792 アクセス日時 4/15/2023.
(4) [FT]北朝鮮、ロシアに急接近 中国の思惑から離反 - 日本経済新聞.
https://www.nikkei.com/article/DGXZQOCB120DR0S2A910C2000000/ アクセス日時 4/15/2023.
(5) ロシアと中国、北朝鮮情勢巡り緊密に連携 | ロイター.
https://jp.reuters.com/article/northkorea-missiles-russia-idJPKCN2LM1RV アクセス日時 4/15/2023.
(6) 「中露と北朝鮮がサイバー攻撃」初の名指し…自衛隊の防衛 ....
https://www.yomiuri.co.jp/politics/20210927-OYT1T50080/ アクセス日時 4/15/2023.
今回のABCレート不具合で変動なしらしいな
苦手分野過ぎてAとBしか解けなかったからありがたいわ
のんびり解いてた割には暖まるなあと思ってたけどこれDDoSの影響で普段速く解く人が遅れたってことか🥶
研究者が自分の名前を手法に付けることは、研究コミュニティで一般的には推奨されていません。ただし、研究者が特定の手法やアルゴリズムを開発した場合、その手法が他の研究者や専門家によって引用されることがあります。この場合、研究者の名前が手法に関連付けられることがあります。
どうしても自力で解けないなら解説読んでいいんじゃね
もし自分でアルゴリズム開発したらかっこいい略称付けたいよね
>>241 俺かよ
PriorityqueやSortedSetを使わずに普通の配列やSetを使って出力時に都度ソートしたら行けた
自前のライブラリだと重すぎるみたいだな
Aho, Hopcroft and UllmanのThe Design and Analysis of Computer Algorithmsという
非常に古い本はもうゴミのような本でしょうか？
>>245 Aho, Hopcroft, and UllmanのThe Design and Analysis of Computer Algorithmsという本は、1974年に初版が出版された古いテキストですが、ゴミのような本とまで言うのは必ずしも適切ではありません。この本は、コンピュータアルゴリズムの設計と解析に関する初期の基本的な理論と概念をカバーしており、多くの現代のアルゴリズムの基礎となっています。しかし、この本が初版が出版されてから約半世紀が経過し、その間にコンピュータ科学やアルゴリズムに関する研究は大幅に進歩しています。例えば、機械学習、データマイニング、並列化、分散システムなどのトピックが現代のアルゴリズム研究の重要な分野となっていますが、これらはこの本では扱われていません。
この本は古典的なアルゴリズムの理解には役立ちますが、より新しいアルゴリズムや技術の発展を学ぶためには、最近出版された書籍やオンラインリソースを利用することが望ましいです。例えば、Cormen, Leiserson, Rivest, and SteinによるIntroduction to AlgorithmsやKleinberg and TardosのAlgorithm Designといった現代のテキストは、最新の研究や技術を含んでおり、現在の学習者に適した教材です。
つまり、Aho, Hopcroft, and UllmanのThe Design and Analysis of Computer Algorithmsは、歴史的な価値があるという点でゴミのような本とは言えませんが、現代のアルゴリズム研究や技術を学ぶ上で最も適切な教材ではないかもしれません。学ぶ内容に応じて、より新しいリソースや書籍を利用することを検討してみてください。
アルゴリズムデザイン、重版されて書店に並んでて嬉しかった
ないのかあるのかどっちだと突っ込んでほしいジジイおるな
またUnratedやないか
誰やねんDDoSしてるやつ
こんなサイトにしても意味ないやろ
中国かロシアやろな
国がらみの可能性もあるから犯人探しは無意味
意図的に狙われてるのは確かだけどなんの目的で狙ってるんやろ
C問題なんだけど解説みたいに反転させる必要ある？
一つでも-が含まれてたらoの最大長答えるだけじゃない？
つまりn未満のoの最大長答えるだけでしょ
解答例のやり方だと反転の必要あるな
串が出てきて初めてansに入るから
反転させて2回チェックすれば団子判定をシンプルにできるって意図じゃないかな
-が入っていれば、oと-しかないのだからoは-と接してるわけで、oと-どちらかなければ-1、両方あれば連続したoの長さでいいんじゃないの？
久し振りにやったんだけど、
rated選んだつもりなのにunratedになってたんだけど、自分が選び間違えたの？
成績よくなかったからいいんだけど
質問タブに書いてあるけどDDOSのせいで全員unratedの無効試合になってる
>>268 それでもいいし解けさえすればそれでなくてもいいというだけの話
>>270 ありがと。
別にお酒に酔ってたわけじゃないのに、
なんで間違えたのかずっと悩んでたの
Cは正規表現で解けるな
肯定的先読み言明を使えば一回のマッチでいける
質問タブでアナウンス送るの、知らない人にとっては分かりづらい
Chatgptの影響ですでにレート出にくくなってるとかある？
GPTのおかげで誰でもCくらいまでは瞬殺できるし、緑茶らへんの人にとっては影響あるんじゃない？
茶色中盤くらいまではCまで早解きゲーだしまあ初心者は萎えるかもな
D - Find by Query
この問題の意味がわからない、運が悪いとACできないとか無いの？
10 ^ 6で試せる回数が20回だから二分探索しかないんだけどこういうメタ読み辞めたいんだよな
何なら序盤で出てくるインタラクティブ問題っていう時点でパターンが限られすぎてて8、9割二分探索(の類型)であることが推測出来る
>>276 必ず正しい答えを出すわけじゃないから自分で直せないとペナルティ食らうぞ
茶色だけみんなchatgptで序盤の問題解いてたのか
俺もそうしようかな
GPT使ってないからレートが低い、みたいなセルフハンディキャップはカッコ悪すぎるからGPTくらいは賢く利用しようね
A,Bの問題文を整形してChatGPTに貼り付けて反応もどってくるの待つより自分で解いたほうが速いわけ
更に投稿前にチェックも必要だし
嫁にそのやり方を教えてA,B問題の投稿を担当してもらってる間に自分はCあたりから手を付けるのほうがいいかも
>>287 そんな姑息なことをするほど、競技プログラミングで良い成績をおさめることにメリットはあるんですね。
>>287 APIあるんだから全部自動化するにきまってんだろ
5完しかできなかった
Dみたいなのが地味にめんどくさい
D問題昨日勉強した内容が出てきてめっちゃ嬉しかった
これ進研ゼミでやったことある状態だったわ
Gで解説と違う方針で通したから解説書こうと思ったが、一応C++でも通るか確認したらC++だとTLEだったのでやめた
C++遅いね
Patisserie ABC 3 出るかと思って過去問見直したけど全然出なかった
n次元直方体とは I = [a_1, b_1] × [a_2, b_2] × … × [a_n, b_n] の形の集合である。
n次元空間 R^n の部分集合 B で、有限個のn次元直方体の和集合であるようなもの全体の集合を C とする。
B1, B2 ∈ C であるときに、 B1 = B2 であるかそうでないかを判定してください。
↑自作の問題です。
この問題って効率的なアルゴリズムが存在しますか？
B1とB2の直方体の数が異なる場合、B1とB2は等しくない
B1とB2の直方体の数が同じ場合、B1とB2に含まれる直方体の番号を並べ替える
各直方体の対応する要素が等しくない場合、B1とB2は等しくない
すべての直方体の対応する要素が等しい場合、B1とB2は等しい
B1 が1個のn次元直方体からなる集合とします。
それを2つに分けた2つのn次元直方体の和集合を B2 とします。
B1 を構成する直方体の数は 1 です。
B2 を構成する直方体の数は 2 です。
ですが、B1 = B2 です。
B1 = [0, 1] × [0, 1]
B2 = [0, 1/2] × [0, 1/2] ∪ [1/2, 1] × [0, 1/2] ∪ [0, 1/2] × [1/2, 1] ∪ [1/2, 1] × [1/2, 1]
が入力として与えられた場合、 B1 = B2 です。
B1 = [0, 5] × [0, 5]
B2 = [0, 2] × [0, 1] ∪ [1, 4] × [2, 3] ∪ [2, 4] × [3, 4] ∪ [0, 1] × [2, 4] ∪ [2, 4] × [0, 2] ∪ [0, 2] × [1, 2]
B1 ≠ B2 です。
>>301 訂正します：
B1 = [0, 4] × [0, 4]
B2 = [0, 2] × [0, 1] ∪ [1, 4] × [2, 3] ∪ [2, 4] × [3, 4] ∪ [0, 1] × [2, 4] ∪ [2, 4] × [0, 2] ∪ [0, 2] × [1, 2]
B1 ≠ B2 です。
そんなことよりn乗で増えていくのを抑えないと無理なんでは
2次元限定、座標は有理数限定にしたら、競プロの問題として成立しますか？
>>307 そういうサイトがあるんですか。
a, b を実数とする。
a ≦ b とする。
[a, b], [a, b), (a, b], (a, b) を区間という。
d 個の区間 I_1, …, I_d の直積 B := I_1 × … × I_d を R^d の直方体という。
B_1, …, B_k を互いに共通部分のない R^d の直方体とする。
E = B_1 ∪ … ∪ B_k
とする。
i ∈ {1, …, k} とする。
B_i を含む E の部分集合の中で最大の直方体を求めよ。
この効率的な解法はありますか？
よくわからないけど [0, 1) の最大の区間は存在しないんだけど大丈夫そ？
攻撃を受けてもratedという前例ができたのはよかった
>>294 女性だよ
検索したら本名とか出て来ると思うけど
>>315 Youtubeで本人の歌声も聴けるしな
パフォーマンスがinfinityになった回って61以前にあった？
やっとE問題解けるようになってきた
E問題って一個一個の実行時間が長いんだな
競プロ有段者(強い人)に質問
Atcoderで一段階上に行くためには解説を何も見ずとも解けるレベルの一段階上を同じように解けるレベルになるまでその問題を解説だけ見て実装は全て自分で、っていう感じでひたすら練習していくっていうやり方は有効？
自分の場合はD問題は9割ガタ解けて、Eがまだ実戦では歯が立たないレベル
某所で「左右がバランスした括弧の列を生成する」という問題があり、解答が
void parenthesis(int l, int r, string& s, vector<string>& ans) {
if (l + r == 0) {
ans.push_back(s); return;
}
if (r < l) return;
if (l > 0) {
s.push_back('(');
parenthesis(l - 1, r, s, ans);
s.pop_back();
}
if (r > 0) {
s.push_back(')');
parenthesis(l, r - 1, s, ans);
s.pop_back();
}
}
（呼出の例） vector<string> ans; string s; parenthesis(4, 4, s, ans);
この if (r < l) return; が左右のバランス（単に'('と')'の数が同じというだけでなく）の条件に
効いているようですが、ピンとこないのです... 確かに正しい括弧の列のとき、それが成り
立つのはわかりますが、逆にそれがバランス条件を満たすのに十分であるというのが
どなたかわかりやすい説明はないでしょうか
しょーもない処理を複雑に描いてるだけのクソプログラムやな
この関数は最初の呼び出しでlとrが同じ数字なるよう入れるのが前提で
r<lの条件は例外処理みたいなもんやろ
このコードの一部 `if (r < l) return;` について説明します。
ここで `l` と `r` はそれぞれまだ追加できる '(' の数と ')' の数を表しています。なので、このチェック `if (r < l) return;` は、')' の数が '(' の数より少なくなる場合、すなわち、開き括弧より閉じ括弧が少なくなる場合を防いでいます。
正しい括弧の列を生成するためには、2つの重要なルールを守らなければなりません：
1. 左括弧と右括弧の数が等しいこと
2. 任意の時点で、右括弧の数が左括弧の数を超えないこと
1つ目のルールは、左括弧と右括弧を同数だけ生成すれば満たされます。しかし、2つ目のルールはもう少し注意が必要です。それは、どの時点でも、閉じ括弧の数が開き括弧の数を超えてはならないからです。これを超えてしまうと、括弧の列が無効になってしまいます。
例えば、"())(" のような列は、開き括弧と閉じ括弧の数は同じでも、2番目の閉じ括弧が開き括弧を超えているため、無効な括弧の列となります。
だからこそ、`if (r < l) return;` のチェックが必要なのです。これにより、閉じ括弧の数が開き括弧を超えるような状況を防いでいます。これは、まだ追加できる閉じ括弧の数 `r` が、開き括弧 `l` より少なくなる場合、すなわち、閉じ括弧が開き括弧を超える可能性がある場合に、そのパスをすぐに終了させることで実現されています。
(を+1)を-1と対応させて累積和が常に非負っていうのがバランスしていることの必要十分条件であることを認めれば if(r < l)return; がそれの言い換えなことは明らか
証明したければ累積和が0になるところで文字列を分割して、それぞれの文字列の一番外側の括弧を取り外すとネストが一つ浅いものに帰着できるからネストの深さで帰納法を回すみたいなことを気をつけてやるといいんじゃないか
>>329はChatGPTなのかな? すごいな
>>330 どうもありがとうございます
このコードの場合、再帰時に常に右側に括弧を追加することが if (r < l) return; で
必要十分になることの前提だと思うんですが....
>>329はそのことがうやむやのような
>>327のコードとは別に、
(と)をそれぞれn個使う正当な括弧列をレベルn(L=n)の括弧列と呼んだとき、L=nの括弧列から
L=n+1の括弧列はどう生成されるのかを考えてみたのですが
例えばL=2の()()はL=1の()の右か左に()を追加した、考えてみます
L=3の((()))はL=2の(())に ( + (()) + ) とした、と考えてみます
このように「全体を()で囲むか()を追加するかのルール」でいけるのかと思いきや
L=4の(())(())がL=3のどれからどう作られるのか、がよくわからず
( + ())(() + )ができたらいいのですが ())(() はL=3の正しい括弧列ではない
例えばL=3の (())() に (()) ( + () + ) と、括弧を割り込ませる? なんだかおかしい?
あるいはこれはL=2の(())を二つ並べた、と考えるべき?
要は、正しい括弧の追加操作のみをして再帰的に括弧列を生成することは可能なのか?
あるいは単にすべてのパターンを生成して正当でないのを刈り取ることしかできないのか?
などということが気になったのですが
>>332 結論から言うと、それは難しい問題であり、一般的なアプローチでは、「全てのパターンを生成し、
それがバランスの取れた括弧列であるかどうかを判定する」という方法が用いられます。
しかし、バランスの取れた括弧列を生成するための一種の再帰的なパターンは存在します。
それは、大きさnの全てのバランスの取れた括弧列を生成した後で、その各々に対して以下の操作を行うことです：
1. '(' + P + ')' を追加する
2. P + '()' を追加する
3. '()' + P を追加する
ここで P は大きさnの任意のバランスの取れた括弧列です。
この操作を行うと、全ての大きさn+1のバランスの取れた括弧列を生成することができます。
ただし、これは重複する列を生成する可能性があるため、生成された列は一意であることを保証するために
何らかの方法で重複を除去する必要があります。
したがって、厳密には「全てのパターンを生成し、それがバランスの取れた括弧列であるかどうかを判定する」
という方法とは異なりますが、これは一種の再帰的なアプローチと言えます。
しかし、これらのアプローチは計算時間やメモリ使用量の観点から見ると、
>>327に示されたDFSを用いたアプローチに比べて
効率的ではないかもしれません。また、DFSを用いたアプローチは明確に「正しい括弧の追加操作のみ」を行っていると言えます。
なぜなら、すべての括弧列を生成する過程で、同時にその列が正しい括弧列であるかどうかをチェックすることが可能だからです。
>>332 >>333 は嘘
バランスした括弧列の定義は全体を括弧で囲む操作と括弧列2つの結合で生成される集合だから、その()を追加するっていうのを右か左に追加するって意味だとするとレベル2以上の文字列同士の結合が考慮されていないの
で、(())(())が作れない
中に()を挿入することを許すとすると、今度は全体を括弧で囲む操作はいらなくなる
というのも、どんな空でないバランスした括弧列にも()の部分があるから、それを取り除くことを繰り返すことで空にできるから、逆に空文字列に()を追加していくことで任意のバランスした括弧列が作れるし、バランスした括弧列の任意の箇所に()を挿入した文字列もまたバランスした括弧列になっている
>>331 ご指摘の通り、このコードでは再帰的に右側に括弧を追加しています。具体的には、まず左括弧を追加し、その後で右括弧を追加しています。
この if (r < l) return; の制約は、この追加の順序に基づいています。開始時点では、開き括弧と閉じ括弧の数が等しく（つまり、l == r）、左括弧を先に追加します。そのため、追加の過程では一時的に l が r より小さくなります。しかし、その後すぐに右括弧を追加することでバランスを保ちます。
if (r < l) return; のチェックにより、右括弧が先に追加される（つまり、r < l となる）状況を防いでいます。これは、左括弧を追加した後でのみ右括弧を追加するという、このコードの括弧の追加の順序を反映しています。そのため、この制約が満たされない場合（つまり、右括弧が先に追加される場合）、そのパスは無効となり、すぐに終了します。
したがって、この if (r < l) return; の制約は、このコードの括弧の追加の順序に基づいて、左括弧と右括弧が正しくバランスを保つことを保証しています。
非負のランダムウォーク書いて+1-1を()に対応させるだけだろ
>>327 閉じ括弧が開き括弧より少なかったら、ダメってことなだけでは。
開き括弧と閉じ括弧の数が同じって条件は最初の呼び出しではlとrが同じでなければならないって制約があると思う
6完…
途中まではいいペースもFで帰りがけにも頂点集合受け取るの忘れて時間ギリギリに
>>337 例えば())(()は閉じ開きの括弧数だけでいうとおkだけど実際にはおkじゃない
では何故これが生成されないか、他の駄目パターンもなぜ生成されないか気になった
というのを既に考察したつもり
しかし、解く時間が限られている場合にグダグダ悩んでいる暇はないよなあ
そういう場合パターンを覚えておくしかない?
atcoderがddos受けてるとして、潰して得をするのは誰だ？
10:10くらい？から今(10:50)までずっとatcoder開けませんが、同じ人いるかな
なんてツイートしてるひともいるね
このコードがaws環境でsegmentationfaultになる原因わかる人いる？
ちなみにatcoderではこのコードでACを取れたので致命的な間違いがあるわけでは無さそう
int main(){
ll n, q, dp[39][100009], A[100009];
cin >> n >> q;
rep(i, 1, n) {
cin >> A[i];
dp[0][i] = A[i];
}
rep(i, 1, 29){
rep(j, 1, n){
dp[i][j] = dp[i-1][dp[i-1][j]];
}
}
rrep(i, q){
ll x, y;
cin >> x >> y;
ll cur = x;
Rep(j, 29, 0){
if((y & (1 << j)) != 0) cur = dp[j][cur];
}
cout << cur << endl;
}
}
Twitterのpaizaの広告とかに必ず現れる
「入力値をチェックしていない」
という返信をつける人は、具体的に何をチェックして、どう処理するの？
たとえば、
・Nは偶数
・AとBの合計はN未満
といった制約は、実際のプログラムならチェックして例外をスローする
しかし、
「nが整数値じゃない場合をチェックしていない」
みたいなよくわからない難癖をつける人もいる
整数値じゃなければint型にパースするときに、ほとんどの言語で例外になるからいいのでは
>>355 ll で dp[39][100009], A[100009];
何バイトあるん
コンテスト初参加
C問題があまりにも酷いと思った
20分くらいかけて、priorityqueue<pair<double、int>> に値をプッシュする時にpairのsecondの方にマイナスを付ければ良いことに気がついたもののWA
何を試してもWAで、doubleの精度に問題があるんじゃないかと思って、ネット検索をしたら、long doubleという型があることを知り、試してみたら無事AC
Ｃ問題で時間とメンタルを削られてD問題は諦めた
初参加とはいえ茶パフォはあまりに脳障害すぎるだろ
今回のＣ問題でpriorityqueueを使ったんだけど、priorityqueue<pair<double、int>> に値をプッシュする時、pairのsecondの方に-をつけて取り出す順番を工夫するのって典型？
ちょっとした閃きだけど思いついた時は俺ちょっと頭いいんじゃねって思っちゃった
その後ものの見事に脳障害っぷりを晒してしまったけど
マジレスすると符号付けて逆順にすることで実装をシンプルにするのはかなりの典型です
むしろそのマイナスにするのが主題と言ってもいいくらい
C++ってFraction無いんだっけ？
まあ無くても自分で通分すれば済む話だが
なるほど、ただの典型だったか…
ただ、その典型を自分で思いついたのはちょっと嬉しい
先程 D問題をACしてきた
結構簡単だし、C問題を普通に解けていたら多分四完出来た
今回のC問題みたいに本質的じゃない部分(long doubleという型を知っているかどうかみたいな)を問うのは本当にやめた方が良いと思う 問題の質がシンプルに低い
小数の精度についての理解を問うなかなかの良問だと思ったけどね
浮動小数点数での出力を求められていない場合に浮動小数点数を使うのはアンチパターン
分数を管理する構造体を持ち出したり適切な比較関数を書いたりして対処するべき
前回のC問題はただめちゃくちゃ面倒なだけでアレだったけど今週のC問題は何も悪くないし非本質的でもないだろ
浮動小数点数は誤差に気をつけるべきなんて競プロでは身につけておくべき典型知識だし競プロ外でも浮動小数点数の仕組みは知っておくべきだしm
強いて言うならlong double型で無理矢理通すような解答を弾けるような設定にして比較関数やら有理数型を表す構造体やらの整数しか登場しなくて誤差の心配がない解答のみが通るようにしてほしかったがCでそれは酷かもしれない
long double使わなくても解けるし、それ知らないと解けないと言ってる人のレベルが低すぎるだけ
E問題の意味が分からないんだが。
俺の考えたアルゴリズムは、
Mが0,1,2になる数、
Eが0,1,2になる数、
Xが0,1,2になる数、
を全て数えて
各組み合わせ27通りについて、
mex×場合分けの数
っていうやり方をしたんだがサンプル3の問題からしてそもそも合わない
日本語下手で説明難しいからコードを見てほしい。
https://atcoder.jp/contests/abc308/submissions/43167367 このやり方がなぜいけないのかわからない
コンテスト中「E問題いけるやん！」と思ってただけに絶望だったわ、はぁ。。
関係ないけど、dictのkeyで回せば
if k not in dic["X"]:
continue
みたいなのいらなかったな
雑なやり方だけど、
「E」に来た時点で、それより前のMの各012の数と
それより後のXの「012」の数を保持しておけば簡単に解けたわけか
Cみたいなのが普通に小数にしてソートして解けないとか、現実的に不要な精度を求めてるからじゃ。工夫して分数を比較とか一般的なプログラミングではあり得ない。
一切の誤差が許容できないケースは業プロでもあり得ると思う
普通に業プロでも浮動小数点の誤差でやらかすのあるあるだけどな
とくに一致判定しだすと大抵はテストを通って後でトラブる
むしろ業プロはバグだらけで運用でカバーするのが当たり前だか？
バグなくなるまでQAとデバッグしてたらいつまでたっても終わらない
>>381 あり得ないのは誤差があることを知りながらdoubleを使うことだぞ
誤差が許容できないとわかってて整数で誤差のない計算ができることもわかってるんだから整数で計算するべき
わかってないお前が無能というだけ
しかし、スポーツとかゲームの勝率を管理するシステムがあったとして、
小数点以下6桁以上の精度のために内部的に分子分母を整数で別々に保存してるとは思えないのだがｗｗｗ
思えよw
勝ち数と試合数を保存してるに決まってるだろw
逆に勝率だけ保存してその後の試合の結果どうすんの？w
過去の勝率からどうやって現在の勝率を計算するんだよw
それは当然してるけど、orderbyで引き出すときに、勝率をatcoder流でソートするとか多分ないｗ
ワテが知らないだけで分数流ベイズ統計学とかあるのかｗ
>>390 n 試合後に
現在の勝率 R(n)「だけ」が判っている場合
n+1 試合後の勝率 R(n+1) は
n+1 試合目の勝ち負けが r (勝ちなら 1 負けなら 0) とすると
R(n+1) = (R(n) x n + r) / (n + 1)
で良いんじゃね
もちろん誤差は蓄積するよ
こんなこと一々描くのも恥ずかしいレベル
>>394 そのnは試合数じゃないのかw
こんなこといちいち書かせるなよw
もう少し比較条件が複雑化されて
operator<なりstd::sortに渡すラムダ式をちゃんと定義しないと駄目なら一転して教育的とかいいそう
昨日はABC三完
今日はARCゼロ完
A問題は解けそうだったけど結局最後までAC出来ず
頭が悪すぎる
IQ1しか無いよ俺は
・解説開くとTwitterに飛ぶやつあるが、アカウント持ってないから見れない。
・今日のARC出題者はPCT。何千人の大人が高校生の手の上で転がされていると思うと笑える。
大人は経験を積んでるから対応力があるわけで素の能力的には筋力でも記憶力でも計算力でも高校生くらいがピークだろ
ずっと数学に取り組んできた高校生が年食ったにわかより数学力高いのは何もおかしくない
コードクイーンの足切りライン調べたら女性率わかりそう
高校生の茶パフォ、大人の緑パフォが通過してるのは観測した
CodeQUEENの予選通過ボーダーは4000位くらいか
決勝が200人だから、予選参加者の女性率は1/20くらい？ 意外と多い
普段よりは多いはずだしmaxで5%って少なすぎでは
明日ICPC国内予選で、紙デバッグのためにソースコード印刷できる環境を作りたいんだけど、どういう方法で印刷するのがおすすめ？？
できれば関数とか変数に色ついた状態で印刷できるのがよくて（結局白黒印刷でそこまで判別できないんだろうけど……）、コマンド一発とかだとさらに嬉しい。
ubuntu on wslで、C++のコードを印刷する予定。
>>413 エディタでスクショ撮って印刷すれば？
それかSlidesCodeHighlighter
関数とか変数のfontを変えればいいんじゃないの?
終了ぎりぎりにしか参加できなかったけどEなんでこんなに少ないの
処理水放出にブチ切れた某国のハッカーがDDoS攻撃をエスカレートさせるか？
次回ABCに注目！
Haskellで競技プログラミングやってみたい
過去問解答つきのコンテストかオンラインジャッジって何がある？
マ板は落ちてるし、ここも調子悪いし、Xより先に5ch終わってもおかしくなさそう
talkのパソコン一般か、ム板の二択になるのかな？
ガイジのみなさんのご来訪を、本スレ民一同心よりお待ちしております
chokuから青でカンストいただきました
青agerが一歩リードか？
このまま5ch潰れてもいいから一緒にXも閉鎖してくれ
これでネットも平和になるしみんなの幸福度も上がるだろ
[クライシスアクター」「豊島保養所」←画像検索＆拡散！
他スレに丸ごとコピペよろしっくっ！！
ネットでできる反ﾚﾌﾟﾃｨﾘｱﾝ・反ｲﾙﾐ活動です！！！！！
動画サイトのコメ欄もねらい目だぞ！！！！！！！
健全にアルゴリズムの議論が行われるこっちの方がいいね
緑はセンター300点レベル
緑は境界知能レベル
緑は社会不適応者
abcってcまでは名前ついてるアルゴリズムは絶対不要でしょうか？
世の中IQなの？
おれwais検査の結果IQ119だった絶望
赤マスさんみたいな脳がほしかった
また本スレの時代が帰ってきたな
もうここだけでいいよ
忌み数字を踏ませる業者、アプリ、コンピュータプログラムの嫌がらせ
動画再生回数、表示回数、登録者数、フォロワー数、評価数、コメント数、レベル、経験値、ポイント、HP、通貨、価格、メッセージ数、通知数、フレンド数
4（死）、13（キリスト教における忌み数字）
18（嫌）、24（〜に死）、34（〜さん死）
40、42、44
56（殺）、64（無視）
71（無い）、74（無し）、79（無く、亡く）
84（〜は死）、94（〜君死）、96（黒）
このような数字と名前や生年月日、IDなどを組み合わせて執拗に強調することで、精神攻撃をする業者やストーカー、嫌がらせ組織がキモい。
lud20250206010524このスレへの固定リンク： http://5chb.net/r/tech/1679465982/
ヒント：5chスレのurlに http://xxxx.5chb.net/xxxx のようにbを入れるだけでここでスレ保存、閲覧できます。
TOPへ TOPへ
全掲示板一覧 この掲示板へ 人気スレ |
Youtube 動画
>50
>100
>200
>300
>500
>1000枚
新着画像
↓「競技プログラミング総合スレ 66 」を見た人も見ています：
・競技プログラミング総合スレ 65
・ヒッキーの競技プログラミングするスレ 3完
・競技プログラミングにハマるプログラマのスレ 72
・競技プログラミングにハマるプログラマのスレ 52
・競技プログラミングにハマるプログラマのスレ 9
・競技プログラミングにハマるプログラマのスレ 85
・競技プログラミングにハマるプログラマのスレ 92
・競技プログラミングにハマるプログラマのスレ 17
・競技プログラミングにハマるプログラマのスレ 110
・競技プログラミングにハマるプログラマのスレ 112
・競技プログラミングにハマるプログラマのスレ 18
・競技プログラミングにハマるプログラマのスレ 27
・競技プログラミングにハマるプログラマのスレ 68
・競技プログラミングにハマるプログラマのスレ 2 [無断転載禁止]
・競技プログラミングにハマるプログラマのスレ 5 [無断転載禁止]
・【IT】bitFlyerが競技プログラミングコンテスト「codeFlyer」を開催 ～年俸1,200万円オファーの可能性も
・競技プログラミングにハマるプログラマのスレ 30
・競技プログラミングにハマるプログラマのスレ 32
・競技プログラミングにハマるプログラマのスレ 29
・競技プログラミングにハマるプログラマのスレ (222)
・プログラミング言語ランキング総合【TIOBE】
・GUIプログラミング総合
・ラジオストリーミング総合スレッド
・【2018年】FA・ポスティング総合スレ 15
・【2018年】FA・ポスティング総合スレ 36
・【2018年】FA・ポスティング総合スレ 35【感想戦】
・【2018年】FA・ポスティング総合スレ 28【タテ読み日本一】
・野球はプロとアマで使う道具すら変わるお笑い競技w
・競技者が競技場から出ても続行するスポーツ(笑)はプロレスだけ
・英語のリスニング総合スレ 6
・新車販売台数ランキング総合スレ 174
・新車販売台数ランキング総合スレ 181
・プヲタが他競技の八百長を語るスレ
・【天候不順】北海道ツーリング総合スレ 17-12
・◇◇◇歯のホワイトニング総合スレ 18◇◇◇
・【軽自動車板】新車販売台数ランキング総合スレ 9
・【競技】全日本プロ選手権自転車競技大会
・ヒッキーのプログラミングするスレ 9 (旧 プログラミング雑談 in HIKIKO) [無断転載禁止]
・PCで出来る2Dシューティング総合スレ112
・【2020年】FA・ポスティング総合スレ5
・PCで出来る2Dシューティング総合スレ103
・自転車旅行・ツーリング総合スレッド Part93
・プログラミングのお題スレ Part19
・【2014年】FA・ポスティング総合スレ28【広島除外】
・シスメックス女子陸上競技部 part3
・プログラミングのお題スレ Part17
・プログラミングのお題スレ Part20
・プログラミングのお題スレ Part9
・【ポケモン】ポケットモンスターカップリング総合スレ10
・プログラミングのお題スレ Part15
・プログラミングのお題スレ Part16
・プログラミングのお題スレ Part12
・プログラミングのお題スレ Part11
・プログラミング学習サイトについて語るスレ
・Androidプログラミング質問スレ revision51
・Androidプログラミング質問スレ revision50
・陸上競技のランパン・ブルマ・スパッツフェチPART43 ©bbspink.com
・相撲ってしきたりから暗黙の了解とか言い出す所からほんと「ジャップの神が作りし競技」って感じだよな…
・【ポリコレ】女子スポーツ『身体は男、心は女性』のオカマ勢にトップを占拠されて女性競技者が終わる
・フィギュアスケートってフェンシングレベルの規模なのにメディアはさも世界的な競技みたいに報道してるよね
・【サッカー】＜日本代表＞ベネズエラ戦のチケットは完売！当日券の販売はなし。大分スポーツ公園総合競技場
・【全国高校駅伝】「ピンクの靴ばかり」と話題 記録更新支える「厚底」シューズ席巻 「経済格差が競技力の差になる」
・【五輪】張本勲氏「嫁入り前のお嬢ちゃんが顔を殴り合ってね。こんな競技好きな人がいるんだ」 入江聖奈のボクシング金メダルに★２ [シャチ★]
・【野球】＜ショック？＞ パリ五輪で“ゲーム"が公式種目へ野球が継続できない理由は世界的に競技者人口と観戦者人口が増えてない★2
13:27:35 up 63 days, 14:26, 0 users, load average: 8.28, 8.63, 8.66
in 0.088732004165649 sec
@0.088732004165649@0b7 on 062002
|
ブックマークへ