競技プログラミング総合スレ 66

2023/04/04(火) 20:39:40.28ID:L6sdRXYAr
>>103
あっそっかぁ……
二分探索木判定とかしたいときあるか？
2023/04/04(火) 20:43:03.69ID:/ayUyQoPa
>>106
平衡二分木の実装をデバッグする時くらいかな
2023/04/04(火) 21:14:56.40ID:t/xEUfRa0
たしかに最後のifもいらねーじゃん
ガイジが集まれば強力なガイジになれそうだな
2023/04/05(水) 07:32:45.91ID:xDsMBQrA0
ガイジは低レベルなところでワヤワヤやってただけだろw
2023/04/05(水) 07:51:29.52ID:V9g+Im060
きみはもしかして高レベルなガイジなの？
2023/04/05(水) 08:33:49.11ID:xDsMBQrA0
一人前にカチンときたか
2023/04/05(水) 08:39:59.26ID:YYcedFeHH
みんなガイジなんだから仲良くしようね
2023/04/05(水) 08:40:53.22ID:xDsMBQrA0
まずお前は素人の質問を見てマウント取らないようにするところから始めたらいいと思うぞガイジw
2023/04/05(水) 08:42:54.34ID:xDsMBQrA0
誰でも見た瞬間わかることをさも有能ムーブで語るのは流石に見てるだけでイタいから
2023/04/05(水) 09:11:39.70ID:kAD3is4b0
効いてて草
2023/04/05(水) 09:13:29.61ID:jU3TV3ZDa
毎日壊れたレコードみたいに戯言つぶやいてないでガイジスレに帰れよw
2023/04/05(水) 10:36:55.94ID:ZG/fEbXfr
お前らもこっちきな😘
あっちは何を書き込んでもいいぞ🤗
2023/04/05(水) 11:41:26.97ID:PMDplXIF0
こっちも何書き込んでも大丈夫だぞ😉
2023/04/05(水) 17:58:38.15ID:RPvbx/wwM
マジで寒いノリだな
2023/04/05(水) 18:27:04.88ID:sB818/CP0
効いてるガイジ君ってずっといるんだなって
2023/04/05(水) 21:21:21.09ID:ez4hA7yb0
みんな効かないように頑張ろう
122デフォルトの名無しさん (ﾜｯﾁｮｲ 7f55-EYsv)
垢版 |
2023/04/06(木) 17:29:09.91ID:AU30dZob0
幅優先探索の計算量が O(N + M)（N は頂点数, M は辺数）ですが、
N と M は異なる種類の変数です。

計算量は、 O(N + M) ですと言われてもピンときません。

普通は、 N << M だと思うので、 O(M) でいいような気がします。

例えば、連結グラフの場合、 N - 1 ≦ M ですよね。
2023/04/06(木) 17:42:27.24ID:bgS53p4B0
辺が重複しない、という前提を入れるならそうですよね
2023/04/06(木) 17:42:52.77ID:SUeW78Oka
ウィキペディアにはO(M)と書いてあるぞ
2023/04/06(木) 17:49:53.74ID:2uDXGWIaa
普通は、と言ったって例外はあるやろ
126デフォルトの名無しさん (ﾜｯﾁｮｲ 7f55-EYsv)
垢版 |
2023/04/06(木) 17:51:04.74ID:AU30dZob0
O(N + M) ですと教えてもらって何が嬉しいですか？
この情報をどう利用しますか？
2023/04/06(木) 17:56:13.19ID:SUeW78Oka
計算量の話をする時って何も断りを入れなければ最悪計算量か平均計算量に決まってるのに普通じゃない時の話を持ち出してるのはどういう人種なんだ
2023/04/06(木) 18:01:17.36ID:bgS53p4B0
すまん、明らかに間違ったことかいてたわ
辺が重複しないじゃなくて、連結グラフという前提ならそうですよね
2023/04/06(木) 18:52:38.27ID:T+lwLVXUr
うるせーバカ
2023/04/06(木) 19:04:02.38ID:bgS53p4B0
サンキューガイジ！
2023/04/06(木) 19:06:12.21ID:O4MLKnYM0
自演失敗してて草
2023/04/06(木) 19:07:23.88ID:bgS53p4B0
自演ガイジも仲良くしようね
2023/04/06(木) 19:10:39.31ID:O4MLKnYM0
効いてて草
2023/04/06(木) 19:18:25.49ID:ejh7i/EB0
計算量の話って
満足な時間内にできるかどうかの議論でしか役に立たないよね
2023/04/06(木) 19:29:21.38ID:aDW8E5OM0
かかる時間が見積もれると嬉しいだろ
O(M)でないものをO(M)って書いていいことにはならないけど
2023/04/06(木) 19:53:45.59ID:Ej/MkqD7d
幅優先探索はそもそもΩ(N+M)なケースが無いと思うからO(M)って書いて欲しいが、N=O(M)は自明じゃないと思うぞ
N頂点0辺のグラフだってあるし
2023/04/06(木) 22:06:07.24ID:qiEKlOzd0
すまん嘘書いた
幅優先探索って最初に距離配列を作るからO(N+M)で合ってたわ
2023/04/07(金) 18:56:18.33ID:koL6xQVKa
チョクダイ毎日AI下げしてるな、これくらい上流層でも脅威なんだな
139デフォルトの名無しさん (ﾜｯﾁｮｲ 7f55-EYsv)
垢版 |
2023/04/07(金) 19:05:30.59ID:PbTiq3Mq0
高橋直大さんの実力は世界トップレベルなんですか？
2023/04/07(金) 19:50:49.14ID:4NY4d7fE0
いいえ
141デフォルトの名無しさん (ﾜｯﾁｮｲ ffca-7Vgv)
垢版 |
2023/04/07(金) 20:14:15.12ID:Jyfuc8w80
赤レベルが解けるようになるのは10年以上かかるだろうけど、
コーディングテストとして売り物になる層はすでにほぼ終了だし、E,Fまで解けるようになったらほとんどの参加者の自力解答は無意味ということに。
GPT前提の問題作りか、時間をかけた試行錯誤は苦手だろうからヒューリスティック重視とかになっていくんじゃないだろうか。
2023/04/08(土) 00:54:27.43ID:NWI0hhIl0
ヒューリスティックもある程度のレベルまでは行きそうだけどな
24時間コードを書かせ続けることもできるし
2023/04/08(土) 14:37:32.42ID:d9UfkEh40
始めて一年の茶色のおっさんだけどAIに負けるレベルになったと聞いてモチベだだ下がり。俺みたいなやつ多いと思うよ。
そりゃ参加者減ったら焦るわな
2023/04/08(土) 14:48:17.63ID:dzO9pS9o0
AIに負けるって言うがChatGPTは競プロ用にチューニングしたプログラミングAIじゃないぞ
こいつができるのは問題を読むことと何を求められてるかを把握すること
つまり日本語(あるいは英語)を読解するAIだ
要するに人類が負けてるのはプログラミング能力じゃなく読解力と記憶力なんだよ
今に見てろこいつらあらゆる分野でゲームと動画に浸かったお前らに国語力の差を見せつけてくるから
2023/04/08(土) 15:13:43.63ID:H0kArwlU0
暖色レベルへの到達はあったとしてもかなり先だろうし競技としては成立するだろうけど緑〜水色くらいなら近い将来到達しそうだし新規参入と寒色停滞勢の参加率は減るかもね
2023/04/08(土) 15:15:38.10ID:obJbbgz0p
競プロってゲームでやってるのかと思ってたからAIに負けてやる気なくなるってのはよくわからん
2023/04/08(土) 15:21:45.60ID:YDsW15QlM
ARC/AGCの中盤以降に競プロの本当の楽しさがあるという主張は否定しないが、ABCの前半も競技として楽しんでいた層の方がマジョリティで、そういう層が競プロの裾野を広げていた側面もあるから、コンテンツとしてダメージを受けざるを得ないと思うわ
企業もスポンサーをするのは基本ABCだし、Jobsで見られているのもレベル的にABCでの実力がメイン
2023/04/08(土) 15:23:40.74ID:YDsW15QlM
>>146
競技を楽しんでるのに競技そのものが成立しなくなったら嫌だろ？
Project Eulerみたいな感覚で問題に取り組んでいるんなら大丈夫だが、そういう人は初心者層ほど少ない
2023/04/08(土) 15:26:53.49ID:obJbbgz0p
>>148
他の人らがAI使って解答してるかもしれないと思ってしまうってこと？
2023/04/08(土) 15:34:11.41ID:YDsW15QlM
>>149
バレる可能性が低く対策不能なチートが蔓延ったオンラインゲームは壊れるやろ
ただのオンラインゲームでさえそうなのに、一応AtCoderはJobsみたいな実利的に意味のあるものと繋がってるから、みんな使うようになるんじゃねーの
開き直ってAIバトルにしても、投稿速度ゲームになりそうだし
2023/04/08(土) 15:35:24.79ID:YDsW15QlM
みんな使わないにしても、使ってるやつにレートを吸われることでモチベの減退はあるだろうな
2023/04/08(土) 15:36:44.41ID:obJbbgz0p
>>150
まあそういう人はスポーツすればいいよ
アルゴリズム解くのが好きとか純粋に知識欲の高い人が残るんだろうね
2023/04/08(土) 15:43:15.50ID:YDsW15QlM
>>152
その辺の人でも楽しめる競技になる道は閉ざされそうで悲しいな
元々運営にそういうモチベなさそうだったが（金のために仕方なくやってる感満載だった）
154デフォルトの名無しさん (ﾜｯﾁｮｲ c6ca-HjNm)
垢版 |
2023/04/08(土) 19:32:52.09ID:jzMk6Pp80
ノーレートで、食事したり飲みながら今までほぼ開かなかったF,GとかをchatGTPに聞いたり調べたりしながらやるのも楽しいぞい。解きたくない問題は解かなくても良いし。
155デフォルトの名無しさん (ﾜｯﾁｮｲ 8255-dXWb)
垢版 |
2023/04/08(土) 20:03:48.77ID:RgGs2QbX0
ワーシャル・フロイドアルゴリズムについて質問です。

最終的に任意の2点間の最短距離を入れるための2次元配列は、
代入演算子の左右で共通のものが使われています。
それでも、問題がないのはなぜですか？
2023/04/08(土) 20:09:47.90ID:8rEHJkBb0
ワーシャル・フロイドアルゴリズムは、全ての頂点間の最短距離を求めるためのアルゴリズムです。このアルゴリズムは、動的計画法の一種であり、一度計算された結果を再利用することで、計算量を減らすことができます。

具体的には、アルゴリズムの初期段階で、すべての頂点の間の距離を表す2次元配列を作成します。この配列は、アルゴリズムの途中で更新されますが、代入演算子の左右で共通のものが使われるため、問題はありません。

なぜなら、アルゴリズムの途中で更新される値は、それ以前の値に依存しているため、代入演算子の左右で共通の2次元配列を使用していることによって、更新された値が正しく計算され、以前に計算された値が失われることはありません。

つまり、更新された値は、以前に計算された値に基づいて正確に計算され、以前に計算された値が配列内に保持され続けるため、代入演算子の左右で共通の2次元配列を使用することは、アルゴリズムの正しい動作に影響を与えないということです。
157デフォルトの名無しさん (ﾜｯﾁｮｲ 8255-dXWb)
垢版 |
2023/04/08(土) 21:36:51.70ID:RgGs2QbX0
>>155

大丈夫な理由が分かりました。
2023/04/08(土) 22:06:19.33ID:8FTHKj1c0
chatGPT便利だろ
こういう風に答えてくれる
2023/04/08(土) 22:12:19.75ID:dzO9pS9o0
ものすごくもっともらしい嘘つくから知らないことを聞くのはおすすめしないぞ
2023/04/08(土) 22:16:56.23ID:dzO9pS9o0
ワルシャワ・フローラル法を知ってる？

はい、ワルシャワ・フローラル法は、グラフの最大マッチングを求めるアルゴリズムの一種です。このアルゴリズムは、ハンガリー人数学者であるエドモンド・ワルシャワと、ポーランド人数学者であるタデウシュ・フローラルによって開発されました。

ワルシャワ・フローラル法は、ハンガリー法と同様に、最大マッチング問題を解決するために使用されます。このアルゴリズムは、二部グラフに適用されます。アルゴリズムの基本的な考え方は、各未マッチング頂点について、その頂点を始点とする増加路を探し、その増加路に属する辺のマッチングを反転させることです。

ワルシャワ・フローラル法は、ハンガリー法よりも効率的であることが知られていますが、完全グラフでは最悪の場合の計算量がO(n^4)であるため、実用的ではありません。しかし、一般のグラフに対しては、最大マッチングを高速に計算することができるため、実際には広く使用されています。
2023/04/09(日) 02:49:15.65ID:3zzmmMIO0
正確なことを答えさせるために、プロンプトエンジニアリングをがんばりましょうね
2023/04/09(日) 06:48:28.69ID:/c2XAn9L0
素朴な整数演算のコードを書いたため、特定のテストケースのときにコードの途中で
整数がオーバーフローするような場合、一般的なコードの書き方の処方箋みたいなものは
ありますかね

例えば「整数の配列から適切な要素を取り出して期待される和を作れ、そういう要素が
ない場合はエラー値を返せ」みたいので、配列要素はどれもオーバーフローに近い整数、
和は配列内の最小要素よりちょっとだけ大きい値（なのでエラー値の場合）、とか....
2023/04/09(日) 10:26:45.20ID:/OFxiXOD0
競プロならlong longを使うだけ
実務ならオーバーフローした時に例外が発生するようにしてそれをキャッチ
164デフォルトの名無しさん (ﾜｯﾁｮｲ 8255-dXWb)
垢版 |
2023/04/09(日) 13:54:07.28ID:l3qXUMY00
『アルゴリズム実技検定公式テキストエントリー〜中級編』

最小全域木を求める、「プリムのアルゴリズム」について説明があります。
こうすれば、求まるという説明はあるのですが、なぜ求まるのかの説明がありません。

みなさんは、こうすれば求まるという情報だけで十分で、それで満足しますか？

それとも、ちゃんと証明まで自分で考えるか、誰かが書いた証明を読みますか？
2023/04/09(日) 14:45:06.26ID:dl/B18nt0
>>163
なるほど。確かに例えば入力がintならlong longを使えばとりあえず大丈夫そう
ちなみにC++ですが、例えばintのオーバーフローを例外で処理するのはどうしたら....
2023/04/09(日) 14:49:24.80ID:3zzmmMIO0
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.
2023/04/09(日) 16:13:00.47ID:sd0zf58N0
gccの__builtin_add_overflowとか__builtin_mul_overflowを使う
168デフォルトの名無しさん (ﾜｯﾁｮｲ 8255-dXWb)
垢版 |
2023/04/09(日) 18:08:06.26ID:l3qXUMY00
github.com/kenkoooo/pastbook-source-code/blob/master/chukyu/python/chapter06/section11/6-11-1.py
169デフォルトの名無しさん (ﾜｯﾁｮｲ 8255-dXWb)
垢版 |
2023/04/09(日) 18:11:31.29ID:l3qXUMY00
↑のファイルはプリムのアルゴリズムで最小全域木問題を解くコードです。
ファイル中の以下の箇所がなぜ必要なのかが分かりません。
一見すると、キューの中には、marked の値がFalseのノードしか入っていないように思うのですが、
実際には、Falseのノードも入ることがあるようです。（以下の箇所をコメントアウトすると
パスしません。）

# 辺につながる頂点 i もすでにマークされていた場合、
# 操作をスキップする
if marked[i]:
■■■■continue
170デフォルトの名無しさん (ﾜｯﾁｮｲ 8255-dXWb)
垢版 |
2023/04/09(日) 18:16:05.03ID:l3qXUMY00
一部、間違えましたので訂正します。↓

↑のファイルはプリムのアルゴリズムで最小全域木問題を解くコードです。
ファイル中の以下の箇所がなぜ必要なのかが分かりません。
一見すると、キューの中には、marked の値がFalseのノードしか入っていないように思うのですが、
実際には、Trueのノードも入ることがあるようです。（以下の箇所をコメントアウトすると
パスしません。）

# 辺につながる頂点 i もすでにマークされていた場合、
# 操作をスキップする
if marked[i]:
■■■■continue
2023/04/09(日) 18:19:09.47ID:fcL4nlHr0
この部分は、既にマークされた頂点に対応する辺をスキップするために必要です。
確かに、キューには基本的に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
この部分によって、既にマークされた頂点に対応する辺をスキップし、
正しい最小全域木を構築することができます。
172デフォルトの名無しさん (ﾜｯﾁｮｲ 8255-dXWb)
垢版 |
2023/04/09(日) 18:19:33.94ID:l3qXUMY00
ヒープにプッシュする前に、そのノードがマークされていないことをチェックしています。
ですので、ヒープ内には、マークされていないノードしか入れないと思うのですが。
173デフォルトの名無しさん (ﾜｯﾁｮｲ 8255-dXWb)
垢版 |
2023/04/09(日) 18:25:07.45ID:l3qXUMY00
>>171
あまり参考にならないだろうと思って読んでいたらなぜか理由が分かりました。
マークされていない状態で、同じノードが複数個ヒープに入ることがあるわけですね。
2023/04/09(日) 18:28:01.90ID:fcL4nlHr0
>>172
確かに、ヒープにプッシュする前にそのノードがマークされていないことをチェックしています。
ただし、ヒープにプッシュされた後で、そのノードが他の辺を経由してマークされる可能性があります。
そのため、ヒープから辺を取り出す前にもう一度マークされているかどうかをチェックする必要があります。

先程のグラフで考えてみましょう。キューがこの様になったところから解説します。
(1, 3), (1, 1), (1, 3)

ここで、最初に(1, 3)をキューから取り出し、頂点3をマークします。この時点で、キューには以下のような状態が残っています。
(1, 1), (1, 3)

次にキューから取り出す辺は(1, 1)です。この辺は、頂点1と頂点2の間にありますが、頂点1はすでにマークされています。
しかし、この辺をヒープにプッシュした時点では、頂点1はまだマークされていませんでした。
それが、例のコード部分が必要とされる理由です。

あの部分によって、既にマークされた頂点に対応する辺をスキップし、正しい最小全域木を構築することができます。
175デフォルトの名無しさん (ﾜｯﾁｮｲ 8255-dXWb)
垢版 |
2023/04/09(日) 18:28:12.80ID:l3qXUMY00
>>171
この場合でいうとノード3が2回ヒープに入るわけですね。
2023/04/09(日) 18:31:35.09ID:fcL4nlHr0
>>175
はい、その通りです。
最初にノード1からノード3への辺がヒープに追加され、次にノード2からノード3への辺がヒープに追加されます。

(1, 3) <-- 1から3への辺
(1, 1)
(1, 3) <-- 2から3への辺

このように、同じノードが複数回ヒープに入ることがあります。プリムのアルゴリズムでは、
すでにマークされた頂点に対応する辺を無視する必要があります。
そのため、ヒープから辺を取り出す前にマークされているかどうかをチェックする必要があるのです。
2023/04/09(日) 19:43:48.36ID:O0uaasVha
おんちぽまんぽげろろろり？
2023/04/09(日) 22:42:46.25ID:fJZ93dkaM
序盤からムズすぎ
2023/04/09(日) 22:44:46.28ID:0uKKY8S80
Eむずい
setとpriority queueいじくってたら通った
2023/04/09(日) 22:47:55.78ID:DKklNxRop
E二分探索でやろうとしたらハマって普通にsetで順番にみるだけだった
F解けたのに今回も解いてる人の数がF<Gなせいであまり順位伸びてないの配点何とかして欲しいわ
181デフォルトの名無しさん (ｽｯｯﾌﾟ Sd22-QZiB)
垢版 |
2023/04/09(日) 23:58:26.29ID:BvehXBT4d
整数式の倍数判定のプログラム作りたいんだけどできる？
nは自然数

例1

入力:n(n+1)(n+2)
出力:6

(入力した式の倍数判定。6の倍数)
2の倍数でも3の倍数でもあるが、最も大きい数を出力


例2
入力:n^9-n^3
出力:504
2023/04/10(月) 02:32:34.26ID:Gn/yyThB0
>>181
nに素数をいくつか突っ込んだ値(0以外)で最大公約数とればいいんでない？
という気はするけど万年茶色脳には正しいか証明するなんてムリ
2023/04/10(月) 02:49:14.21ID:zrtbja+Y0
素数pの倍数かどうかはmod pが整域だから多項式は根を高々次数d個しかもたないのでp≤dだけ調べればいいよね
p^kはわからん
2023/04/10(月) 03:22:55.78ID:zrtbja+Y0
fが零因子⇔あるa≠0が存在してaf=0らしいから、最初にfを係数のgcdで割っとけば零因子じゃなくなって、p^k≤dだけ調べればいいと思う
2023/04/10(月) 03:46:52.88ID:zrtbja+Y0
>>184
これ全部嘘です 寝るか
2023/04/10(月) 13:12:10.43ID:Sbe/ma/bM
mod p で何代入しても0になる多項式は例えば x(x-1)...(x-p+1) でp次を達成できて最適
mod p^n だとこれをn乗すると構成できるので（最適かは知らんが）pn次以下と評価できる
だからpnがd以下の範囲を探索すれば良いが計算量は悪いな
2023/04/10(月) 13:16:20.11ID:Sbe/ma/bM
>>186
馬鹿すぎ、評価すべき方向が逆
2023/04/10(月) 15:49:54.60ID:1oGpX4FF0
Fはやってみたら簡単に解けた
Gはgrundy数求めるとき単純な勘違いしてた
むー悔しい
189デフォルトの名無しさん (ﾜｯﾁｮｲ 8255-dXWb)
垢版 |
2023/04/10(月) 16:05:58.27ID:/Pv3NVQa0
DAGの最長パスを求める問題について質問があります。

『アルゴリズム実技検定公式テキストエントリー〜中級編』に
「トポロジカルソート」の考え方が重要と書いてあります。
ですが、DAGがトポロジカルソートできるということを使っている
箇所が見当たりません。

載っている解法は、indegreeが0である頂点からの最長パスをDPにより求めるというものです。
2023/04/10(月) 16:12:48.08ID:GqegRxcS0
確かに、その解法ではトポロジカルソートを明示的に実行していないように見えますが、
実際にはトポロジカルソートの考え方が含まれています。DAGの最長パスを求める際、
トポロジカルソートの概念が重要なのは、頂点の順序付けによって依存関係を解決することができるからです。

その解法で、indegree（入次数）が0の頂点からDPを用いて最長パスを求めています。これは、各頂点について、
その頂点に入ってくる辺がなくなる（依存関係が解決される）順序で処理を行っていることを意味します。
この順序付けがトポロジカルソートの結果と同じです。

indegreeが0になる頂点から処理を行い、その後、処理された頂点から出る辺を削除することで、
indegreeが0になる頂点が次々と現れます。この手順は、トポロジカルソートを実行する手順と同じです。

したがって、トポロジカルソートを明示的に行わなくても、その考え方が解法に含まれているため、
問題を解決することができます。トポロジカルソートの概念は、DAGの最長パス問題を解く際の重要な考え方であることがわかります。
191デフォルトの名無しさん (ﾜｯﾁｮｲ 8255-dXWb)
垢版 |
2023/04/10(月) 16:13:37.24ID:/Pv3NVQa0
DAGであれば、最長パスが存在し、それはDPで求められる。

ただそれだけのことではないでしょうか？
2023/04/10(月) 16:19:57.68ID:GqegRxcS0
はい、おっしゃる通りです。DAGであれば、最長パスが存在し、動的計画法（DP）を用いて求めることができます。

繰り返しになりますが、トポロジカルソートの概念を用いることで、DAG内の頂点の順序付けが可能であり、
この順序付けに従ってDPを適用することで、最長パスを求めることができます。
193デフォルトの名無しさん (ﾜｯﾁｮｲ 8255-dXWb)
垢版 |
2023/04/10(月) 16:20:04.87ID:/Pv3NVQa0
DAGにoutdegreeおよびindegreeが0の点が両方とも存在することは、自明です。
もしそのような点がなければ、閉路が存在することになるからです。
トポロジカルソートなどという考え方を持ち出すまでもありません。
2023/04/10(月) 16:26:05.43ID:GqegRxcS0
トポロジカルソートを明示的に実行しなくても、DAGの最長パス問題をDPで解くことは可能です。
ただし、その際に頂点の処理順序や依存関係の解決が重要となるため、トポロジカルソートの考え方が役立ちます。

トポロジカルソートを適用したDPでは、頂点の依存関係が効率的に解決されるため、計算量はO(V+E)です。
ここで、Vは頂点数、Eは辺数です。トポロジカルソートによって得られた頂点の順序に従ってDPを行うことで、
各頂点と辺に対して一度だけ計算が行われます。

一方、トポロジカルソートを適用しないDPでは、無駄な計算が発生する可能性があります。
例えば、メモ化再帰を用いたDPの場合、計算量は最悪O(2^V)になることがあります。
これは、全ての頂点に対して、それぞれを含むか含まないかの選択肢があるためです。
2023/04/10(月) 19:58:08.22ID:6t40mDb70
>>181
多項式 f(n) について計算したい
calc(f) で求めたい値を返す関数として
f が定数ならそれを返す
定数でないなら g(n)=f(n+1)-f(n)
とgを定めて
calc(f) = gcd(f(1), calc(g))
を計算すればいい、再帰の深さはfの次数で抑えられる
196デフォルトの名無しさん (ﾜｯﾁｮｲ 8255-dXWb)
垢版 |
2023/04/10(月) 20:30:41.82ID:/Pv3NVQa0
『アルゴリズム実技検定公式テキストエントリー〜中級編』に載っている
DAGの最長パスを求めるコードでは、トポロジカルソートを陽には使っていないです。
2023/04/10(月) 21:31:52.04ID:Qr60KJ2xa
その本持ってないからその本の解法教えて
そしたら質問の回答するよ
198デフォルトの名無しさん (ﾜｯﾁｮｲ 8255-dXWb)
垢版 |
2023/04/10(月) 21:57:16.12ID:/Pv3NVQa0
>>197
ソースコードは以下です：
github.com/kenkoooo/pastbook-source-code/blob/master/chukyu/python/chapter06/section04/6-4-8.py
2023/04/10(月) 22:22:43.61ID:Qr60KJ2xa
確かに陽にトポロジカルソートはしてないね
値が確定する順序がトポロジカルソート順の逆順にはなってるけど

多分、以下のようなことを言いたいんじゃないかな

・各頂点の値を一つずつ順に確定していって、
・一度確定した頂点を再度訪れる必要がない
・そのようなことが可能な確定順が存在する

確かに考え方によっては自明とも思えるかもしれないけど、逆にそれくらいのことしか言ってないということでは
2023/04/10(月) 22:32:19.30ID:GqegRxcS0
この問題の場合はメモ化再帰でトポロジカルソートを使わなくても計算量はO(N+M)です。
頂点間に循環がないため、再帰の深さが頂点数Nを超えることがなく、
各頂点に対して rec 関数が最大1回しか呼び出されないからです。

トポロジカルソートを使ってそのコードを書き換えるとこうなります。
https://ideone.com/1NbHIf
2023/04/11(火) 00:50:14.84ID:AEAouguL0
んげりいいいいいいいwwwwww
202デフォルトの名無しさん (ﾜｯﾁｮｲ 8255-dXWb)
垢版 |
2023/04/11(火) 10:56:16.23ID:KVT1yw8N0
>>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の要素を後ろから見ていかなければ
ならないように思ったのですが、そうではないのはなぜでしょうか？
203デフォルトの名無しさん (ﾜｯﾁｮｲ 8255-dXWb)
垢版 |
2023/04/11(火) 11:11:09.23ID:KVT1yw8N0
for u in order:
■■■■print(u)

とすると自分が思っている順序とちょうど逆順で表示されます。

order.append(u)

を実行すると order の最大インデックスの要素の次に u が挿入されますよね。

そうだとすると、 order[0], order[1], … は queue から出てきた順に並べたものになりますよね。
204デフォルトの名無しさん (ﾜｯﾁｮｲ 8255-dXWb)
垢版 |
2023/04/11(火) 11:15:16.38ID:KVT1yw8N0
多分、単純な勘違いなんですが、どこを勘違いしているのかが分かりません。
205デフォルトの名無しさん (ﾜｯﾁｮｲ 8255-dXWb)
垢版 |
2023/04/11(火) 11:16:45.70ID:KVT1yw8N0
あ、分かりました。
与えられた有向グラフの辺の向きをすべて逆にしても、最長パスの長さは変わりませんね。
206デフォルトの名無しさん (ﾜｯﾁｮｲ 8255-dXWb)
垢版 |
2023/04/11(火) 11:35:54.50ID:KVT1yw8N0
以下のコードは全く無駄なことをやっていますが、自分の理解通りなのはこちらのコードです：
ideone.com/gMUZDZ
2023/04/11(火) 13:43:59.54ID:FMwVbediM
すまん初めてこのスレ来たんだけど連投してるやつはネームド？
2023/04/11(火) 14:46:33.78ID:vCEpO63Mr
ネームド志望
2023/04/11(火) 15:09:56.33ID:F0CC9LzbM
>>195
天才か

gcd(f(1),f(2),...)
=gcd(f(1),f(2)-f(1),f(3)-f(2),...)
ということか

確かに典型だが無限で思考がストップしてしまっていた
210デフォルトの名無しさん (ﾜｯﾁｮｲ 8255-dXWb)
垢版 |
2023/04/11(火) 18:39:41.18ID:KVT1yw8N0
pythonで2分探索を行う bisect というものがあります。

bisect.bisect(l, a)

としたとき、 a in l であるかどうかも判定したいのですが、そのような関数は用意されていませんか？
自分で作るしかないですかね？
211デフォルトの名無しさん (ﾜｯﾁｮｲ 8255-dXWb)
垢版 |
2023/04/11(火) 18:42:16.72ID:KVT1yw8N0
Pythonに2分探索で整列済みのリスト l に要素 a が含まれるかどうかを調べる関数はありますか？
212デフォルトの名無しさん (ﾜｯﾁｮｲ 8255-dXWb)
垢版 |
2023/04/11(火) 18:44:52.56ID:KVT1yw8N0
もちろん、 bisect を使って、簡単に実装できますが、用意されている関数はないですか？
2023/04/11(火) 19:14:39.91ID:AEAouguL0
がんばれ
214デフォルトの名無しさん (ﾜｯﾁｮｲ 8255-dXWb)
垢版 |
2023/04/11(火) 19:20:22.62ID:KVT1yw8N0
まあ、以下のコードでいいと思うのですが、車輪の再発明はしたくないですよね。

i = bisect.bisect_left(l, a)
if l[i] == a:
return True
else:
return False
2023/04/11(火) 23:36:07.25ID:HQTQbeZV0
車輪の再発明はしたくないですよ
2023/04/12(水) 00:15:56.65ID:9s1XLAQx0
公式を読めと言いたいが
https://docs.python.org/ja/3.8/library/bisect.html
集合でも管理してinで判定すれば良いのでは(´・ω・`)
2023/04/12(水) 09:07:44.12ID:tXIe9h+KM
今IT系とは全く別の職種だから転職したくてAtCoder始めたけど楽しいな
未経験で他職種に転職出来るのか分からんけど
2023/04/12(水) 09:21:22.65ID:g9fBg21da
>>216
2分探索することは確定でそこで発見できるのにそれに加えてわざわざ他の集合を使う意味とは？
2023/04/12(水) 09:24:04.21ID:g9fBg21da
>>217
最低緑以上になればJobsで転職できる可能性はあるが緑っていっぱいいるので年齢や運が絡むかもな
2023/04/12(水) 09:48:33.24ID:VY8vydj+M
>>219
ありがとう
数学好きでアルゴリズムも昔やったことあったから緑まではすんなりいけたわ
今は水色目指して色々やってるけどアルゴリズム的要素より数学要素のほうが多く感じるな
年齢は25だからあと3年位がギリギリかなあと思ってる
2023/04/12(水) 10:00:29.60ID:e73VjvEsa
水より緑の方が採用しやすい
ほんとに転職したいなら水まで行ったらとか思わない方がいい
2023/04/12(水) 12:09:52.88ID:SHZyHyDIM
>>221
今年色々あって復職したてだから転職活動するなら来年以降かもしれんわ、一応ビズリーチとか登録はしたけど
水色より緑のほうが採用しやすいのはなぜ？
223デフォルトの名無しさん (ｽｯﾌﾟﾌﾟ Sd22-QZiB)
垢版 |
2023/04/12(水) 17:15:55.13ID:d+uvLod6d
今から狂気プログラミング始めるならPythonでいいかな、
2023/04/12(水) 18:22:04.45ID:7SV2gFKB0
brainfuckがいいと思うよ
225デフォルトの名無しさん (ﾜｯﾁｮｲ 8255-dXWb)
垢版 |
2023/04/12(水) 20:36:03.56ID:AXD/P1A20
以下の問題ですが、パスするまでに1日かかりました。

atcoder.jp/contests/past202004-open/tasks/past202004_g

こういうアイディアはほとんど必要がないけれども、実装するのが大変という
問題の対処方法を教えてください。

1日かかって作成したコードは以下です：

ideone.com/NY8mNY
226デフォルトの名無しさん (ﾜｯﾁｮｲ 8255-dXWb)
垢版 |
2023/04/12(水) 20:42:57.91ID:AXD/P1A20
あ、模範解答を見たら、実装するのも実は大変じゃないんですね。
2023/04/13(木) 14:51:21.47ID:YZ8/Xbx00
>>225
> こういうアイディアはほとんど必要がないけれども、実装するのが大変という
> 問題の対処方法を教えてください。
「アイデアを出すか頑張って実装する」以外の答えが思いつかんのだが真面目に聞いてるのか？
228デフォルトの名無しさん (ﾜｯﾁｮｲ 8255-dXWb)
垢版 |
2023/04/13(木) 16:57:11.93ID:lV5klkX+0
実装大変だなーと思ったら、自分のアイディアが悪いと思ってまず間違いないですか？

というのも、模範解答を見ると実装もシンプルな場合ばかりなので。
2023/04/13(木) 17:03:32.55ID:UbSfQqvCa
風向風速とかの簡単で面倒な問題も初期の頃はあったなあ
最近見ないけど無いと言い切る材料もない
2023/04/14(金) 00:49:29.86ID:PKpPv7DW0
土曜夕方にコドフォdiv1あるじゃん
2023/04/14(金) 00:57:35.22ID:iX1MRsL1r
普通デートするよね
2023/04/15(土) 15:22:24.86ID:J7EhpH7h0
中国にウクライナ侵攻関連で厚い助力を求めるようだな
台湾侵攻の際には、米軍を混乱させるためにロシアは北海道に、北朝鮮は南に牽制するという話もあったしそりゃそうだよな

https://www.bloomberg.co.jp/news/articles/2023-04-14/RT3MFKDWX2PT01
中国は、プーチン大統領が１年以上前にウクライナ侵攻を命じて以来初めて、国防相をロシアに派遣する。中ロの緊密な関係があらためて示唆される。

中国の李尚福国防相はロシアのショイグ国防相の招きに応じ、16日からロシア訪問を開始する。
ショイグ氏は李氏と軍事協力および世界や地域の安全保障について議論すると語ったと、ロシアの国営タス通信は報じた。
2023/04/15(土) 18:34:37.16ID:YgeZYNMw0
そうですか。中国やロシア、北朝鮮の動向は世界の平和や安全に影響を与える可能性がありますね。

最新のニュースによると、米国が中国の台湾侵攻を確実視しており、日本も中国と戦火を交える可能性があるという記事がありました。¹

また、安保理が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.
2023/04/15(土) 22:26:08.62ID:KbvfxJ7qM
今回のABCレート不具合で変動なしらしいな
苦手分野過ぎてAとBしか解けなかったからありがたいわ
2023/04/15(土) 22:42:31.24ID:hxYUx3pC0
5完
バグりまくるし止まりまくるし散々だった
2023/04/15(土) 22:45:28.79ID:2lW0lXjE0
>>218
調子良かったのにunratedかよ☹
2023/04/15(土) 22:55:38.71ID:2lW0lXjE0
のんびり解いてた割には暖まるなあと思ってたけどこれDDoSの影響で普段速く解く人が遅れたってことか🥶
2023/04/15(土) 23:06:02.45ID:hxYUx3pC0
あと5分あったらF修正して解けてた…
2023/04/16(日) 16:50:33.05ID:+7pzCas80
https://twitter.com/chokudai/status/1643492418497699841
マルチchokudaiサーチがダサくないと思ってるところに草生える
https://twitter.com/5chan_nel (5ch newer account)
2023/04/16(日) 18:18:14.06ID:iQzJN3tu0
研究者が自分の名前を手法に付けることは、研究コミュニティで一般的には推奨されていません。ただし、研究者が特定の手法やアルゴリズムを開発した場合、その手法が他の研究者や専門家によって引用されることがあります。この場合、研究者の名前が手法に関連付けられることがあります。
2023/04/16(日) 18:55:38.54ID:uh3dAZwl0
今回のCでどうしても3つTLEが潰せない
2023/04/16(日) 19:06:04.93ID:Ke39kkrTa
どうしても自力で解けないなら解説読んでいいんじゃね
2023/04/16(日) 22:30:54.90ID:SVYFRHN6r
もし自分でアルゴリズム開発したらかっこいい略称付けたいよね
2023/04/16(日) 22:32:11.67ID:XfEQvCuWa
>>241
俺かよ
PriorityqueやSortedSetを使わずに普通の配列やSetを使って出力時に都度ソートしたら行けた
自前のライブラリだと重すぎるみたいだな
245デフォルトの名無しさん (ﾜｯﾁｮｲ 5f55-7nfa)
垢版 |
2023/04/17(月) 08:58:02.89ID:5c7uVWzN0
Aho, Hopcroft and UllmanのThe Design and Analysis of Computer Algorithmsという
非常に古い本はもうゴミのような本でしょうか？
2023/04/17(月) 12:28:12.67ID:WWhqmq79r
今アホって言った？
2023/04/17(月) 22:20:09.89ID:5e6VxUA80
最近は自分で判断できない輩が増えてきたな。
2023/04/17(月) 22:52:26.54ID:LKkslgOL0
>>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は、歴史的な価値があるという点でゴミのような本とは言えませんが、現代のアルゴリズム研究や技術を学ぶ上で最も適切な教材ではないかもしれません。学ぶ内容に応じて、より新しいリソースや書籍を利用することを検討してみてください。
2023/04/17(月) 23:36:48.58ID:y8gbGQlA0
アルゴリズムデザイン、重版されて書店に並んでて嬉しかった
2023/04/20(木) 19:31:49.09ID:f2njLhGLa
https://mathlog.info/articles/4204

今までにない斬新なセグ木の解説記事
2023/04/20(木) 19:42:54.89ID:mhtgTGfFa
>>250
その下のスーパー某もすごいな
2023/04/21(金) 12:31:14.61ID:Oi9Mt79Gr
レートは？書いた人の
2023/04/21(金) 13:07:22.60ID:/VhDvdfwa
正確な数値はともかく灰色以外の何に見えるんだ？
2023/04/21(金) 13:16:18.21ID:wvR7tFMwr
読む価値があるか確認するために聞いたんだけど
2023/04/21(金) 13:19:22.09ID:/VhDvdfwa
ないよ
2023/04/21(金) 13:20:36.38ID:Va2XyxIX0
ないアルヨ
2023/04/21(金) 13:23:56.80ID:/VhDvdfwa
ないのかあるのかどっちだと突っ込んでほしいジジイおるな
2023/04/21(金) 13:26:33.33ID:Va2XyxIX0
ツッコんでほしいアルヨ
2023/04/21(金) 17:05:10.19ID:k2duIDVm0
関数型しか触ったことないに1ペソ
2023/04/22(土) 21:46:10.29ID:5GqLc7RXM
またUnratedやないか
誰やねんDDoSしてるやつ
こんなサイトにしても意味ないやろ
2023/04/22(土) 22:42:13.57ID:/cmb/FVj0
久しぶりにABCDEG6完😤
2023/04/22(土) 23:12:42.60ID:rVcI1++Da
中国かロシアやろな
国がらみの可能性もあるから犯人探しは無意味
2023/04/23(日) 01:27:17.24ID:moyGSSduM
意図的に狙われてるのは確かだけどなんの目的で狙ってるんやろ
2023/04/23(日) 15:36:40.71ID:60YTymnP0
C問題なんだけど解説みたいに反転させる必要ある？
一つでも-が含まれてたらoの最大長答えるだけじゃない？
つまりn未満のoの最大長答えるだけでしょ
2023/04/23(日) 15:44:39.80ID:QD8bkyZga
解答例のやり方だと反転の必要あるな
串が出てきて初めてansに入るから
2023/04/23(日) 18:46:05.86ID:MZTwl0QJ0
反転させて2回チェックすれば団子判定をシンプルにできるって意図じゃないかな
2023/04/23(日) 18:54:15.92ID:LpJKh+XVa
出題者は反転してない
どっちでもいいんじゃね
2023/04/23(日) 20:08:08.02ID:PWijjkXzM
-が入っていれば、oと-しかないのだからoは-と接してるわけで、oと-どちらかなければ-1、両方あれば連続したoの長さでいいんじゃないの？
2023/04/23(日) 20:10:50.67ID:PWijjkXzM
久し振りにやったんだけど、
rated選んだつもりなのにunratedになってたんだけど、自分が選び間違えたの？
成績よくなかったからいいんだけど
2023/04/23(日) 20:17:55.91ID:5yiVxLP00
質問タブに書いてあるけどDDOSのせいで全員unratedの無効試合になってる
2023/04/23(日) 20:18:35.89ID:5yiVxLP00
>>268
それでもいいし解けさえすればそれでなくてもいいというだけの話
2023/04/23(日) 20:39:44.51ID:PWijjkXzM
>>270
ありがと。
別にお酒に酔ってたわけじゃないのに、
なんで間違えたのかずっと悩んでたの
2023/04/23(日) 20:43:02.12ID:LpJKh+XVa
Cは正規表現で解けるな
肯定的先読み言明を使えば一回のマッチでいける
2023/04/23(日) 21:48:22.47ID:kV4uegyh0
質問タブでアナウンス送るの、知らない人にとっては分かりづらい
2023/04/25(火) 18:22:04.22ID:NfKxocHyd
Chatgptの影響ですでにレート出にくくなってるとかある？
2023/04/25(火) 18:32:28.97ID:aoA2LcV80
GPTのおかげで誰でもCくらいまでは瞬殺できるし、緑茶らへんの人にとっては影響あるんじゃない？
2023/04/25(火) 20:23:26.21ID:Nhg6f6DZa
インタラクティブ問題なら回避できるんかな
2023/04/25(火) 22:48:32.00ID:8h60ybjNd
茶色中盤くらいまではCまで早解きゲーだしまあ初心者は萎えるかもな
2023/04/26(水) 00:39:41.99ID:v/InlOgJ0
D - Find by Query
この問題の意味がわからない、運が悪いとACできないとか無いの？
2023/04/26(水) 00:44:09.42ID:v/InlOgJ0
ああ、境界を探すのか
2023/04/26(水) 04:47:13.13ID:CtDSQpU90
10 ^ 6で試せる回数が20回だから二分探索しかないんだけどこういうメタ読み辞めたいんだよな
2023/04/26(水) 04:53:12.19ID:dFoBwinZp
何なら序盤で出てくるインタラクティブ問題っていう時点でパターンが限られすぎてて8、9割二分探索(の類型)であることが推測出来る
2023/04/26(水) 14:19:57.84ID:pZKGmWvba
>>276
必ず正しい答えを出すわけじゃないから自分で直せないとペナルティ食らうぞ
2023/04/26(水) 18:10:09.71ID:hY8jXU1C0
問題公開されてても提出できなかったらどうすんの
2023/04/26(水) 18:32:26.54ID:PpfAVk7MM
茶色だけみんなchatgptで序盤の問題解いてたのか
俺もそうしようかな
2023/04/27(木) 13:25:15.77ID:N5pXZR7+0
GPT使ってないからレートが低い、みたいなセルフハンディキャップはカッコ悪すぎるからGPTくらいは賢く利用しようね
2023/04/28(金) 04:45:15.96ID:9dah9Cbv0
A,Bの問題文を整形してChatGPTに貼り付けて反応もどってくるの待つより自分で解いたほうが速いわけ
更に投稿前にチェックも必要だし
嫁にそのやり方を教えてA,B問題の投稿を担当してもらってる間に自分はCあたりから手を付けるのほうがいいかも
2023/04/28(金) 08:08:18.98ID:Qu9Tu4Uo0
>>287

そんな姑息なことをするほど、競技プログラミングで良い成績をおさめることにメリットはあるんですね。
2023/04/28(金) 08:22:56.44ID:39Dn9gJ30
>>287
APIあるんだから全部自動化するにきまってんだろ
2023/04/29(土) 23:10:27.33ID:yZQ+uKse0
5完しかできなかった
Dみたいなのが地味にめんどくさい
2023/04/29(土) 23:17:20.22ID:BBFLtm1nM
D問題昨日勉強した内容が出てきてめっちゃ嬉しかった
これ進研ゼミでやったことある状態だったわ
2023/04/30(日) 00:03:32.63ID:VtRKwrnb0
Gで解説と違う方針で通したから解説書こうと思ったが、一応C++でも通るか確認したらC++だとTLEだったのでやめた
C++遅いね
293デフォルトの名無しさん (ｽﾌｯ Sdbf-TsFU)
垢版 |
2023/04/30(日) 01:19:01.58ID:WQH2sNqzd
Patisserie ABC 3 出るかと思って過去問見直したけど全然出なかった
2023/05/03(水) 00:51:23.91ID:83koBp/d0
ngtkanaって男性？
2023/05/03(水) 04:10:47.45ID:k35m8F9T0
黄色だから野郎じゃない
296デフォルトの名無しさん (ﾜｯﾁｮｲ 9f55-hzXf)
垢版 |
2023/05/03(水) 17:06:24.93ID:aKUbjdKi0
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 であるかそうでないかを判定してください。

↑自作の問題です。
この問題って効率的なアルゴリズムが存在しますか？
2023/05/03(水) 17:43:05.99ID:C+dlbD9Z0
日本語で書いてくれ
2023/05/03(水) 19:29:13.60ID:ElyXadep0
B1とB2の直方体の数が異なる場合、B1とB2は等しくない
B1とB2の直方体の数が同じ場合、B1とB2に含まれる直方体の番号を並べ替える
各直方体の対応する要素が等しくない場合、B1とB2は等しくない
すべての直方体の対応する要素が等しい場合、B1とB2は等しい
2023/05/03(水) 19:40:48.41ID:aKUbjdKi0
B1 が1個のn次元直方体からなる集合とします。
それを2つに分けた2つのn次元直方体の和集合を B2 とします。
B1 を構成する直方体の数は 1 です。
B2 を構成する直方体の数は 2 です。
ですが、B1 = B2 です。
300デフォルトの名無しさん (ﾜｯﾁｮｲ 9f55-hzXf)
垢版 |
2023/05/03(水) 19:43:42.25ID:aKUbjdKi0
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 です。
301デフォルトの名無しさん (ﾜｯﾁｮｲ 9f55-hzXf)
垢版 |
2023/05/03(水) 19:48:56.95ID:aKUbjdKi0
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 です。
302デフォルトの名無しさん (ﾜｯﾁｮｲ 9f55-hzXf)
垢版 |
2023/05/03(水) 19:49:22.48ID:aKUbjdKi0
>>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 です。
2023/05/03(水) 21:06:39.53ID:MtXxv88er
うんち！w
2023/05/04(木) 00:35:43.31ID:FFDpqzE90
併合していって無駄のない表現にできればいける？
2023/05/04(木) 01:33:09.74ID:Pbw0n2Gt0
そんなことよりn乗で増えていくのを抑えないと無理なんでは
306デフォルトの名無しさん (ﾜｯﾁｮｲ 9f55-hzXf)
垢版 |
2023/05/04(木) 02:26:58.39ID:iR6EpWdh0
2次元限定、座標は有理数限定にしたら、競プロの問題として成立しますか？
2023/05/04(木) 04:20:04.21ID:W+5O3yqN0
>>306
yukicoderで出題してみれば？
308デフォルトの名無しさん (ﾜｯﾁｮｲ 9f55-hzXf)
垢版 |
2023/05/05(金) 10:56:46.77ID:xYbtWehf0
>>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 の部分集合の中で最大の直方体を求めよ。


この効率的な解法はありますか？
2023/05/05(金) 13:25:13.43ID:CuujTRH+0
あるよ
2023/05/05(金) 18:31:53.93ID:zrOWQZW0M
自分で解けてなければ自作の問題とは言わん
2023/05/05(金) 21:17:04.26ID:0zwWrX/A0
よくわからないけど [0, 1) の最大の区間は存在しないんだけど大丈夫そ？
2023/05/13(土) 22:41:38.39ID:WJe+G9hta
5分延長か
面白い対応するね
2023/05/14(日) 00:45:51.21ID:KvQ47IR30
攻撃を受けてもratedという前例ができたのはよかった
2023/05/14(日) 06:52:48.64ID:NgHJ91w50
コンテストモードの敗北
315デフォルトの名無しさん (ﾜｯﾁｮｲ f37c-ECSL)
垢版 |
2023/05/17(水) 05:36:16.93ID:UaIMjrrs0
>>294
女性だよ
検索したら本名とか出て来ると思うけど
2023/05/17(水) 09:19:32.53ID:tRah0iPS0
>>315
Youtubeで本人の歌声も聴けるしな
2023/05/20(土) 22:48:05.22ID:IbXAPdJ/0
６完…
今回は７完したかった…
2023/05/20(土) 23:12:12.63ID:+EVZ8y+Ka
配点割とその通りだったな
2023/05/22(月) 00:56:46.44ID:mBh1GEMi0
パフォーマンスがinfinityになった回って61以前にあった？
2023/05/27(土) 22:44:08.16ID:DM47Hxe/0
難しすぎるよ
2023/05/27(土) 23:33:38.14ID:DM47Hxe/0
コドフォもないし
2023/06/03(土) 23:01:24.39ID:i1emxrQn0
6完
mod入力ミスってたのがアホすぎる
323デフォルトの名無しさん (ﾜｯﾁｮｲ c6bd-2a7c)
垢版 |
2023/06/04(日) 16:31:49.86ID:VEMViUBd0
やっとE問題解けるようになってきた

E問題って一個一個の実行時間が長いんだな
324デフォルトの名無しさん (ﾜｯﾁｮｲ c2bd-2a7c)
垢版 |
2023/06/04(日) 17:44:29.58ID:0q9gSB9x0
競プロ有段者(強い人)に質問

Atcoderで一段階上に行くためには解説を何も見ずとも解けるレベルの一段階上を同じように解けるレベルになるまでその問題を解説だけ見て実装は全て自分で、っていう感じでひたすら練習していくっていうやり方は有効？

自分の場合はD問題は9割ガタ解けて、Eがまだ実戦では歯が立たないレベル
2023/06/04(日) 17:53:24.73ID:AGQzq0Q+0
うん
326デフォルトの名無しさん (ﾜｯﾁｮｲ 02bd-2a7c)
垢版 |
2023/06/04(日) 20:29:27.17ID:z/tZxQvT0
E問題思ったより簡単だな
食わず嫌いしてた
2023/06/06(火) 11:53:03.19ID:MhCqkbZk0
某所で「左右がバランスした括弧の列を生成する」という問題があり、解答が

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; が左右のバランス（単に'('と')'の数が同じというだけでなく）の条件に
効いているようですが、ピンとこないのです... 確かに正しい括弧の列のとき、それが成り
立つのはわかりますが、逆にそれがバランス条件を満たすのに十分であるというのが　
どなたかわかりやすい説明はないでしょうか
2023/06/06(火) 12:29:54.00ID:GQVo4dJ/a
しょーもない処理を複雑に描いてるだけのクソプログラムやな
この関数は最初の呼び出しでlとrが同じ数字なるよう入れるのが前提で
r<lの条件は例外処理みたいなもんやろ
2023/06/06(火) 12:35:33.96ID:UncR9VmG0
このコードの一部 `if (r < l) return;` について説明します。

ここで `l` と `r` はそれぞれまだ追加できる '(' の数と ')' の数を表しています。なので、このチェック `if (r < l) return;` は、')' の数が '(' の数より少なくなる場合、すなわち、開き括弧より閉じ括弧が少なくなる場合を防いでいます。

正しい括弧の列を生成するためには、2つの重要なルールを守らなければなりません：

1. 左括弧と右括弧の数が等しいこと
2. 任意の時点で、右括弧の数が左括弧の数を超えないこと

1つ目のルールは、左括弧と右括弧を同数だけ生成すれば満たされます。しかし、2つ目のルールはもう少し注意が必要です。それは、どの時点でも、閉じ括弧の数が開き括弧の数を超えてはならないからです。これを超えてしまうと、括弧の列が無効になってしまいます。

例えば、"())(" のような列は、開き括弧と閉じ括弧の数は同じでも、2番目の閉じ括弧が開き括弧を超えているため、無効な括弧の列となります。

だからこそ、`if (r < l) return;` のチェックが必要なのです。これにより、閉じ括弧の数が開き括弧を超えるような状況を防いでいます。これは、まだ追加できる閉じ括弧の数 `r` が、開き括弧 `l` より少なくなる場合、すなわち、閉じ括弧が開き括弧を超える可能性がある場合に、そのパスをすぐに終了させることで実現されています。
2023/06/06(火) 12:49:04.77ID:FRsr3KcUH
(を+1)を-1と対応させて累積和が常に非負っていうのがバランスしていることの必要十分条件であることを認めれば if(r < l)return; がそれの言い換えなことは明らか
証明したければ累積和が0になるところで文字列を分割して、それぞれの文字列の一番外側の括弧を取り外すとネストが一つ浅いものに帰着できるからネストの深さで帰納法を回すみたいなことを気をつけてやるといいんじゃないか
2023/06/07(水) 08:00:55.26ID:nPOLblkw0
>>329はChatGPTなのかな? すごいな
>>330 どうもありがとうございます

このコードの場合、再帰時に常に右側に括弧を追加することが if (r < l) return; で
必要十分になることの前提だと思うんですが.... >>329はそのことがうやむやのような
2023/06/07(水) 08:33:42.08ID:nPOLblkw0
>>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の(())を二つ並べた、と考えるべき?

要は、正しい括弧の追加操作のみをして再帰的に括弧列を生成することは可能なのか?
あるいは単にすべてのパターンを生成して正当でないのを刈り取ることしかできないのか?
などということが気になったのですが
2023/06/07(水) 09:49:06.82ID:Bta2HQ7X0
>>332
結論から言うと、それは難しい問題であり、一般的なアプローチでは、「全てのパターンを生成し、
それがバランスの取れた括弧列であるかどうかを判定する」という方法が用いられます。

しかし、バランスの取れた括弧列を生成するための一種の再帰的なパターンは存在します。
それは、大きさnの全てのバランスの取れた括弧列を生成した後で、その各々に対して以下の操作を行うことです：

1. '(' + P + ')' を追加する
2. P + '()' を追加する
3. '()' + P を追加する
ここで P は大きさnの任意のバランスの取れた括弧列です。

この操作を行うと、全ての大きさn+1のバランスの取れた括弧列を生成することができます。
ただし、これは重複する列を生成する可能性があるため、生成された列は一意であることを保証するために
何らかの方法で重複を除去する必要があります。

したがって、厳密には「全てのパターンを生成し、それがバランスの取れた括弧列であるかどうかを判定する」
という方法とは異なりますが、これは一種の再帰的なアプローチと言えます。

しかし、これらのアプローチは計算時間やメモリ使用量の観点から見ると、>>327に示されたDFSを用いたアプローチに比べて
効率的ではないかもしれません。また、DFSを用いたアプローチは明確に「正しい括弧の追加操作のみ」を行っていると言えます。
なぜなら、すべての括弧列を生成する過程で、同時にその列が正しい括弧列であるかどうかをチェックすることが可能だからです。
2023/06/07(水) 10:10:41.04ID:WomvMCD50
>>332
>>333 は嘘
バランスした括弧列の定義は全体を括弧で囲む操作と括弧列2つの結合で生成される集合だから、その()を追加するっていうのを右か左に追加するって意味だとするとレベル2以上の文字列同士の結合が考慮されていないの
で、(())(())が作れない

中に()を挿入することを許すとすると、今度は全体を括弧で囲む操作はいらなくなる
というのも、どんな空でないバランスした括弧列にも()の部分があるから、それを取り除くことを繰り返すことで空にできるから、逆に空文字列に()を追加していくことで任意のバランスした括弧列が作れるし、バランスした括弧列の任意の箇所に()を挿入した文字列もまたバランスした括弧列になっている
2023/06/07(水) 11:08:01.09ID:DYKBdUd80
>>331
ご指摘の通り、このコードでは再帰的に右側に括弧を追加しています。具体的には、まず左括弧を追加し、その後で右括弧を追加しています。

この if (r < l) return; の制約は、この追加の順序に基づいています。開始時点では、開き括弧と閉じ括弧の数が等しく（つまり、l == r）、左括弧を先に追加します。そのため、追加の過程では一時的に l が r より小さくなります。しかし、その後すぐに右括弧を追加することでバランスを保ちます。

if (r < l) return; のチェックにより、右括弧が先に追加される（つまり、r < l となる）状況を防いでいます。これは、左括弧を追加した後でのみ右括弧を追加するという、このコードの括弧の追加の順序を反映しています。そのため、この制約が満たされない場合（つまり、右括弧が先に追加される場合）、そのパスは無効となり、すぐに終了します。

したがって、この if (r < l) return; の制約は、このコードの括弧の追加の順序に基づいて、左括弧と右括弧が正しくバランスを保つことを保証しています。
2023/06/07(水) 14:48:36.26ID:w+aRYGw/r
非負のランダムウォーク書いて+1-1を()に対応させるだけだろ
2023/06/10(土) 17:29:19.24ID:0oQUevmP0
>>327
閉じ括弧が開き括弧より少なかったら、ダメってことなだけでは。

開き括弧と閉じ括弧の数が同じって条件は最初の呼び出しではlとrが同じでなければならないって制約があると思う
2023/06/10(土) 22:46:50.51ID:sqwX2ns70
6完…
途中まではいいペースもFで帰りがけにも頂点集合受け取るの忘れて時間ギリギリに
2023/06/11(日) 20:43:12.18ID:Fc1cWZtx0
>>337
例えば())(()は閉じ開きの括弧数だけでいうとおkだけど実際にはおkじゃない
では何故これが生成されないか、他の駄目パターンもなぜ生成されないか気になった
というのを既に考察したつもり
2023/06/11(日) 20:59:44.70ID:Fc1cWZtx0
しかし、解く時間が限られている場合にグダグダ悩んでいる暇はないよなあ
そういう場合パターンを覚えておくしかない?
2023/06/17(土) 22:47:22.26ID:/YYtpwSS0
ジャッジが終わらないよ
2023/06/17(土) 23:10:07.92ID:dXHH06bsM
unratedおおすぎ
2023/06/17(土) 23:16:56.58ID:re9nMjXH0
アーロンジャッジたすけて
2023/06/18(日) 04:25:23.41ID:KT9X3u120
atcoderがddos受けてるとして、潰して得をするのは誰だ？
2023/06/18(日) 11:57:26.20ID:zhu3s9uha
ロシア中国
2023/06/24(土) 17:44:41.70ID:SdmUsAHw0
ガイジのみんなこっちおいで😆
怖がる必要ないよ✌
2023/06/24(土) 18:57:52.69ID:JQRvym1Fr
うおおおおおおおお🤓
2023/06/24(土) 19:30:32.53ID:SdmUsAHw0
他のガイジもこっちおいで！
349デフォルトの名無しさん (ﾜｯﾁｮｲ a3bd-/B6M)
垢版 |
2023/06/24(土) 22:23:51.32ID:+O4dPU7T0
攻撃されてね？
2023/06/24(土) 22:28:05.07ID:SdmUsAHw0
落ちてる！クソすぎ！！！
2023/06/24(土) 22:42:50.37ID:ZtOuHWP80
せっかくG解けたのに1分遅れになってしまった…
2023/06/24(土) 22:55:29.87ID:gDpwuzMxa
アンレでしょ、ね？ね？
2023/06/24(土) 22:56:49.69ID:ZtOuHWP80
ところでC正解者少なすぎ
2023/06/24(土) 23:12:14.22ID:SdmUsAHw0
10:10くらい？から今(10:50)までずっとatcoder開けませんが、同じ人いるかな
なんてツイートしてるひともいるね
2023/06/25(日) 01:40:55.82ID:9o2+M89H0
このコードが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;
}
}
2023/06/25(日) 01:41:11.75ID:9o2+M89H0
どこかおかしい部分あるかな
2023/06/25(日) 02:14:14.53ID:0IEJDuKo0
スタックサイズ
2023/06/25(日) 02:15:11.19ID:3TXiYfiya
>>355
マルチは市ね
359デフォルトの名無しさん (ｱｳｱｳｳｰ Sa69-yAbC)
垢版 |
2023/06/29(木) 15:31:24.42ID:wEpX0/Cla
Twitterのpaizaの広告とかに必ず現れる

「入力値をチェックしていない」

という返信をつける人は、具体的に何をチェックして、どう処理するの？
360デフォルトの名無しさん (ｱｳｱｳｳｰ Sa69-yAbC)
垢版 |
2023/06/29(木) 15:35:22.33ID:wEpX0/Cla
たとえば、

・Nは偶数
・AとBの合計はN未満

といった制約は、実際のプログラムならチェックして例外をスローする
しかし、

「nが整数値じゃない場合をチェックしていない」

みたいなよくわからない難癖をつける人もいる
整数値じゃなければint型にパースするときに、ほとんどの言語で例外になるからいいのでは
361デフォルトの名無しさん (ｽﾌﾟﾌﾟ Sd43-2HPs)
垢版 |
2023/06/29(木) 15:50:34.59ID:WjHgY0Cmd
>>355
ll で dp[39][100009], A[100009];
何バイトあるん
2023/07/01(土) 22:45:27.97ID:rC0kSH/20
今回は簡単めでしたね
G解けなかったけど
2023/07/01(土) 23:33:06.19ID:x6PMIr/p0
コンテスト初参加
C問題があまりにも酷いと思った
20分くらいかけて、priorityqueue<pair<double、int>> に値をプッシュする時にpairのsecondの方にマイナスを付ければ良いことに気がついたもののWA
何を試してもWAで、doubleの精度に問題があるんじゃないかと思って、ネット検索をしたら、long doubleという型があることを知り、試してみたら無事AC
Ｃ問題で時間とメンタルを削られてD問題は諦めた
初参加とはいえ茶パフォはあまりに脳障害すぎるだろ
2023/07/01(土) 23:39:31.52ID:x6PMIr/p0
今回のＣ問題でpriorityqueueを使ったんだけど、priorityqueue<pair<double、int>> に値をプッシュする時、pairのsecondの方に-をつけて取り出す順番を工夫するのって典型？
ちょっとした閃きだけど思いついた時は俺ちょっと頭いいんじゃねって思っちゃった
その後ものの見事に脳障害っぷりを晒してしまったけど
2023/07/01(土) 23:43:47.83ID:L7MIkgdg0
その発想は天才だよ、才能あるね
2023/07/01(土) 23:50:30.60ID:wjWc9sXDp
マジレスすると符号付けて逆順にすることで実装をシンプルにするのはかなりの典型です
2023/07/01(土) 23:53:37.30ID:6JFt9TARa
むしろそのマイナスにするのが主題と言ってもいいくらい
2023/07/01(土) 23:57:08.30ID:CM44ThHXa
C++ってFraction無いんだっけ？
まあ無くても自分で通分すれば済む話だが
2023/07/02(日) 00:35:29.46ID:sYDH7cmq0
なるほど、ただの典型だったか…
ただ、その典型を自分で思いついたのはちょっと嬉しい
2023/07/02(日) 00:39:10.97ID:sYDH7cmq0
先程 D問題をACしてきた
結構簡単だし、C問題を普通に解けていたら多分四完出来た
今回のC問題みたいに本質的じゃない部分(long doubleという型を知っているかどうかみたいな)を問うのは本当にやめた方が良いと思う 問題の質がシンプルに低い
2023/07/02(日) 01:16:07.96ID:3YsXAzA4a
小数の精度についての理解を問うなかなかの良問だと思ったけどね
2023/07/02(日) 01:33:02.66ID:K/v1SCuX0
浮動小数点数での出力を求められていない場合に浮動小数点数を使うのはアンチパターン
分数を管理する構造体を持ち出したり適切な比較関数を書いたりして対処するべき
2023/07/02(日) 03:53:32.35ID:FFIcTLPjp
前回のC問題はただめちゃくちゃ面倒なだけでアレだったけど今週のC問題は何も悪くないし非本質的でもないだろ
浮動小数点数は誤差に気をつけるべきなんて競プロでは身につけておくべき典型知識だし競プロ外でも浮動小数点数の仕組みは知っておくべきだしm
2023/07/02(日) 03:56:07.16ID:FFIcTLPjp
強いて言うならlong double型で無理矢理通すような解答を弾けるような設定にして比較関数やら有理数型を表す構造体やらの整数しか登場しなくて誤差の心配がない解答のみが通るようにしてほしかったがCでそれは酷かもしれない
2023/07/02(日) 04:23:31.59ID:vN/hop9Q0
long double使わなくても解けるし、それ知らないと解けないと言ってる人のレベルが低すぎるだけ
2023/07/02(日) 08:45:23.44ID:TDPjDhzP0
E問題の意味が分からないんだが。

俺の考えたアルゴリズムは、

Mが0,1,2になる数、
Eが0,1,2になる数、
Xが0,1,2になる数、
を全て数えて

各組み合わせ27通りについて、

mex×場合分けの数

っていうやり方をしたんだがサンプル3の問題からしてそもそも合わない

日本語下手で説明難しいからコードを見てほしい。
https://atcoder.jp/contests/abc308/submissions/43167367
このやり方がなぜいけないのかわからない

コンテスト中「E問題いけるやん！」と思ってただけに絶望だったわ、はぁ。。
2023/07/02(日) 08:51:37.04ID:TDPjDhzP0
関係ないけど、dictのkeyで回せば
if k not in dic["X"]:
continue

みたいなのいらなかったな
2023/07/02(日) 08:52:36.78ID:IX/DQMpQ0
i<j<k
2023/07/02(日) 08:55:34.57ID:TDPjDhzP0
>>378
ないてもいい？
2023/07/02(日) 09:02:55.87ID:TDPjDhzP0
雑なやり方だけど、
「E」に来た時点で、それより前のMの各012の数と
それより後のXの「012」の数を保持しておけば簡単に解けたわけか
381デフォルトの名無しさん (ﾜｯﾁｮｲ ceca-Sjvf)
垢版 |
2023/07/02(日) 10:28:08.37ID:ZqX35jN50
Cみたいなのが普通に小数にしてソートして解けないとか、現実的に不要な精度を求めてるからじゃ。工夫して分数を比較とか一般的なプログラミングではあり得ない。
2023/07/02(日) 11:00:12.04ID:zHWl+4BQ0
一切の誤差が許容できないケースは業プロでもあり得ると思う
2023/07/02(日) 11:08:00.56ID:KeYtCxoR0
COBOL使われてそう
2023/07/02(日) 11:14:00.32ID:w7ISOQF/0
普通に業プロでも浮動小数点の誤差でやらかすのあるあるだけどな
とくに一致判定しだすと大抵はテストを通って後でトラブる
2023/07/02(日) 11:34:46.41ID:13GYnxJn0
むしろ業プロはバグだらけで運用でカバーするのが当たり前だか？
バグなくなるまでQAとデバッグしてたらいつまでたっても終わらない
2023/07/02(日) 11:37:01.69ID:13GYnxJn0
当たり前だが？
2023/07/02(日) 11:40:04.07ID:uPRSXMfXa
>>381
あり得ないのは誤差があることを知りながらdoubleを使うことだぞ
誤差が許容できないとわかってて整数で誤差のない計算ができることもわかってるんだから整数で計算するべき
わかってないお前が無能というだけ
388デフォルトの名無しさん (ﾜｯﾁｮｲ ceca-Sjvf)
垢版 |
2023/07/02(日) 11:40:34.10ID:ZqX35jN50
しかし、スポーツとかゲームの勝率を管理するシステムがあったとして、
小数点以下6桁以上の精度のために内部的に分子分母を整数で別々に保存してるとは思えないのだがｗｗｗ
2023/07/02(日) 11:56:01.97ID:uPRSXMfXa
思えよw
勝ち数と試合数を保存してるに決まってるだろw
2023/07/02(日) 11:57:10.10ID:uPRSXMfXa
逆に勝率だけ保存してその後の試合の結果どうすんの？w
過去の勝率からどうやって現在の勝率を計算するんだよw
391デフォルトの名無しさん (ﾜｯﾁｮｲ ceca-Sjvf)
垢版 |
2023/07/02(日) 12:04:01.86ID:ZqX35jN50
それは当然してるけど、orderbyで引き出すときに、勝率をatcoder流でソートするとか多分ないｗ
ワテが知らないだけで分数流ベイズ統計学とかあるのかｗ
2023/07/02(日) 12:04:59.74ID:762mJONda
お前の我流が間違ってるだけだぞ
2023/07/02(日) 12:50:39.91ID:3YsXAzA4a
普通に業務でもあり得るんだよなぁ
2023/07/02(日) 15:00:00.77ID:Kiw2FHRVd
>>390
n 試合後に
現在の勝率 R(n)「だけ」が判っている場合
n+1 試合後の勝率 R(n+1) は
n+1 試合目の勝ち負けが r (勝ちなら 1 負けなら 0) とすると
R(n+1) = (R(n) x n + r) / (n + 1)
で良いんじゃね
もちろん誤差は蓄積するよ
こんなこと一々描くのも恥ずかしいレベル
2023/07/02(日) 15:20:20.64ID:762mJONda
>>394
そのnは試合数じゃないのかw
こんなこといちいち書かせるなよw
2023/07/02(日) 15:24:37.03ID:vW9xhJCj0
もう少し比較条件が複雑化されて
operator<なりstd::sortに渡すラムダ式をちゃんと定義しないと駄目なら一転して教育的とかいいそう
2023/07/02(日) 23:05:02.47ID:CGuiBJy50
ARCゼロ完 地頭悪すぎる ガチで死にたい
2023/07/02(日) 23:07:06.37ID:CGuiBJy50
昨日はABC三完
今日はARCゼロ完
A問題は解けそうだったけど結局最後までAC出来ず
頭が悪すぎる
IQ1しか無いよ俺は
2023/07/02(日) 23:13:24.16ID:CGuiBJy50
数理能力皆無の知的障害者です
2023/07/03(月) 01:30:24.77ID:OPBRIWzz0
・解説開くとTwitterに飛ぶやつあるが、アカウント持ってないから見れない。
・今日のARC出題者はPCT。何千人の大人が高校生の手の上で転がされていると思うと笑える。
2023/07/03(月) 09:36:39.54ID:NXhRhmBta
大人は経験を積んでるから対応力があるわけで素の能力的には筋力でも記憶力でも計算力でも高校生くらいがピークだろ
ずっと数学に取り組んできた高校生が年食ったにわかより数学力高いのは何もおかしくない
2023/07/03(月) 09:44:41.24ID:XuaWdgM7a
女子高生ですが質問良いですか？
2023/07/03(月) 17:22:23.00ID:UseykR7Wa
女子高生は伊藤ハムと株式会社響の登録商標
2023/07/03(月) 17:33:27.76ID:hlx2Z5bC0
女子高生®
2023/07/03(月) 21:06:06.47ID:XBoVoSsZ0
女子高生++
2023/07/03(月) 21:54:41.71ID:8MjNV9lj0
32進数で18のガールです
2023/07/04(火) 01:04:41.48ID:7JsYF2E60
コードクイーンの足切りライン調べたら女性率わかりそう
2023/07/04(火) 12:50:20.11ID:1hihmjJNd
高校生の茶パフォ、大人の緑パフォが通過してるのは観測した
2023/07/04(火) 20:30:01.45ID:HVVBDHOp0
CodeQUEENの予選通過ボーダーは4000位くらいか
決勝が200人だから、予選参加者の女性率は1/20くらい？ 意外と多い
410デフォルトの名無しさん (ﾜｯﾁｮｲ 367c-4DRt)
垢版 |
2023/07/04(火) 23:33:24.09ID:iNviWYF50
普段よりは多いはずだしmaxで5%って少なすぎでは
2023/07/04(火) 23:40:14.20ID:6S0skEB80
情報系学科には5%も女子いないしそんなもんだろ
2023/07/05(水) 01:19:41.42ID:6DXjNiw00
決勝50人だという認識だけど変わった？
2023/07/06(木) 21:25:45.68ID:mwFnQ94pr
明日ICPC国内予選で、紙デバッグのためにソースコード印刷できる環境を作りたいんだけど、どういう方法で印刷するのがおすすめ？？
できれば関数とか変数に色ついた状態で印刷できるのがよくて（結局白黒印刷でそこまで判別できないんだろうけど……）、コマンド一発とかだとさらに嬉しい。

ubuntu on wslで、C++のコードを印刷する予定。
2023/07/06(木) 22:38:13.51ID:b7c0NS7t0
うんち！ｗ
2023/07/07(金) 01:30:49.16ID:1mcI69WL0
>>413
エディタでスクショ撮って印刷すれば？
それかSlidesCodeHighlighter
2023/07/07(金) 03:12:20.80ID:z4kqZgsu0
関数とか変数のfontを変えればいいんじゃないの?
2023/07/15(土) 22:42:12.55ID:x+Qg/K3m0
Fで撃沈
Dの壁がすごい
418デフォルトの名無しさん (ﾜｯﾁｮｲ 66ca-cnuG)
垢版 |
2023/07/15(土) 23:22:55.96ID:1q2XYUPT0
D難しくて４０分前に撤退
2023/07/22(土) 22:41:53.66ID:L4ADMrXM0
6完
時間あればGもいけそうないけなさそうな
2023/07/24(月) 22:17:46.28ID:E8Gan8+c0
うんち
2023/07/29(土) 23:20:17.83ID:NN0rwgAC0
終了ぎりぎりにしか参加できなかったけどEなんでこんなに少ないの
2023/08/05(土) 22:42:06.48ID:D/vhtMxo0
D解けそうで解けず
E解くの遅くなってしまった
2023/08/30(水) 18:31:09.12ID:alovhTb10
処理水放出にブチ切れた某国のハッカーがDDoS攻撃をエスカレートさせるか？
次回ABCに注目！
2023/09/23(土) 10:35:29.30ID:jxRoyGbM0
Haskellで競技プログラミングやってみたい
過去問解答つきのコンテストかオンラインジャッジって何がある？
2023/09/23(土) 11:46:13.14ID:qyvMvmTV0
うんち！w
2023/10/01(日) 15:56:56.21ID:vKLB4nokr
マ板落ちてる？
2023/10/01(日) 15:57:14.41ID:vKLB4nokr
マ板落ちてる？
2023/10/01(日) 16:15:12.67ID:XhyBuOUk0
マ板は落ちてるし、ここも調子悪いし、Xより先に5ch終わってもおかしくなさそう
2023/10/01(日) 18:55:58.51ID:XWaBOyPlM
ガイジスレ終了
430デフォルトの名無しさん (ﾜｯﾁｮｲ 0505-47+T)
垢版 |
2023/10/02(月) 08:51:52.74ID:1rOigmc00
talkのパソコン一般か、ム板の二択になるのかな？
2023/10/02(月) 11:25:29.06ID:UjKxm5VW0
ガイジのみなさんのご来訪を、本スレ民一同心よりお待ちしております
2023/10/02(月) 15:52:58.24ID:SAZFQLC/d
緑最高！
2023/10/02(月) 17:49:39.22ID:Xk1RT1SJ0
chokuから青でカンストいただきました
青agerが一歩リードか？
2023/10/04(水) 13:20:04.40ID:nwK1CNVl0
このまま5ch潰れてもいいから一緒にXも閉鎖してくれ
これでネットも平和になるしみんなの幸福度も上がるだろ
2023/10/04(水) 20:21:54.14ID:fboJjni1a
こっちは生きてるのか
2023/10/04(水) 20:58:06.36ID:3U3tGCCa0
本スレへようこそ
437デフォルトの名無しさん (ﾜｯﾁｮｲ 235b-2qr8)
垢版 |
2023/10/06(金) 16:53:30.65ID:jg1c5xSH0
[クライシスアクター」「豊島保養所」←画像検索＆拡散！

他スレに丸ごとコピペよろしっくっ！！
ネットでできる反ﾚﾌﾟﾃｨﾘｱﾝ・反ｲﾙﾐ活動です！！！！！
動画サイトのコメ欄もねらい目だぞ！！！！！！！
438あぼーん
垢版 |
NGNG
あぼーん
2023/10/28(土) 13:32:45.14ID:e4vdwJlAM
ICPC WF延期
https://codeforces.com/blog/entry/121779
2023/11/04(土) 16:28:03.75ID:XpaBBm0TF
本スレ再開
441デフォルトの名無しさん (ﾜｯﾁｮｲ 6dc3-HiwA)
垢版 |
2023/11/04(土) 16:46:16.64ID:KCu6Yt7G0
こちらに一本化しよう
442デフォルトの名無しさん (ﾜｯﾁｮｲ 6dc3-HiwA)
垢版 |
2023/11/04(土) 16:50:33.92ID:KCu6Yt7G0
今日のABCの感想もこっちに書こう
2023/11/04(土) 16:51:45.36ID:XpaBBm0TF
うん
2023/11/04(土) 17:26:47.06ID:7LtD6ckv0
ち
2023/11/21(火) 20:58:26.23ID:kTtgfW380
ガイジスレ死んだ
2023/11/21(火) 22:17:50.81ID:5HqMPdEv0
健全にアルゴリズムの議論が行われるこっちの方がいいね
2023/11/28(火) 14:07:19.23ID:/rgISlx/0
緑はセンター300点レベル
緑は境界知能レベル
緑は社会不適応者
2023/11/29(水) 02:32:01.49ID:xqH5V0kf0
本当のことを言うな
449デフォルトの名無しさん (ﾜｯﾁｮｲ bf3a-0Op2)
垢版 |
2023/12/12(火) 18:23:19.27ID:2Q51Rv3/0
緑ってなんですか？
2023/12/20(水) 17:56:23.37ID:pk0/hmWL0
緑も知らんの？
赤や青は知ってる？
451デフォルトの名無しさん (ﾜｯﾁｮｲ 631f-NelK)
垢版 |
2023/12/21(木) 14:08:39.39ID:SY9H5Zmo0
知らない
2023/12/21(木) 15:26:15.66ID:JcfXDDS80
ポケモンだぞ
453デフォルトの名無しさん (ﾜｯﾁｮｲ 631f-NelK)
垢版 |
2023/12/21(木) 18:41:30.76ID:SY9H5Zmo0
ポケモンか・・・余計にわからんわw
2024/02/26(月) 12:05:02.65ID:vifm+9f80
誰かいますか？
2024/02/26(月) 13:43:02.39ID:z8mAy46Q0
いませんよ
456デフォルトの名無しさん (ﾜｯﾁｮｲ 339b-7efP)
垢版 |
2024/02/27(火) 14:30:48.92ID:0J04Un9A0
い、い、い、いませんよ
2024/03/02(土) 16:17:30.83ID:mD9CgiFs0
abcってcまでは名前ついてるアルゴリズムは絶対不要でしょうか？
2024/03/02(土) 22:54:36.00ID:6/wbHV2ha
d3分オーバーで解けたのに悔しい😭
2024/03/14(木) 20:32:31.05ID:4Vkd17kg0
>>457
線形探索とか使うよね
2024/03/21(木) 11:47:14.44ID:jsHau+G+0
何か太ましい
https://article.yahoo.co.jp/detail/c8cdecddb22f0a1cdf74539e2cafd8356184596a
2024/03/21(木) 12:21:14.26ID:rDQztVEL0
天才プログラマーはいまだ成長中ということ
2024/04/19(金) 18:16:54.50ID:FRYEa2Zy0
どこも書き込めんわ
2024/07/25(木) 19:20:19.74ID:vAw9wUiS0
本スレの時代きたな
2024/07/25(木) 21:12:02.40ID:H+vcKyNb0
ワッチョイありの方がいいね
2024/07/25(木) 21:58:57.94ID:vAw9wUiS0
それはそう
2024/07/25(木) 23:38:06.15ID:YmWtsF4o0
ガイジスレ嫌われてて草
2024/10/19(土) 05:08:25.95ID:SUgcunIqM
世の中IQなの？
おれwais検査の結果IQ119だった絶望
赤マスさんみたいな脳がほしかった
2024/10/24(木) 23:41:09.47ID:7cG4d91K0
馬鹿が何作るの？って話だわな
469デフォルトの名無しさん (ﾜｯﾁｮｲ a325-gs3f)
垢版 |
2024/11/11(月) 22:36:11.66ID:MPmtK6g60
また本スレの時代が帰ってきたな
もうここだけでいいよ
2024/11/11(月) 22:42:01.87ID:9obeAX070
ガイジスレやっと終了したか
2024/11/12(火) 09:02:29.67ID:iuEQfh/S0
ガイジスレ終了
2024/11/13(水) 10:13:57.00ID:9mozrIA1M
ガイジスレ終了
2024/11/13(水) 17:28:18.76ID:7etISFVT0
ガイジスレ開始
2024/12/24(火) 13:01:41.41ID:7hDg2JYL0
ガイジスレ終了
2025/01/16(木) 19:05:38.66ID:i/XAt3I90
ガイジスレ終了
476デフォルトの名無しさん (ﾜｯﾁｮｲ 53af-LZB9)
垢版 |
2025/01/24(金) 22:51:23.50ID:pX5+qcQ20
忌み数字を踏ませる業者、アプリ、コンピュータプログラムの嫌がらせ

動画再生回数、表示回数、登録者数、フォロワー数、評価数、コメント数、レベル、経験値、ポイント、HP、通貨、価格、メッセージ数、通知数、フレンド数

4（死）、13（キリスト教における忌み数字）

18（嫌）、24（〜に死）、34（〜さん死）

40、42、44

56（殺）、64（無視）

71（無い）、74（無し）、79（無く、亡く）

84（〜は死）、94（〜君死）、96（黒）

このような数字と名前や生年月日、IDなどを組み合わせて執拗に強調することで、精神攻撃をする業者やストーカー、嫌がらせ組織がキモい。
2025/01/27(月) 03:01:46.93ID:MRBGot2f0
>>476
お大事に
2025/02/13(木) 17:49:53.29ID:6bYvU5k10
ガイジスレ終了
新着レスの表示
レスを投稿する

5ちゃんねるの広告が気に入らない場合は、こちらをクリックしてください。
ニューススポーツなんでも実況