アルゴリズム実技検定（PAST）ってどうですか？

1 ：デフォルトの名無しさん：2021/03/13(土) 08:31:14.54 ID:apj29DI2.net

受ける意味ある？

2 ：デフォルトの名無しさん：2021/03/13(土) 11:41:04.55 ID:Xt+x/mlU.net

>>1
お前が受けても受からない

3 ：デフォルトの名無しさん：2021/03/13(土) 15:08:07.90 ID:f5S30BZg.net

毎日アルゴリズム体操やってるのに力がつきません…

4 ：デフォルトの名無しさん：2021/03/13(土) 21:18:56.21 ID:+/gF4ceM.net

>>1
マ板にも同じ糞スレを立ててただろ

5 ：デフォルトの名無しさん：2021/10/01(金) 16:32:05.62 ID:O2R0V5cQ.net

atcoderのサイトのトップから過去問のページへリンクが貼られていないのはなぜですか？
Googleで検索するとたどり着けます。

6 ：デフォルトの名無しさん：2021/10/01(金) 16:54:57.70 ID:xAAYN8E1.net

ODPT

7 ：デフォルトの名無しさん：2021/10/01(金) 18:01:32.00 ID:I8Z+rzQA.net

トップページ(https://atcoder.jp/)には過去問公開中というリンクがありますよ
たくさん解きたい人はコンテスト一覧>過去のコンテスト>PAST過去問にあります
https://atcoder.jp/contests/archive?category=50
外部サイトのAtCoder Problemsも有用です
https://kenkoooo.com/atcoder/

8 ：デフォルトの名無しさん：2021/10/01(金) 18:28:07.19 ID:O2R0V5cQ.net

>>7
ありがとうございました。

9 ：デフォルトの名無しさん：2021/10/24(日) 20:41:29.55 ID:tzzO99P4.net

https://atcoder.jp/contests/past202004-open/tasks/past202004_f

この問題は貪欲法が適用できるとのことですが、適用できることの証明はどう証明するのでしょうか？

10 ：デフォルトの名無しさん：2021/10/25(月) 11:22:57.01 ID:vmRZrQEp.net

最適であることを証明するのではなく適用出来るだけなら実装すれば良いのでは？

11 ：デフォルトの名無しさん：2021/10/26(火) 10:49:48.99 ID:CwYCZWUI.net

>>9

以下のような感じで証明できないですかね？

タスク T のポイントを p(T) で表すことにする。

貪欲法によって選ばれたタスク列を

T_1, T_2, …, T_n

とする。

S := {(S_1, S_2, …, S_k) | 1 ≦ k ≦ n, S_i は第i日に行うタスク, p(S_1 + … + S_k) > p(T_1 + … + T_k)}

S が空集合ではないとして矛盾を導く。

(S_1, S_2, …, S_l) を長さが最小の S の元とする。

p(S_1) + … + p(S_{l-1}) ≦ p(T_1) + … + p(T_{l-1})

12 ：デフォルトの名無しさん：2021/10/26(火) 11:35:46.60 ID:CwYCZWUI.net

>>9

タスク T のポイントを p(T) で表すことにする。

貪欲法によって選ばれたタスク列を

T_1, T_2, …, T_n

とする。

S := {k | 1 ≦ k ≦ n, 第1日目から第k日目の間に得られるポイントの合計の最大値 > p(T_1) + … + p(T_k)} が空集合ではないと仮定して矛盾を導く。

k_0 := min S とおく。

第1日目から第k_0日目の間に得られるポイントの合計の最大値を達成するタスク列を

S_1, S_2, …, S_{k_0} とする。

仮定により、

p(S_1) = p(T_1)
p(S_2) = p(T_2)
…
p(S_{k_0-1}) = p(T_{k_0-1})
p(S_{k_0}) > p(T_{k_0})

が成り立つ。

13 ：デフォルトの名無しさん：2021/10/26(火) 11:36:05.88 ID:CwYCZWUI.net

このとき、長さ n のタスク列 S_1, S_2, …, S_{k_0-1}, R_{k_0}, R_{k_0+1}, …, R_{n} で

p(R_{k_0}) = p(T_{k_0})
p(R_{k_0+1}) = p(T_{k_0+1})
…
p(R_{n}) = p(T_{n})

を満たすようなものが存在することは明らかである。

このタスク列 S_1, S_2, …, S_{k_0-1}, R_{k_0}, R_{k_0+1}, …, R_{n} も貪欲法によって選ばれうるタスク列である。

ところが、タスク列 S_1, S_2, …, S_{k_0-1}, R_{k_0}, R_{k_0+1}, …, R_{n} は第k_0日において、 p(S_{k_0}) > p(T_{k_0}) = p(R_{k_0}) であるにもかかわらず、
タスク S_{k_0} を選択しないタスク列であるから、このタスク列は貪欲法によって選ばれうるタスク列ではない。

これは矛盾である。

よって、 S は空集合である。

14 ：デフォルトの名無しさん：2021/10/26(火) 15:26:24.78 ID:4xSLwudN.net

まるちんこ

15 ：デフォルトの名無しさん：2021/10/31(日) 19:17:07.83 ID:BY7qrcrb.net

https://atcoder.jp/contests/nikkei2019-qual/tasks/nikkei2019_qual_c

↓途中の段階で最終的に得られる互いの幸福度の総和をどうやって彼らは知るのでしょうか？


ただし、彼らはともに、「最終的に自分が得る幸福度の総和」から「最終的に相手が得る幸福度の総和」を引いた値を最大化するように料理を選びます。

このとき、「最終的に高橋くんが得る幸福度の総和」から「最終的に青木さんが得る幸福度の総和」を引いた値はいくつになるでしょうか？

16 ：デフォルトの名無しさん：2021/11/02(火) 14:08:09.04 ID:RQoewYsN.net

『Algorithm Design』は、競技プログラミングに向いた正統派の教科書だと思いますが、いかがですか？

17 ：デフォルトの名無しさん：2022/03/05(土) 12:32:12.67 ID:c2cv6ICZ.net

https://i.imgur.com/5WatPk9.jpg

18 ：デフォルトの名無しさん：2023/12/26(火) 09:17:35.65 ID:R4gIzqdA2

選挙したことのないクソシナは常に党員監視されて汚職て゛も発見されようものならただちに失脚厳罸二度と表に出てこられなくなるか゛
選挙が意味のない日本では自民公明による汚職は誤魔化され隠蔽され税金で補填され合法化まて゛されるのが当たり前
この世界最悪の腐敗組織の代わりとして期待されていた維新は軍拡思想と憲法の下の平等も世代による公平も理解て゛きないクス゛だらけ
それでもまだ自民公明よりマシた゛ろ思われていたところ馬場伸幸みたいな老害か゛関西地球破壞力シ゛ノ萬博だの立ち上け゛た上に事業通した後て゛
税金泥棒予算倍増する戦中の戰艦みたいな，汚職五輪からすら何ひとつ学ふ゛こともせす゛押し通し続けるあたりオワコン確定しちまったな
氣候変動させて災害連発させて儲けてる強盜殺人の首魁蓄財3億圓超の斎藤鉄夫以上の資産を持つ者が後継者を欲しているわけて゛もない
子育て費とか親にとって賭博や風俗と同類の遊興費なわけた゛か゛それを赤の他人に支払わせようとか遺棄罪適用されるへ゛き犯罪者に追い銭
くれてやるのと同し゛だろ、そんなクズに育てられたら地球破壞して國を蝕む不良債権にしか育たねえわホ゛ケシ゛ジィ
(ref.) ttps://www.call4.jp/info.php?type=items&id=I0000062
ttps://haneda-project.jimdofree.com/ , ttps://flight-route.com/
ttps://n-souonhigaisosyoudan.amebaownd.com/