競技プログラミング総合スレ 66 (478レス)
1-

178: (ブーイモ MMf6-tIu7) 2023/04/09(日)22:42 ID:fJZ93dkaM(1) AAS
序盤からムズすぎ
179: (ワッチョイ d9b0-OQ9P) 2023/04/09(日)22:44 ID:0uKKY8S80(1) AAS
Eむずい
setとpriority queueいじくってたら通った
180: (ササクッテロラ Spd1-x1gv) 2023/04/09(日)22:47 ID:DKklNxRop(1) AAS
E二分探索でやろうとしたらハマって普通にsetで順番にみるだけだった
F解けたのに今回も解いてる人の数がF<Gなせいであまり順位伸びてないの配点何とかして欲しいわ
181
(2): (スッップ Sd22-QZiB) 2023/04/09(日)23:58 ID:BvehXBT4d(1) AAS
整数式の倍数判定のプログラム作りたいんだけどできる?
nは自然数

例1

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

(入力した式の倍数判定。6の倍数)
2の倍数でも3の倍数でもあるが、最も大きい数を出力
省3
182: (ワッチョイ eebb-Sq7r) 2023/04/10(月)02:32 ID:Gn/yyThB0(1) AAS
>>181
nに素数をいくつか突っ込んだ値(0以外)で最大公約数とればいいんでない?
という気はするけど万年茶色脳には正しいか証明するなんてムリ
183: (ワッチョイ bd5f-EL/2) 2023/04/10(月)02:49 ID:zrtbja+Y0(1/3) AAS
素数pの倍数かどうかはmod pが整域だから多項式は根を高々次数d個しかもたないのでp≤dだけ調べればいいよね
p^kはわからん
184
(1): (ワッチョイ bd5f-EL/2) 2023/04/10(月)03:22 ID:zrtbja+Y0(2/3) AAS
fが零因子⇔あるa≠0が存在してaf=0らしいから、最初にfを係数のgcdで割っとけば零因子じゃなくなって、p^k≤dだけ調べればいいと思う
185: (ワッチョイ bd5f-EL/2) 2023/04/10(月)03:46 ID:zrtbja+Y0(3/3) AAS
>>184
これ全部嘘です 寝るか
186
(1): (ブーイモ MMf6-tIu7) 2023/04/10(月)13:12 ID:Sbe/ma/bM(1/2) AAS
mod p で何代入しても0になる多項式は例えば x(x-1)...(x-p+1) でp次を達成できて最適
mod p^n だとこれをn乗すると構成できるので(最適かは知らんが)pn次以下と評価できる
だからpnがd以下の範囲を探索すれば良いが計算量は悪いな
187: (ブーイモ MMf6-tIu7) 2023/04/10(月)13:16 ID:Sbe/ma/bM(2/2) AAS
>>186
馬鹿すぎ、評価すべき方向が逆
188: (ワッチョイ d9b0-OQ9P) 2023/04/10(月)15:49 ID:1oGpX4FF0(1) AAS
Fはやってみたら簡単に解けた
Gはgrundy数求めるとき単純な勘違いしてた
むー悔しい
189: (ワッチョイ 8255-dXWb) 2023/04/10(月)16:05 ID:/Pv3NVQa0(1/5) AAS
DAGの最長パスを求める問題について質問があります。

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

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

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

indegreeが0になる頂点から処理を行い、その後、処理された頂点から出る辺を削除することで、
省3
191: (ワッチョイ 8255-dXWb) 2023/04/10(月)16:13 ID:/Pv3NVQa0(2/5) AAS
DAGであれば、最長パスが存在し、それはDPで求められる。

ただそれだけのことではないでしょうか?
192: (ワッチョイ 412d-dXWb) 2023/04/10(月)16:19 ID:GqegRxcS0(2/4) AAS
はい、おっしゃる通りです。DAGであれば、最長パスが存在し、動的計画法(DP)を用いて求めることができます。

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

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

一方、トポロジカルソートを適用しないDPでは、無駄な計算が発生する可能性があります。
例えば、メモ化再帰を用いたDPの場合、計算量は最悪O(2^V)になることがあります。
省1
195
(1): (ワッチョイ 417c-g1pj) 2023/04/10(月)19:58 ID:6t40mDb70(1) AAS
>>181
多項式 f(n) について計算したい
calc(f) で求めたい値を返す関数として
f が定数ならそれを返す
定数でないなら g(n)=f(n+1)-f(n)
とgを定めて
calc(f) = gcd(f(1), calc(g))
省1
196: (ワッチョイ 8255-dXWb) 2023/04/10(月)20:30 ID:/Pv3NVQa0(4/5) AAS
『アルゴリズム実技検定公式テキストエントリー〜中級編』に載っている
DAGの最長パスを求めるコードでは、トポロジカルソートを陽には使っていないです。
197
(1): (アウアウウー Sa05-ynyP) 2023/04/10(月)21:31 ID:Qr60KJ2xa(1/2) AAS
その本持ってないからその本の解法教えて
そしたら質問の回答するよ
198: (ワッチョイ 8255-dXWb) 2023/04/10(月)21:57 ID:/Pv3NVQa0(5/5) AAS
>>197
ソースコードは以下です:
github.com/kenkoooo/pastbook-source-code/blob/master/chukyu/python/chapter06/section04/6-4-8.py
199
(1): (アウアウウー Sa05-ynyP) 2023/04/10(月)22:22 ID:Qr60KJ2xa(2/2) AAS
確かに陽にトポロジカルソートはしてないね
値が確定する順序がトポロジカルソート順の逆順にはなってるけど

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

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

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

トポロジカルソートを使ってそのコードを書き換えるとこうなります。
外部リンク:ideone.com
201: (ワッチョイ 06d7-IjNm) 2023/04/11(火)00:50 ID:AEAouguL0(1/2) AAS
んげりいいいいいいいwwwwww
202: (ワッチョイ 8255-dXWb) 2023/04/11(火)10:56 ID:KVT1yw8N0(1/9) AAS
>>199-200
ありがとうございました。

>>200
コードを見たのですが、

# トポロジカルソートで得られた順序に沿って最長経路を更新
for u in order:
for v in edges[u]:
省3
203: (ワッチョイ 8255-dXWb) 2023/04/11(火)11:11 ID:KVT1yw8N0(2/9) AAS
for u in order:
■■■■print(u)

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

order.append(u)

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

そうだとすると、 order[0], order[1], … は queue から出てきた順に並べたものになりますよね。
204: (ワッチョイ 8255-dXWb) 2023/04/11(火)11:15 ID:KVT1yw8N0(3/9) AAS
多分、単純な勘違いなんですが、どこを勘違いしているのかが分かりません。
205: (ワッチョイ 8255-dXWb) 2023/04/11(火)11:16 ID:KVT1yw8N0(4/9) AAS
あ、分かりました。
与えられた有向グラフの辺の向きをすべて逆にしても、最長パスの長さは変わりませんね。
206: (ワッチョイ 8255-dXWb) 2023/04/11(火)11:35 ID:KVT1yw8N0(5/9) AAS
以下のコードは全く無駄なことをやっていますが、自分の理解通りなのはこちらのコードです:
ideone.com/gMUZDZ
207: (ブーイモ MM66-NK+R) 2023/04/11(火)13:43 ID:FMwVbediM(1) AAS
すまん初めてこのスレ来たんだけど連投してるやつはネームド?
208: (オッペケ Srd1-Ofdo) 2023/04/11(火)14:46 ID:vCEpO63Mr(1) AAS
ネームド志望
209: (ブーイモ MM66-tIu7) 2023/04/11(火)15:09 ID:F0CC9LzbM(1) AAS
>>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 ID:KVT1yw8N0(6/9) AAS
pythonで2分探索を行う bisect というものがあります。

bisect.bisect(l, a)

としたとき、 a in l であるかどうかも判定したいのですが、そのような関数は用意されていませんか?
自分で作るしかないですかね?
211: (ワッチョイ 8255-dXWb) 2023/04/11(火)18:42 ID:KVT1yw8N0(7/9) AAS
Pythonに2分探索で整列済みのリスト l に要素 a が含まれるかどうかを調べる関数はありますか?
212: (ワッチョイ 8255-dXWb) 2023/04/11(火)18:44 ID:KVT1yw8N0(8/9) AAS
もちろん、 bisect を使って、簡単に実装できますが、用意されている関数はないですか?
213: (ワッチョイ 06d7-IjNm) 2023/04/11(火)19:14 ID:AEAouguL0(2/2) AAS
がんばれ
214: (ワッチョイ 8255-dXWb) 2023/04/11(火)19:20 ID:KVT1yw8N0(9/9) AAS
まあ、以下のコードでいいと思うのですが、車輪の再発明はしたくないですよね。

i = bisect.bisect_left(l, a)
if l[i] == a:
return True
else:
return False
215: (ワッチョイ 85a4-Az6A) 2023/04/11(火)23:36 ID:HQTQbeZV0(1) AAS
車輪の再発明はしたくないですよ
216
(1): (ワッチョイ e9ad-RYvx) 2023/04/12(水)00:15 ID:9s1XLAQx0(1) AAS
公式を読めと言いたいが
外部リンク[html]:docs.python.org
集合でも管理してinで判定すれば良いのでは(´・ω・`)
217
(1): (テテンテンテン MM66-NK+R) 2023/04/12(水)09:07 ID:tXIe9h+KM(1) AAS
今IT系とは全く別の職種だから転職したくてAtCoder始めたけど楽しいな
未経験で他職種に転職出来るのか分からんけど
218
(1): (アウアウウー Sa05-NO7/) 2023/04/12(水)09:21 ID:g9fBg21da(1/2) AAS
>>216
2分探索することは確定でそこで発見できるのにそれに加えてわざわざ他の集合を使う意味とは?
219
(1): (アウアウウー Sa05-NO7/) 2023/04/12(水)09:24 ID:g9fBg21da(2/2) AAS
>>217
最低緑以上になればJobsで転職できる可能性はあるが緑っていっぱいいるので年齢や運が絡むかもな
220: (テテンテンテン MM66-NK+R) 2023/04/12(水)09:48 ID:VY8vydj+M(1) AAS
>>219
ありがとう
数学好きでアルゴリズムも昔やったことあったから緑まではすんなりいけたわ
今は水色目指して色々やってるけどアルゴリズム的要素より数学要素のほうが多く感じるな
年齢は25だからあと3年位がギリギリかなあと思ってる
221
(1): (アウアウウー Sa05-rH7V) 2023/04/12(水)10:00 ID:e73VjvEsa(1) AAS
水より緑の方が採用しやすい
ほんとに転職したいなら水まで行ったらとか思わない方がいい
222: (テテンテンテン MM66-NK+R) 2023/04/12(水)12:09 ID:SHZyHyDIM(1) AAS
>>221
今年色々あって復職したてだから転職活動するなら来年以降かもしれんわ、一応ビズリーチとか登録はしたけど
水色より緑のほうが採用しやすいのはなぜ?
223: (スッププ Sd22-QZiB) 2023/04/12(水)17:15 ID:d+uvLod6d(1) AAS
今から狂気プログラミング始めるならPythonでいいかな、
224: (ワッチョイ 412d-dXWb) 2023/04/12(水)18:22 ID:7SV2gFKB0(1) AAS
brainfuckがいいと思うよ
225
(1): (ワッチョイ 8255-dXWb) 2023/04/12(水)20:36 ID:AXD/P1A20(1/2) AAS
以下の問題ですが、パスするまでに1日かかりました。

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

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

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

ideone.com/NY8mNY
226: (ワッチョイ 8255-dXWb) 2023/04/12(水)20:42 ID:AXD/P1A20(2/2) AAS
あ、模範解答を見たら、実装するのも実は大変じゃないんですね。
227: (ワッチョイ d907-NO7/) 2023/04/13(木)14:51 ID:YZ8/Xbx00(1) AAS
>>225
> こういうアイディアはほとんど必要がないけれども、実装するのが大変という
> 問題の対処方法を教えてください。
「アイデアを出すか頑張って実装する」以外の答えが思いつかんのだが真面目に聞いてるのか?
228: (ワッチョイ 8255-dXWb) 2023/04/13(木)16:57 ID:lV5klkX+0(1) AAS
実装大変だなーと思ったら、自分のアイディアが悪いと思ってまず間違いないですか?

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

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

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

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

また、安保理が18日に北朝鮮のICBM発射について緊急会合を開催することになりました。²

ロシアはウクライナ侵攻で敗色濃厚であり、北朝鮮の核ミサイル開発にも深刻な影響を受けているという記事もありました。³

これらの情報はあなたの興味に沿っていますか?
省6
234: (テテンテンテン MM8f-H/xe) 2023/04/15(土)22:26 ID:KbvfxJ7qM(1) AAS
今回のABCレート不具合で変動なしらしいな
苦手分野過ぎてAとBしか解けなかったからありがたいわ
235: (ワッチョイ 47b0-AIBz) 2023/04/15(土)22:42 ID:hxYUx3pC0(1/2) AAS
5完
バグりまくるし止まりまくるし散々だった
236: (ワッチョイ c7ad-/dh0) 2023/04/15(土)22:45 ID:2lW0lXjE0(1/2) AAS
>>218
調子良かったのにunratedかよ☹
237: (ワッチョイ c7ad-/dh0) 2023/04/15(土)22:55 ID:2lW0lXjE0(2/2) AAS
のんびり解いてた割には暖まるなあと思ってたけどこれDDoSの影響で普段速く解く人が遅れたってことか🥶
238: (ワッチョイ 47b0-AIBz) 2023/04/15(土)23:06 ID:hxYUx3pC0(2/2) AAS
あと5分あったらF修正して解けてた…
239: (ワッチョイ 4707-uZLY) 2023/04/16(日)16:50 ID:+7pzCas80(1) AAS
Twitterリンク:chokudai
マルチchokudaiサーチがダサくないと思ってるところに草生える
Twitterリンク:5chan_nel (5ch newer account)
240: (ワッチョイ 67a4-ws6F) 2023/04/16(日)18:18 ID:iQzJN3tu0(1) AAS
研究者が自分の名前を手法に付けることは、研究コミュニティで一般的には推奨されていません。ただし、研究者が特定の手法やアルゴリズムを開発した場合、その手法が他の研究者や専門家によって引用されることがあります。この場合、研究者の名前が手法に関連付けられることがあります。
241
(1): (ワッチョイ 072d-7nfa) 2023/04/16(日)18:55 ID:uh3dAZwl0(1) AAS
今回のCでどうしても3つTLEが潰せない
242: (アウアウウー Sacb-uZLY) 2023/04/16(日)19:06 ID:Ke39kkrTa(1) AAS
どうしても自力で解けないなら解説読んでいいんじゃね
243: (オッペケ Srfb-g0sp) 2023/04/16(日)22:30 ID:SVYFRHN6r(1) AAS
もし自分でアルゴリズム開発したらかっこいい略称付けたいよね
244: (アウアウウー Sacb-4m2x) 2023/04/16(日)22:32 ID:XfEQvCuWa(1) AAS
>>241
俺かよ
PriorityqueやSortedSetを使わずに普通の配列やSetを使って出力時に都度ソートしたら行けた
自前のライブラリだと重すぎるみたいだな
245
(1): (ワッチョイ 5f55-7nfa) 2023/04/17(月)08:58 ID:5c7uVWzN0(1) AAS
Aho, Hopcroft and UllmanのThe Design and Analysis of Computer Algorithmsという
非常に古い本はもうゴミのような本でしょうか?
246: (オッペケ Srfb-Lcwe) 2023/04/17(月)12:28 ID:WWhqmq79r(1) AAS
今アホって言った?
247: (ワッチョイ 07da-vbZL) 2023/04/17(月)22:20 ID:5e6VxUA80(1) AAS
最近は自分で判断できない輩が増えてきたな。
248: (ワッチョイ c705-9i6p) 2023/04/17(月)22:52 ID:LKkslgOL0(1) AAS
>>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は、歴史的な価値があるという点でゴミのような本とは言えませんが、現代のアルゴリズム研究や技術を学ぶ上で最も適切な教材ではないかもしれません。学ぶ内容に応じて、より新しいリソースや書籍を利用することを検討してみてください。
249: (ワッチョイ 7fd6-GSlL) 2023/04/17(月)23:36 ID:y8gbGQlA0(1) AAS
アルゴリズムデザイン、重版されて書店に並んでて嬉しかった
250
(1): (アウアウウー Sacb-J8Vk) 2023/04/20(木)19:31 ID:f2njLhGLa(1) AAS
外部リンク:mathlog.info

今までにない斬新なセグ木の解説記事
251: (アウアウウー Sacb-uZLY) 2023/04/20(木)19:42 ID:mhtgTGfFa(1) AAS
>>250
その下のスーパー某もすごいな
252: (オッペケ Srfb-Lcwe) 2023/04/21(金)12:31 ID:Oi9Mt79Gr(1) AAS
レートは?書いた人の
253: (アウアウウー Sacb-uZLY) 2023/04/21(金)13:07 ID:/VhDvdfwa(1/3) AAS
正確な数値はともかく灰色以外の何に見えるんだ?
254: (オッペケ Srfb-Lcwe) 2023/04/21(金)13:16 ID:wvR7tFMwr(1) AAS
読む価値があるか確認するために聞いたんだけど
255: (アウアウウー Sacb-uZLY) 2023/04/21(金)13:19 ID:/VhDvdfwa(2/3) AAS
ないよ
256: (ワッチョイ bfd7-KgtD) 2023/04/21(金)13:20 ID:Va2XyxIX0(1/2) AAS
ないアルヨ
257: (アウアウウー Sacb-uZLY) 2023/04/21(金)13:23 ID:/VhDvdfwa(3/3) AAS
ないのかあるのかどっちだと突っ込んでほしいジジイおるな
258: (ワッチョイ bfd7-KgtD) 2023/04/21(金)13:26 ID:Va2XyxIX0(2/2) AAS
ツッコんでほしいアルヨ
1-
あと 220 レスあります
スレ情報 赤レス抽出 画像レス抽出 歴の未読スレ AAサムネイル

ぬこの手 ぬこTOP 0.016s