狠狠撸

狠狠撸Share a Scribd company logo
Codeforces #162
   Div1-C,Div2-E
Choosing Balls
     Writer: hogloid
    improvement: snuke
cooperation: rng_58,degwer
? N個のボールが一列に並んでいます
? それぞれのボールには,色?価値が定めら
れています
? あるボールの列の価値は以下のように定
  められます
? あるボールが列の先頭,もしくは一つ前の
  ボールと色が違うなら,(ボールの価値)*b
? そうでないなら,(ボールの価値)*a
? 列の価値はボールはこれらの数の和
? N個のボールの中から,相対的な順序を変えず
  に一部のボールを取り出します(部分列を取
  ります)
? (a,b)のペアがQ個与えられるので,それぞれ
  の(a,b)について,選べるボールの部分列の
  価値の最大値を答えなさい ただし,空の列の
  価値は0とします。
? 1<=N<=100000 1<=Q<=500
? -100000<=a,b,ボールの価値<=100000
? 1<=ボールの色<=N
? クエリーと聞いて前処理が頭をよぎるか
  も知れませんが,O(NQ)なら間に合いそう
? O(QNlogN)はO(10^9)ぐらいになるのでか
  なり危険???(実際通りません)
? それぞれのクエリーについて独立に考え
  てみます
? 妥当にDPを考えてみましょう
? dp[i]:=列の最後の色がiとなるような部
  分列の最大価値
? i番目のボールの色をColor[i],価値を
  Value[i]とおくと,
? dp[Color[i]] を,
①dp[Color[i]]+a*Value[i] か
②dp[j]+b*Value[i] (1<=j<=N,j!=Color[i])
  に更新することができます
? ボールを順に見てこの更新を繰り返す
? ナイーブな実装で、O(N^2)
? ①のパターンはO(1)で楽勝
? ②は、よくあるパターンとしてColor[i]
  の左、右で分けると、それぞれの区間の
  最大値を求め、最大値に+Value[i]*bす
  ればOK
? Range Minimum Query&更新!
? Segment Tree!!!
? しかし、更新/RangeMinimum Queryを
  どちらもO(1)で解くのはセグメント木で
  は無理そう???
? logが一つかかると、TimeLimitにも間に
  合いそうにない
? 別のO(1)で更新する方法を考えよう
? dp配列の上位二つの(最後の色、価値)を
  持っていれば、あらゆる色でも、違う色
  の最大値がどちらかにはある
? dp配列の値の更新は常に増加するので、
  消去などの面倒なことが起こらず、更新
  はどれもO(1)で可能
? 少し場合分けが必要です ここでのWAがか
  なり多かった
? First Acceptance: KADR 25m24s
? Japanese First Acceptance: Komaki
  27m50s
? Accepted User/All Rated User/All
  Submission:236/566/916
? 普段のCよりかなり解かれました
? 赤族やそれに準ずる人はCを解けないと厳
  しかったかもしれません
? バグで詰まってる人が多くて悲しかった
? First Acceptance: Moor 70m52s
? Japanese First Acceptance: ikouki
  108m6s
? Accepted User/All Rated User:
  12/1526
? Div2-Eとしては理想的な解かれ具合だと
  思います
? これが解ける人は早くdiv1に来ましょう!
? いつかまた問題を作ったときはよろしく
お願いします

  ? Codeforcesの

  トップページを飾った
  名誉なLissくん→
Ad

Recommended

分割木
分割木
Kohji Liu
?
JOIss2013
JOIss2013
Shunya Satake
?
直交领域探索
直交领域探索
okuraofvegetable
?
ABC2015 Summer LT
ABC2015 Summer LT
Kensuke Onishi
?
ユークリッド最小全域木
ユークリッド最小全域木
理玖 川崎
?
グラフと木
グラフと木
京大 マイコンクラブ
?
FOSS4G 2014 Hokkaidoハンズオン - PostGIS入門
FOSS4G 2014 Hokkaidoハンズオン - PostGIS入門
Hideo Harada
?
折り纸とコンパスで计算してみよう@ノラヤ?サイエンス?バー
折り纸とコンパスで计算してみよう@ノラヤ?サイエンス?バー
Junpei Tsuji
?
2024 Trend Updates: What Really Works In SEO & Content Marketing
2024 Trend Updates: What Really Works In SEO & Content Marketing
Search Engine Journal
?
Storytelling For The Web: Integrate Storytelling in your Design Process
Storytelling For The Web: Integrate Storytelling in your Design Process
Chiara Aliotta
?
Artificial Intelligence, Data and Competition – SCHREPEL – June 2024 OECD dis...
Artificial Intelligence, Data and Competition – SCHREPEL – June 2024 OECD dis...
OECD Directorate for Financial and Enterprise Affairs
?
How to Leverage AI to Boost Employee Wellness - Lydia Di Francesco - SocialHR...
How to Leverage AI to Boost Employee Wellness - Lydia Di Francesco - SocialHR...
SocialHRCamp
?
2024 State of Marketing Report – by Hubspot
2024 State of Marketing Report – by Hubspot
Marius Sescu
?
Everything You Need To Know About ChatGPT
Everything You Need To Know About ChatGPT
Expeed Software
?
Product Design Trends in 2024 | Teenage Engineerings
Product Design Trends in 2024 | Teenage Engineerings
Pixeldarts
?
How Race, Age and Gender Shape Attitudes Towards Mental Health
How Race, Age and Gender Shape Attitudes Towards Mental Health
ThinkNow
?
AI Trends in Creative Operations 2024 by Artwork Flow.pdf
AI Trends in Creative Operations 2024 by Artwork Flow.pdf
marketingartwork
?
Skeleton Culture Code
Skeleton Culture Code
Skeleton Technologies
?
PEPSICO Presentation to CAGNY Conference Feb 2024
PEPSICO Presentation to CAGNY Conference Feb 2024
Neil Kimberley
?
Content Methodology: A Best Practices Report (Webinar)
Content Methodology: A Best Practices Report (Webinar)
contently
?
How to Prepare For a Successful Job Search for 2024
How to Prepare For a Successful Job Search for 2024
Albert Qian
?
Social Media Marketing Trends 2024 // The Global Indie Insights
Social Media Marketing Trends 2024 // The Global Indie Insights
Kurio // The Social Media Age(ncy)
?
Trends In Paid Search: Navigating The Digital Landscape In 2024
Trends In Paid Search: Navigating The Digital Landscape In 2024
Search Engine Journal
?
5 Public speaking tips from TED - Visualized summary
5 Public speaking tips from TED - Visualized summary
SpeakerHub
?
ChatGPT and the Future of Work - Clark Boyd
ChatGPT and the Future of Work - Clark Boyd
Clark Boyd
?
Getting into the tech field. what next
Getting into the tech field. what next
Tessa Mero
?
Google's Just Not That Into You: Understanding Core Updates & Search Intent
Google's Just Not That Into You: Understanding Core Updates & Search Intent
Lily Ray
?
How to have difficult conversations
How to have difficult conversations
Rajiv Jayarajah, MAppComm, ACC
?

More Related Content

Featured (20)

2024 Trend Updates: What Really Works In SEO & Content Marketing
2024 Trend Updates: What Really Works In SEO & Content Marketing
Search Engine Journal
?
Storytelling For The Web: Integrate Storytelling in your Design Process
Storytelling For The Web: Integrate Storytelling in your Design Process
Chiara Aliotta
?
Artificial Intelligence, Data and Competition – SCHREPEL – June 2024 OECD dis...
Artificial Intelligence, Data and Competition – SCHREPEL – June 2024 OECD dis...
OECD Directorate for Financial and Enterprise Affairs
?
How to Leverage AI to Boost Employee Wellness - Lydia Di Francesco - SocialHR...
How to Leverage AI to Boost Employee Wellness - Lydia Di Francesco - SocialHR...
SocialHRCamp
?
2024 State of Marketing Report – by Hubspot
2024 State of Marketing Report – by Hubspot
Marius Sescu
?
Everything You Need To Know About ChatGPT
Everything You Need To Know About ChatGPT
Expeed Software
?
Product Design Trends in 2024 | Teenage Engineerings
Product Design Trends in 2024 | Teenage Engineerings
Pixeldarts
?
How Race, Age and Gender Shape Attitudes Towards Mental Health
How Race, Age and Gender Shape Attitudes Towards Mental Health
ThinkNow
?
AI Trends in Creative Operations 2024 by Artwork Flow.pdf
AI Trends in Creative Operations 2024 by Artwork Flow.pdf
marketingartwork
?
Skeleton Culture Code
Skeleton Culture Code
Skeleton Technologies
?
PEPSICO Presentation to CAGNY Conference Feb 2024
PEPSICO Presentation to CAGNY Conference Feb 2024
Neil Kimberley
?
Content Methodology: A Best Practices Report (Webinar)
Content Methodology: A Best Practices Report (Webinar)
contently
?
How to Prepare For a Successful Job Search for 2024
How to Prepare For a Successful Job Search for 2024
Albert Qian
?
Social Media Marketing Trends 2024 // The Global Indie Insights
Social Media Marketing Trends 2024 // The Global Indie Insights
Kurio // The Social Media Age(ncy)
?
Trends In Paid Search: Navigating The Digital Landscape In 2024
Trends In Paid Search: Navigating The Digital Landscape In 2024
Search Engine Journal
?
5 Public speaking tips from TED - Visualized summary
5 Public speaking tips from TED - Visualized summary
SpeakerHub
?
ChatGPT and the Future of Work - Clark Boyd
ChatGPT and the Future of Work - Clark Boyd
Clark Boyd
?
Getting into the tech field. what next
Getting into the tech field. what next
Tessa Mero
?
Google's Just Not That Into You: Understanding Core Updates & Search Intent
Google's Just Not That Into You: Understanding Core Updates & Search Intent
Lily Ray
?
How to have difficult conversations
How to have difficult conversations
Rajiv Jayarajah, MAppComm, ACC
?
2024 Trend Updates: What Really Works In SEO & Content Marketing
2024 Trend Updates: What Really Works In SEO & Content Marketing
Search Engine Journal
?
Storytelling For The Web: Integrate Storytelling in your Design Process
Storytelling For The Web: Integrate Storytelling in your Design Process
Chiara Aliotta
?
How to Leverage AI to Boost Employee Wellness - Lydia Di Francesco - SocialHR...
How to Leverage AI to Boost Employee Wellness - Lydia Di Francesco - SocialHR...
SocialHRCamp
?
2024 State of Marketing Report – by Hubspot
2024 State of Marketing Report – by Hubspot
Marius Sescu
?
Everything You Need To Know About ChatGPT
Everything You Need To Know About ChatGPT
Expeed Software
?
Product Design Trends in 2024 | Teenage Engineerings
Product Design Trends in 2024 | Teenage Engineerings
Pixeldarts
?
How Race, Age and Gender Shape Attitudes Towards Mental Health
How Race, Age and Gender Shape Attitudes Towards Mental Health
ThinkNow
?
AI Trends in Creative Operations 2024 by Artwork Flow.pdf
AI Trends in Creative Operations 2024 by Artwork Flow.pdf
marketingartwork
?
PEPSICO Presentation to CAGNY Conference Feb 2024
PEPSICO Presentation to CAGNY Conference Feb 2024
Neil Kimberley
?
Content Methodology: A Best Practices Report (Webinar)
Content Methodology: A Best Practices Report (Webinar)
contently
?
How to Prepare For a Successful Job Search for 2024
How to Prepare For a Successful Job Search for 2024
Albert Qian
?
Trends In Paid Search: Navigating The Digital Landscape In 2024
Trends In Paid Search: Navigating The Digital Landscape In 2024
Search Engine Journal
?
5 Public speaking tips from TED - Visualized summary
5 Public speaking tips from TED - Visualized summary
SpeakerHub
?
ChatGPT and the Future of Work - Clark Boyd
ChatGPT and the Future of Work - Clark Boyd
Clark Boyd
?
Getting into the tech field. what next
Getting into the tech field. what next
Tessa Mero
?
Google's Just Not That Into You: Understanding Core Updates & Search Intent
Google's Just Not That Into You: Understanding Core Updates & Search Intent
Lily Ray
?

Choosing balls

  • 1. Codeforces #162 Div1-C,Div2-E Choosing Balls Writer: hogloid improvement: snuke cooperation: rng_58,degwer
  • 2. ? N個のボールが一列に並んでいます ? それぞれのボールには,色?価値が定めら れています ? あるボールの列の価値は以下のように定 められます ? あるボールが列の先頭,もしくは一つ前の ボールと色が違うなら,(ボールの価値)*b ? そうでないなら,(ボールの価値)*a ? 列の価値はボールはこれらの数の和
  • 3. ? N個のボールの中から,相対的な順序を変えず に一部のボールを取り出します(部分列を取 ります) ? (a,b)のペアがQ個与えられるので,それぞれ の(a,b)について,選べるボールの部分列の 価値の最大値を答えなさい ただし,空の列の 価値は0とします。 ? 1<=N<=100000 1<=Q<=500 ? -100000<=a,b,ボールの価値<=100000 ? 1<=ボールの色<=N
  • 4. ? クエリーと聞いて前処理が頭をよぎるか も知れませんが,O(NQ)なら間に合いそう ? O(QNlogN)はO(10^9)ぐらいになるのでか なり危険???(実際通りません) ? それぞれのクエリーについて独立に考え てみます ? 妥当にDPを考えてみましょう ? dp[i]:=列の最後の色がiとなるような部 分列の最大価値
  • 5. ? i番目のボールの色をColor[i],価値を Value[i]とおくと, ? dp[Color[i]] を, ①dp[Color[i]]+a*Value[i] か ②dp[j]+b*Value[i] (1<=j<=N,j!=Color[i]) に更新することができます ? ボールを順に見てこの更新を繰り返す ? ナイーブな実装で、O(N^2)
  • 6. ? ①のパターンはO(1)で楽勝 ? ②は、よくあるパターンとしてColor[i] の左、右で分けると、それぞれの区間の 最大値を求め、最大値に+Value[i]*bす ればOK ? Range Minimum Query&更新! ? Segment Tree!!!
  • 7. ? しかし、更新/RangeMinimum Queryを どちらもO(1)で解くのはセグメント木で は無理そう??? ? logが一つかかると、TimeLimitにも間に 合いそうにない ? 別のO(1)で更新する方法を考えよう
  • 8. ? dp配列の上位二つの(最後の色、価値)を 持っていれば、あらゆる色でも、違う色 の最大値がどちらかにはある ? dp配列の値の更新は常に増加するので、 消去などの面倒なことが起こらず、更新 はどれもO(1)で可能 ? 少し場合分けが必要です ここでのWAがか なり多かった
  • 9. ? First Acceptance: KADR 25m24s ? Japanese First Acceptance: Komaki 27m50s ? Accepted User/All Rated User/All Submission:236/566/916 ? 普段のCよりかなり解かれました ? 赤族やそれに準ずる人はCを解けないと厳 しかったかもしれません ? バグで詰まってる人が多くて悲しかった
  • 10. ? First Acceptance: Moor 70m52s ? Japanese First Acceptance: ikouki 108m6s ? Accepted User/All Rated User: 12/1526 ? Div2-Eとしては理想的な解かれ具合だと 思います ? これが解ける人は早くdiv1に来ましょう!
  • 11. ? いつかまた問題を作ったときはよろしく お願いします ? Codeforcesの トップページを飾った 名誉なLissくん→