狠狠撸

狠狠撸Share a Scribd company logo

AtCoder Regular Contest 034 解説

?
?
A
AtCoder Inc.

AtCoder Regular Contest 034 解説

1 of 27
Downloaded 25 times
AtCoder Regular Contest 034 解説 AtCoder株式会社 代表取締役 高橋 直大 2015/2/21 1
競技プログラミングを始める前に ? 競技プログラミングをやったことがない人へ – まずはこっちのスライドを見よう！ – http://www.slideshare.net/chokudai/abc004 2015/2/21 2
?AtCoder Inc. All rights reserved. 3 A問題 首席 1. 問題概要 2. アルゴリズム 2015/2/21 3
A問題 問題概要 ? 受験生の人数Nと、それぞれの受験生の、「国語」 「数学」「理科」「英語」「塗り絵」の5科目の点数が与 えられる。 ? 受験生の最終得点は、以下の式で表せられる – 国語＋数学＋理科＋英語＋（塗り絵*110/900） ? 最終得点が最も高い受験生の、最終得点を求めよ ? 制約 – 2 ≦ N ≦ 3049 2015/2/21 4
A問題 アルゴリズム ? 解法 – 順番に点数を計算する ? この時に、（塗り絵）*900/110などを整数演算ではなく、小数とし て計算出来るように工夫することに注意！ – *900.0にするなど – 計算した中で、最も点数の高い点数を出力する ? やり方はいろいろ – 配列に入れてソート – 最も高い点数を入れる変数を用意しておき、毎回max関数などで最 大値を格納する。 2015/2/21 5
?AtCoder Inc. All rights reserved. 6 B問題 方程式 1. 問題概要 2. アルゴリズム 2015/2/21 6
B問題 問題概要 ? Nの十進表記における各桁の数の和をf(n)で表す ? f(x) + x = Nとなるxを全て出力しなさい ? 制約 – 1 ≦ N ≦1018 2015/2/21 7
B問題 アルゴリズム ? 考察 – f(x) + xについて考える – 全てのxについて、Nについて調べることが可能か？ ? 可能であれば、全部試せば良いので簡単！ 2015/2/21 8
B問題 アルゴリズム ? 部分点解法 (N≦1000) – xもf(x)も共に1以上の整数 ? つまり、x+f(x)=Nになるには、xはN以下の正整数であることが解 る – よって、1以上N以下の整数を全て試すことで、部分点を 取ることが出来る 2015/2/21 9
B問題 アルゴリズム 部分点解法(N≦1000) ? 考察 – xもf(x)も共に1以上の整数 ? つまり、x+f(x)=Nになるには、xはN以下の正整数であることが解 る – よって、1以上N以下の整数を全て試すことで、部分点を 取ることが出来る 2015/2/21 10
B問題 アルゴリズム 満点解法 ? 考察 – f(x)の最大値はどれくらいか？ ? x=99999999999999999の時、f(x) = 9 * 17 = 153 ? これよりは大きくならなそう – つまり、調べるべき範囲は、N-153からNの間で十分 ? これは全探索可能！ 2015/2/21 11
B問題 アルゴリズム 満点解法 ? 注意点 – 数が大きいので、32bit整数型には収まらない ? 64bit整数型などの、大きな数が格納可能な整数型を使おう！ 2015/2/21 12
?AtCoder Inc. All rights reserved. 13 C問題 約数かつ倍数 1. 問題概要 2. アルゴリズム 2015/2/21 13
C問題 問題概要 ? A,Bが与えられる ? A!の約数であり、B!の倍数である数の個数を出力せ よ ? 制約 – 1 ≦ B ＜ A ≦ 1018 – A - 100 ≦ B 2015/2/21 14
C問題 アルゴリズム 部分点1 ? A,B≦15のとき – 15! = 1307674368000 ? 全通り試すことは出来ない！ ? 何か工夫しなければいけない – Aの約数を全て列挙して、そのうちでBの倍数になってい るかどうかを1つ1つチェックすれば間に合う？ ? 約数を、O(√A!)くらいで列挙出来れば可能！ 2015/2/21 15
C問題 アルゴリズム 部分点1 ? 簡単な約数の列挙方法 – 例えば、A=5の時、A! = 120（これを暫定的にFAとする) – これの約数を列挙することを考える ? 1から√FA (11くらい)までのうち、FAの約数であるものをループで探 す – If(FA % I == 0)みたいな感じ ? 見つかった約数をiとすると、FA/iもFAの約数である – 1が約数なので、120も約数 – 2が約数なので、60も約数 – 3が約数なので、40も約数 – ???? ? これを、√FAまで繰り返すことによって、全ての約数を列挙でき る！ ? 各約数に対して、B!の倍数になっているかどうかチェックすれば 良い 2015/2/21 16
C問題 アルゴリズム 部分点2 ? 考察 – もっと高速化するには、根本的な部分を見直す必要があ る。 – A!の倍数かつ、B!の約数とは何か？ ? (A! / B!)の約数に、B!を掛けたものである！ ? 例えば、A=5, B=3であれば、5*4の約数に、3*2*1を掛けたもので ある！ – 20の約数は1,2,4,5,10,20なので、解は6,12,24,30,60,120である ? まずはこれを利用する 2015/2/21 17
C問題 アルゴリズム 部分点2 ? さらに考察 – A,Bが大きい時、全ての約数を列挙するのは難しい ? 約数の個数をもっと上手に数えよう！ – 約数を効率的に数えるには、素因数分解をすると良い！ – 例えば、20の約数の個数を数えたい時、 ? 20 = 2 × 2 × 5と表せる。 ? この約数は、(2の0,1,2乗のいずれか) × (5の0,1乗のいずれか) であることが解る – 例えば、2の1乗×5の1乗を選ぶと、約数の1つである10が出来る ? つまり、この組み合わせの個数を数えてあげれば良い！ – これは、各素因数に対して、その指数が分かれば良い 2015/2/21 18
C問題 アルゴリズム 部分点2 ? A,B≦10^6, A-B≦100の時 – A! / B!について、約数の個数を調べたい – 計算式を考えて、10^6以上の素因数は、この数には含ま れない ? よって、各素因数について、いくつ存在したかを配列で管理して あげれば良い – A!/B!を素因数分解するのは難しいが、B+1からAまでの整 数1つ1つに対して、素因数分解してあげるのは可能 ? であれば、この1つ1つに対して素因数分解を行い、指数の計算を してあげれば良い。1つ1つの計算量は、部分点1の約数全列挙と 同じようなアルゴリズムを用いると、O(√A) – 指数が求まったら、あとは先ほどの公式を用いて、約数 の個数を計算すれば解ける 2015/2/21 19
C問題 アルゴリズム 満点解法 ? A,B≦10^9, A-B≦100の時 – 先ほどのように、素因数の最大値が小さくはならない ? だが、種類数自体はそこまで多くない！ ? よって、配列で管理していた部分を、連想配列に直してあげれば 良い！ – 計算量は、素因数分解がO(√A)、その回数が100回で、1 回の素因数分解で発生する素因数は、O(logA)個程度な ので、十分に間に合う 2015/2/21 20
2015-2-21 AtCoder Regular Contest 034 問題D 解説 (暫定版) AtCoder株式会社 代表取締役 高橋 直大 1
2015-2-21 ?AtCoder Inc. All rights reserved. * D問題 1. 問題概要 2. 解法 2
2015-2-21 D問題 問題概要 ?赤 数字 整数 書 A枚 ?青 数字 整数 書 B枚 ?何 書 C枚 ?以上 山札 上 引 行 ?赤 数字a 引 +a点 ?青 数字b 引 得点 b倍 ?何 引 ?最終得点 期待値 ? ?制約 – 1 A,B,C 50 – 1 各数字 100 3
D問題 部分点解法1 (5点) 出題者 都合 超 駆 足 申 訳 by evima ?1 A,B,C 3 ?合計9枚以下 ?山札 全 試 ?時間計算量 O((A+B+C)! * poly(A+B))
D問題 部分点解法2 (20点) ?1 A,B,C 8 ?赤 青 合計16枚以下 ?dp[今 引 集合] ?時間計算量 O(2^(A+B) * poly(A+B))
D問題 部分点解法3 (40点) ?1 A, C 50, 1 B 8 ? 考 赤 書 数字 平均 R 全 赤 R 書 答 同 → 区別不要 ?dp[引 赤 枚数][引 青 集 合] ?時間計算量 O(2^B * poly(A+B))
D問題 満点解法 ?1 A, B, C 50 ? 考 青 区別不要 ?青 i枚引 積 期待値 B[i] 値 計算 使 ?dp[引 赤 枚数][引 青 枚 数] ?時間計算量 O(poly(A+B))

More Related Content

AtCoder Regular Contest 034 解説

  • 1. AtCoder Regular Contest 034 解説 AtCoder株式会社 代表取締役 高橋 直大 2015/2/21 1
  • 3. ?AtCoder Inc. All rights reserved. 3 A問題 首席 1. 問題概要 2. アルゴリズム 2015/2/21 3
  • 4. A問題 問題概要 ? 受験生の人数Nと、それぞれの受験生の、「国語」 「数学」「理科」「英語」「塗り絵」の5科目の点数が与 えられる。 ? 受験生の最終得点は、以下の式で表せられる – 国語＋数学＋理科＋英語＋（塗り絵*110/900） ? 最終得点が最も高い受験生の、最終得点を求めよ ? 制約 – 2 ≦ N ≦ 3049 2015/2/21 4
  • 5. A問題 アルゴリズム ? 解法 – 順番に点数を計算する ? この時に、（塗り絵）*900/110などを整数演算ではなく、小数とし て計算出来るように工夫することに注意！ – *900.0にするなど – 計算した中で、最も点数の高い点数を出力する ? やり方はいろいろ – 配列に入れてソート – 最も高い点数を入れる変数を用意しておき、毎回max関数などで最 大値を格納する。 2015/2/21 5
  • 6. ?AtCoder Inc. All rights reserved. 6 B問題 方程式 1. 問題概要 2. アルゴリズム 2015/2/21 6
  • 7. B問題 問題概要 ? Nの十進表記における各桁の数の和をf(n)で表す ? f(x) + x = Nとなるxを全て出力しなさい ? 制約 – 1 ≦ N ≦1018 2015/2/21 7
  • 8. B問題 アルゴリズム ? 考察 – f(x) + xについて考える – 全てのxについて、Nについて調べることが可能か？ ? 可能であれば、全部試せば良いので簡単！ 2015/2/21 8
  • 9. B問題 アルゴリズム ? 部分点解法 (N≦1000) – xもf(x)も共に1以上の整数 ? つまり、x+f(x)=Nになるには、xはN以下の正整数であることが解 る – よって、1以上N以下の整数を全て試すことで、部分点を 取ることが出来る 2015/2/21 9
  • 10. B問題 アルゴリズム 部分点解法(N≦1000) ? 考察 – xもf(x)も共に1以上の整数 ? つまり、x+f(x)=Nになるには、xはN以下の正整数であることが解 る – よって、1以上N以下の整数を全て試すことで、部分点を 取ることが出来る 2015/2/21 10
  • 11. B問題 アルゴリズム 満点解法 ? 考察 – f(x)の最大値はどれくらいか？ ? x=99999999999999999の時、f(x) = 9 * 17 = 153 ? これよりは大きくならなそう – つまり、調べるべき範囲は、N-153からNの間で十分 ? これは全探索可能！ 2015/2/21 11
  • 12. B問題 アルゴリズム 満点解法 ? 注意点 – 数が大きいので、32bit整数型には収まらない ? 64bit整数型などの、大きな数が格納可能な整数型を使おう！ 2015/2/21 12
  • 13. ?AtCoder Inc. All rights reserved. 13 C問題 約数かつ倍数 1. 問題概要 2. アルゴリズム 2015/2/21 13
  • 14. C問題 問題概要 ? A,Bが与えられる ? A!の約数であり、B!の倍数である数の個数を出力せ よ ? 制約 – 1 ≦ B ＜ A ≦ 1018 – A - 100 ≦ B 2015/2/21 14
  • 15. C問題 アルゴリズム 部分点1 ? A,B≦15のとき – 15! = 1307674368000 ? 全通り試すことは出来ない！ ? 何か工夫しなければいけない – Aの約数を全て列挙して、そのうちでBの倍数になってい るかどうかを1つ1つチェックすれば間に合う？ ? 約数を、O(√A!)くらいで列挙出来れば可能！ 2015/2/21 15
  • 16. C問題 アルゴリズム 部分点1 ? 簡単な約数の列挙方法 – 例えば、A=5の時、A! = 120（これを暫定的にFAとする) – これの約数を列挙することを考える ? 1から√FA (11くらい)までのうち、FAの約数であるものをループで探 す – If(FA % I == 0)みたいな感じ ? 見つかった約数をiとすると、FA/iもFAの約数である – 1が約数なので、120も約数 – 2が約数なので、60も約数 – 3が約数なので、40も約数 – ???? ? これを、√FAまで繰り返すことによって、全ての約数を列挙でき る！ ? 各約数に対して、B!の倍数になっているかどうかチェックすれば 良い 2015/2/21 16
  • 17. C問題 アルゴリズム 部分点2 ? 考察 – もっと高速化するには、根本的な部分を見直す必要があ る。 – A!の倍数かつ、B!の約数とは何か？ ? (A! / B!)の約数に、B!を掛けたものである！ ? 例えば、A=5, B=3であれば、5*4の約数に、3*2*1を掛けたもので ある！ – 20の約数は1,2,4,5,10,20なので、解は6,12,24,30,60,120である ? まずはこれを利用する 2015/2/21 17
  • 18. C問題 アルゴリズム 部分点2 ? さらに考察 – A,Bが大きい時、全ての約数を列挙するのは難しい ? 約数の個数をもっと上手に数えよう！ – 約数を効率的に数えるには、素因数分解をすると良い！ – 例えば、20の約数の個数を数えたい時、 ? 20 = 2 × 2 × 5と表せる。 ? この約数は、(2の0,1,2乗のいずれか) × (5の0,1乗のいずれか) であることが解る – 例えば、2の1乗×5の1乗を選ぶと、約数の1つである10が出来る ? つまり、この組み合わせの個数を数えてあげれば良い！ – これは、各素因数に対して、その指数が分かれば良い 2015/2/21 18
  • 19. C問題 アルゴリズム 部分点2 ? A,B≦10^6, A-B≦100の時 – A! / B!について、約数の個数を調べたい – 計算式を考えて、10^6以上の素因数は、この数には含ま れない ? よって、各素因数について、いくつ存在したかを配列で管理して あげれば良い – A!/B!を素因数分解するのは難しいが、B+1からAまでの整 数1つ1つに対して、素因数分解してあげるのは可能 ? であれば、この1つ1つに対して素因数分解を行い、指数の計算を してあげれば良い。1つ1つの計算量は、部分点1の約数全列挙と 同じようなアルゴリズムを用いると、O(√A) – 指数が求まったら、あとは先ほどの公式を用いて、約数 の個数を計算すれば解ける 2015/2/21 19
  • 20. C問題 アルゴリズム 満点解法 ? A,B≦10^9, A-B≦100の時 – 先ほどのように、素因数の最大値が小さくはならない ? だが、種類数自体はそこまで多くない！ ? よって、配列で管理していた部分を、連想配列に直してあげれば 良い！ – 計算量は、素因数分解がO(√A)、その回数が100回で、1 回の素因数分解で発生する素因数は、O(logA)個程度な ので、十分に間に合う 2015/2/21 20
  • 21. 2015-2-21 AtCoder Regular Contest 034 問題D 解説 (暫定版) AtCoder株式会社 代表取締役 高橋 直大 1
  • 22. 2015-2-21 ?AtCoder Inc. All rights reserved. * D問題 1. 問題概要 2. 解法 2
  • 23. 2015-2-21 D問題 問題概要 ?赤 数字 整数 書 A枚 ?青 数字 整数 書 B枚 ?何 書 C枚 ?以上 山札 上 引 行 ?赤 数字a 引 +a点 ?青 数字b 引 得点 b倍 ?何 引 ?最終得点 期待値 ? ?制約 – 1 A,B,C 50 – 1 各数字 100 3
  • 24. D問題 部分点解法1 (5点) 出題者 都合 超 駆 足 申 訳 by evima ?1 A,B,C 3 ?合計9枚以下 ?山札 全 試 ?時間計算量 O((A+B+C)! * poly(A+B))
  • 25. D問題 部分点解法2 (20点) ?1 A,B,C 8 ?赤 青 合計16枚以下 ?dp[今 引 集合] ?時間計算量 O(2^(A+B) * poly(A+B))
  • 26. D問題 部分点解法3 (40点) ?1 A, C 50, 1 B 8 ? 考 赤 書 数字 平均 R 全 赤 R 書 答 同 → 区別不要 ?dp[引 赤 枚数][引 青 集 合] ?時間計算量 O(2^B * poly(A+B))
  • 27. D問題 満点解法 ?1 A, B, C 50 ? 考 青 区別不要 ?青 i枚引 積 期待値 B[i] 値 計算 使 ?dp[引 赤 枚数][引 青 枚 数] ?時間計算量 O(poly(A+B))