狠狠撸

狠狠撸Share a Scribd company logo
One
  原案 : fura2
解答 : komiya, fura2
  解説 : fura2
問題概要
●   長方形の窓から、放物線の形をした山がたくさん
    見えている
●   山と空との境界線の長さを求めよ
解法
1. 山と窓、山と山の交点の x 座標をすべて列挙する
    二次方程式を解くだけ

2. 交点の x 座標をソートする。これを x1, x2, …, xm
  とする

3. 各 i について、区間 (xi, xi+1) において ”一番上”
  にある山を求め、その曲線長を答えに加える
    ただし、”一番上”にある山が窓枠より下にあるなら何も
     しない
解法
●   放物線の曲線長をどうやって求めるか

●   公式があります。y = f(x) の a≦x≦b における曲
    線長は、
解法
●   公式の導出
    [a, b] を N 分割して、曲線を折れ線で近似すると、
    折れ線の長さは次のように書ける。( ピタゴラスの
    定理!)




    おおざっぱに N → ∞ とすると、さっきの公式になる
解法
●   積分の計算は好きな方法でやってください
    –   数値積分 ( 台形法、シンプソン法など )
    –   厳密計算 ( 放物線の場合、幸運にも不定積分が簡単
        な形で書ける )
補足
●   曲線長の計算方法を知らないと、ちょっと苦しかっ
    たかも知れません

●   が、とてもシンプルなので知らなくても自力で導出
    できる!...かもしれません
提出状況
●   AC Rate
    –   16.67 % (4/24)


●   First Acceptance
    –   Onsite: password (154 min)
    –   All: password (154 min)
Ad

Recommended

abc027
abc027
AtCoder Inc.
?
グラフカットによる画像背景切り取り
グラフカットによる画像背景切り取り
coil_kpc
?
AtCoder Beginner Contest 018 解説
AtCoder Beginner Contest 018 解説
AtCoder Inc.
?
情报オリンピック夏合宿発表
情报オリンピック夏合宿発表
Kazuma Mikami
?
极限の问题
极限の问题
nabeshimamasataka
?
Sengoku
Sengoku
Hirotaka Isa
?
竞技プログラミングでの线型方程式系
竞技プログラミングでの线型方程式系
tmaehara
?
最小カットを使って「燃やす埋める问题」を解く
最小カットを使って「燃やす埋める问题」を解く
shindannin
?
楕円曲线セキュリティー
楕円曲线セキュリティー
Jonathan Underwood
?
CODE FESTIVAL 2014 エキシビジョン 解説
CODE FESTIVAL 2014 エキシビジョン 解説
AtCoder Inc.
?
第7回マンホールナイト 第0部 円の14等分线を定规とコンパスで描こう!
第7回マンホールナイト 第0部 円の14等分线を定规とコンパスで描こう!
K Kimura
?
【材料力学】3次元空間のひずみ (II-11 2018)
【材料力学】3次元空間のひずみ (II-11 2018)
Kazuhiro Suga
?
Kobayashi 20140409
Kobayashi 20140409
y-kobayashi
?
公開鍵暗号3: ナップザック暗号
公開鍵暗号3: ナップザック暗号
Joe Suzuki
?
[Basic 14] 暗号について / RSA 暗号 / 楕円曲線暗号
[Basic 14] 暗号について / RSA 暗号 / 楕円曲線暗号
Yuto Takei
?
AtCoder Regular Contest 021 解説
AtCoder Regular Contest 021 解説
AtCoder Inc.
?
WUPC2nd E問題
WUPC2nd E問題
Dai Hamada
?
AtCoder Beginner Contest 023 解説
AtCoder Beginner Contest 023 解説
AtCoder Inc.
?
AtCoder Regular Contest 036 解説
AtCoder Regular Contest 036 解説
AtCoder Inc.
?
搁蝉补暗号で彼女が出来るらしい
搁蝉补暗号で彼女が出来るらしい
Yosuke Onoue
?
第1回竞技プログラミング勉强会
第1回竞技プログラミング勉强会
Yoshiki TAKADA
?
Segpair
Segpair
oupc
?
Permutation
Permutation
oupc
?

More Related Content

What's hot (20)

Sengoku
Sengoku
Hirotaka Isa
?
竞技プログラミングでの线型方程式系
竞技プログラミングでの线型方程式系
tmaehara
?
最小カットを使って「燃やす埋める问题」を解く
最小カットを使って「燃やす埋める问题」を解く
shindannin
?
楕円曲线セキュリティー
楕円曲线セキュリティー
Jonathan Underwood
?
CODE FESTIVAL 2014 エキシビジョン 解説
CODE FESTIVAL 2014 エキシビジョン 解説
AtCoder Inc.
?
第7回マンホールナイト 第0部 円の14等分线を定规とコンパスで描こう!
第7回マンホールナイト 第0部 円の14等分线を定规とコンパスで描こう!
K Kimura
?
【材料力学】3次元空間のひずみ (II-11 2018)
【材料力学】3次元空間のひずみ (II-11 2018)
Kazuhiro Suga
?
Kobayashi 20140409
Kobayashi 20140409
y-kobayashi
?
公開鍵暗号3: ナップザック暗号
公開鍵暗号3: ナップザック暗号
Joe Suzuki
?
[Basic 14] 暗号について / RSA 暗号 / 楕円曲線暗号
[Basic 14] 暗号について / RSA 暗号 / 楕円曲線暗号
Yuto Takei
?
AtCoder Regular Contest 021 解説
AtCoder Regular Contest 021 解説
AtCoder Inc.
?
WUPC2nd E問題
WUPC2nd E問題
Dai Hamada
?
AtCoder Beginner Contest 023 解説
AtCoder Beginner Contest 023 解説
AtCoder Inc.
?
AtCoder Regular Contest 036 解説
AtCoder Regular Contest 036 解説
AtCoder Inc.
?
搁蝉补暗号で彼女が出来るらしい
搁蝉补暗号で彼女が出来るらしい
Yosuke Onoue
?
第1回竞技プログラミング勉强会
第1回竞技プログラミング勉强会
Yoshiki TAKADA
?
竞技プログラミングでの线型方程式系
竞技プログラミングでの线型方程式系
tmaehara
?
最小カットを使って「燃やす埋める问题」を解く
最小カットを使って「燃やす埋める问题」を解く
shindannin
?
楕円曲线セキュリティー
楕円曲线セキュリティー
Jonathan Underwood
?
CODE FESTIVAL 2014 エキシビジョン 解説
CODE FESTIVAL 2014 エキシビジョン 解説
AtCoder Inc.
?
第7回マンホールナイト 第0部 円の14等分线を定规とコンパスで描こう!
第7回マンホールナイト 第0部 円の14等分线を定规とコンパスで描こう!
K Kimura
?
【材料力学】3次元空間のひずみ (II-11 2018)
【材料力学】3次元空間のひずみ (II-11 2018)
Kazuhiro Suga
?
公開鍵暗号3: ナップザック暗号
公開鍵暗号3: ナップザック暗号
Joe Suzuki
?
[Basic 14] 暗号について / RSA 暗号 / 楕円曲線暗号
[Basic 14] 暗号について / RSA 暗号 / 楕円曲線暗号
Yuto Takei
?
AtCoder Regular Contest 021 解説
AtCoder Regular Contest 021 解説
AtCoder Inc.
?
AtCoder Beginner Contest 023 解説
AtCoder Beginner Contest 023 解説
AtCoder Inc.
?
AtCoder Regular Contest 036 解説
AtCoder Regular Contest 036 解説
AtCoder Inc.
?
搁蝉补暗号で彼女が出来るらしい
搁蝉补暗号で彼女が出来るらしい
Yosuke Onoue
?
第1回竞技プログラミング勉强会
第1回竞技プログラミング勉强会
Yoshiki TAKADA
?

Viewers also liked (17)

Segpair
Segpair
oupc
?
Permutation
Permutation
oupc
?
Sharp2sat
Sharp2sat
oupc
?
Comment
Comment
oupc
?
Magical
Magical
oupc
?
Paren
Paren
oupc
?
Palin
Palin
oupc
?
Replace
Replace
oupc
?
Sanpo
Sanpo
oupc
?
指数时间アルゴリズム入门
指数时间アルゴリズム入门
Yoichi Iwata
?
Segpair
Segpair
oupc
?
Permutation
Permutation
oupc
?
Sharp2sat
Sharp2sat
oupc
?
Comment
Comment
oupc
?
Magical
Magical
oupc
?
Paren
Paren
oupc
?
Palin
Palin
oupc
?
Replace
Replace
oupc
?
Sanpo
Sanpo
oupc
?
指数时间アルゴリズム入门
指数时间アルゴリズム入门
Yoichi Iwata
?
Ad

Similar to One (20)

楕円形の连结を使った最小値问题
楕円形の连结を使った最小値问题
政孝 鍋島
?
楕円形の连结を使った最小値问题
楕円形の连结を使った最小値问题
nabeshimamasataka
?
【鲍苍颈迟测道场】ゲーム制作に使う数学を学习しよう
【鲍苍颈迟测道场】ゲーム制作に使う数学を学习しよう
Unity Technologies Japan K.K.
?
指数时间アルゴリズムの最先端
指数时间アルゴリズムの最先端
Yoichi Iwata
?
基础强化数学 第7回
基础强化数学 第7回
studyplace0
?
AtCoder Regular Contest 027 解説
AtCoder Regular Contest 027 解説
AtCoder Inc.
?
数学教材(中间発表)
数学教材(中间発表)
Mizuguchi1205
?
『上级演习』确率
『上级演习』确率
JUKEN7
?
Indeedなう B日程 解説
Indeedなう B日程 解説
AtCoder Inc.
?
最小全域木
最小全域木
Huziwara
?
ディジタル信号処理 课题解説 その4
ディジタル信号処理 课题解説 その4
noname409
?
2018年度秋学期 応用数学(解析) 第1部?「無限」の理解 第2回 無限にも大小がある (2018. 10. 2)
2018年度秋学期 応用数学(解析) 第1部?「無限」の理解 第2回 無限にも大小がある (2018. 10. 2)
Akira Asano
?
2016年度秋学期 応用数学(解析) 第13回 孤立特異点と留数 (2016. 12. 22)
2016年度秋学期 応用数学(解析) 第13回 孤立特異点と留数 (2016. 12. 22)
Akira Asano
?
2016年度秋学期 応用数学(解析) 第2回 無限にも大小がある (2016. 10. 6)
2016年度秋学期 応用数学(解析) 第2回 無限にも大小がある (2016. 10. 6)
Akira Asano
?
2014年度秋学期 応用数学(解析) 第1部?「無限」の理解 / 第2回 無限にも大小がある (2014. 10. 2)
2014年度秋学期 応用数学(解析) 第1部?「無限」の理解 / 第2回 無限にも大小がある (2014. 10. 2)
Akira Asano
?
続?わかりやすいパターン认识第5章
続?わかりやすいパターン认识第5章
Roy Ray
?
2016年度秋学期 画像情報処理 第3回 フーリエ変換とサンプリング定理 (2016. 10. 13)
2016年度秋学期 画像情報処理 第3回 フーリエ変換とサンプリング定理 (2016. 10. 13)
Akira Asano
?
ある反転授业の试み:正规分布の罢补测濒辞谤展开をとおして
ある反転授业の试み:正规分布の罢补测濒辞谤展开をとおして
Hideo Hirose
?
円锥曲线の极座标表示
円锥曲线の极座标表示
Maruyama Tetsutaro
?
楕円形の连结を使った最小値问题
楕円形の连结を使った最小値问题
政孝 鍋島
?
楕円形の连结を使った最小値问题
楕円形の连结を使った最小値问题
nabeshimamasataka
?
【鲍苍颈迟测道场】ゲーム制作に使う数学を学习しよう
【鲍苍颈迟测道场】ゲーム制作に使う数学を学习しよう
Unity Technologies Japan K.K.
?
指数时间アルゴリズムの最先端
指数时间アルゴリズムの最先端
Yoichi Iwata
?
基础强化数学 第7回
基础强化数学 第7回
studyplace0
?
AtCoder Regular Contest 027 解説
AtCoder Regular Contest 027 解説
AtCoder Inc.
?
数学教材(中间発表)
数学教材(中间発表)
Mizuguchi1205
?
『上级演习』确率
『上级演习』确率
JUKEN7
?
Indeedなう B日程 解説
Indeedなう B日程 解説
AtCoder Inc.
?
最小全域木
最小全域木
Huziwara
?
ディジタル信号処理 课题解説 その4
ディジタル信号処理 课题解説 その4
noname409
?
2018年度秋学期 応用数学(解析) 第1部?「無限」の理解 第2回 無限にも大小がある (2018. 10. 2)
2018年度秋学期 応用数学(解析) 第1部?「無限」の理解 第2回 無限にも大小がある (2018. 10. 2)
Akira Asano
?
2016年度秋学期 応用数学(解析) 第13回 孤立特異点と留数 (2016. 12. 22)
2016年度秋学期 応用数学(解析) 第13回 孤立特異点と留数 (2016. 12. 22)
Akira Asano
?
2016年度秋学期 応用数学(解析) 第2回 無限にも大小がある (2016. 10. 6)
2016年度秋学期 応用数学(解析) 第2回 無限にも大小がある (2016. 10. 6)
Akira Asano
?
2014年度秋学期 応用数学(解析) 第1部?「無限」の理解 / 第2回 無限にも大小がある (2014. 10. 2)
2014年度秋学期 応用数学(解析) 第1部?「無限」の理解 / 第2回 無限にも大小がある (2014. 10. 2)
Akira Asano
?
続?わかりやすいパターン认识第5章
続?わかりやすいパターン认识第5章
Roy Ray
?
2016年度秋学期 画像情報処理 第3回 フーリエ変換とサンプリング定理 (2016. 10. 13)
2016年度秋学期 画像情報処理 第3回 フーリエ変換とサンプリング定理 (2016. 10. 13)
Akira Asano
?
ある反転授业の试み:正规分布の罢补测濒辞谤展开をとおして
ある反転授业の试み:正规分布の罢补测濒辞谤展开をとおして
Hideo Hirose
?
Ad

More from oupc (8)

Knapsack
Knapsack
oupc
?
Four op
Four op
oupc
?
Divisor
Divisor
oupc
?
Division
Division
oupc
?
Anagram
Anagram
oupc
?
Comment
Comment
oupc
?
Knapsack
Knapsack
oupc
?
Four op
Four op
oupc
?
Divisor
Divisor
oupc
?
Division
Division
oupc
?
Anagram
Anagram
oupc
?
Comment
Comment
oupc
?

One

  • 1. One 原案 : fura2 解答 : komiya, fura2 解説 : fura2
  • 2. 問題概要 ● 長方形の窓から、放物線の形をした山がたくさん 見えている ● 山と空との境界線の長さを求めよ
  • 3. 解法 1. 山と窓、山と山の交点の x 座標をすべて列挙する  二次方程式を解くだけ 2. 交点の x 座標をソートする。これを x1, x2, …, xm とする 3. 各 i について、区間 (xi, xi+1) において ”一番上” にある山を求め、その曲線長を答えに加える  ただし、”一番上”にある山が窓枠より下にあるなら何も しない
  • 4. 解法 ● 放物線の曲線長をどうやって求めるか ● 公式があります。y = f(x) の a≦x≦b における曲 線長は、
  • 5. 解法 ● 公式の導出 [a, b] を N 分割して、曲線を折れ線で近似すると、 折れ線の長さは次のように書ける。( ピタゴラスの 定理!) おおざっぱに N → ∞ とすると、さっきの公式になる
  • 6. 解法 ● 積分の計算は好きな方法でやってください – 数値積分 ( 台形法、シンプソン法など ) – 厳密計算 ( 放物線の場合、幸運にも不定積分が簡単 な形で書ける )
  • 7. 補足 ● 曲線長の計算方法を知らないと、ちょっと苦しかっ たかも知れません ● が、とてもシンプルなので知らなくても自力で導出 できる!...かもしれません
  • 8. 提出状況 ● AC Rate – 16.67 % (4/24) ● First Acceptance – Onsite: password (154 min) – All: password (154 min)