狠狠撸

狠狠撸Share a Scribd company logo

AtCoder Beginner Contest 033 解説

?
?
A
AtCoder Inc.

AtCoder Beginner Contest 033 解説

1 of 23
Downloaded 21 times
?AtCoder Inc. All rights reserved. 1 AtCoder Beginner Contest #033 解説 AtCoder株式会社 代表取締役 高橋 直大
?AtCoder Inc. All rights reserved. 2 A問題 暗証番号
?AtCoder Inc. All rights reserved. 3 A問題 問題概要 ? 4桁の数が与えられる ? 各桁が全て同じ数字であるか判定せよ
?AtCoder Inc. All rights reserved. 4 A問題 アルゴリズム ? 実際に4文字読み込み、if文などで判定すれば よい ? 例: if(in[0]==in[1]&&in[1]==in[2]&&in[2]==in[3]) – 4桁とも同じ数字には法則性もある – 0000, 1111, 2222, …, 9999は全て 1111の倍数。 ? 1111で割り切れるかどうかを判定してもよい ? 例: if(N%1111==0)
?AtCoder Inc. All rights reserved. 5 B問題 町の合併
?AtCoder Inc. All rights reserved. 6 B問題 問題概要 ? N個の町が合併し、1つの市になる。 ? N個の町の合計人口の過半数以上の人口を持つ町 が存在すれば、新しい市の名前はその町の名前に する ? 存在しなければ、atcoderという名前にする。 ? どのような市の名前になるだろうか？ ? 2 ≦ N ≦ 1,000, 1 ≦ 町の人口 ≦ 100,000
?AtCoder Inc. All rights reserved. 7 B問題 アルゴリズム ? 問題文にあるとおりに実際にループを回してシミュ レートする ? 合計を計算する ? それぞれの町の人口がその合計の過半数以上ある かをifで判定し、あればそれを出力 ? なければatcoderと出力 ? 計算量は O(N)
?AtCoder Inc. All rights reserved. 8 B問題 アルゴリズム ? ちなみに、過半数以上の人口がある町が2つ以上存 在することはない ? (2番目に多い町の人口が過半数あるとすると、1番 目と2番目の合計が全人口を超えてしまい矛盾す る)
?AtCoder Inc. All rights reserved. 9 1. 問題概要 2. アルゴリズム C問題 数式の書き換え
?AtCoder Inc. All rights reserved. 10 C問題 問題概要 ? 1+2+3*4*5+6*7のような、各項が1桁で括弧がなく、 乗算と加算のみの数式が与えられる。 ? これらの数字をいくつか0に書き換えて答えを0にし たい。 ? 最低何個書き換えればよいか。 ? 数式の長さは100,000以下
?AtCoder Inc. All rights reserved. 11 C問題 アルゴリズム ? 各数字を0にする/しないを全て試すと O(2^N)かかる ため、間に合わない ? ある場所を0に書き換えると、どこまで影響が出るだ ろうか。
?AtCoder Inc. All rights reserved. 12 C問題 アルゴリズム ? 1*2*3の1を0にする→ 0*2*3=0 ? 2*4*6の4を0にする→ 2*0*6=0 ? 1+2+3の1を0にする→ 0+2+3 ? 3*6+9の6を0にする→ 3*0+9=0+9 ? 1+2*3+4の2を0にする→1+0*3+4=1+0+4
?AtCoder Inc. All rights reserved. 13 C問題 アルゴリズム ? *だけで繋がっている式のどこかに0があると、その 範囲の答えが0になる ? 0と書かれた項は+を越えた場所には影響しない ? 元の数式の答えを0にするには、+で区切られたそ れぞれの部分の答えを全て0にしなければならない ? 要は、+で区切られた部分それぞれに最低1つの0の 項が欲しい
?AtCoder Inc. All rights reserved. 14 C問題 アルゴリズム ? +で区切る ? 区切ったそれぞれの部分に対して、初期状態で0が 1つもなければ、1回書き換えが必要 ? この合計が必要な最小個数になる ? O(N)
?AtCoder Inc. All rights reserved. 15 D問題 三角形の分類 1. 問題概要 2. アルゴリズム
?AtCoder Inc. All rights reserved. 16 D問題 問題概要 ? 座標平面上の点 (x[i],y[i]) がN個与えられる。 ? N個のうち3つ選んで三角形を作ったとき、それが鋭 角三角形、直角三角形、鈍角三角形になるものを、 それぞれ数える。 ? N ≦ 2,000 ? 部分点: N ≦ 100
?AtCoder Inc. All rights reserved. 17 D問題 アルゴリズム ? 部分点解法 ? 3点を全部選んで角度を計算する ? 角度が 0°より大きく90°より小さいか、90°に等し いか、90°より大きく180°より小さいかの3種類を 分類できればよいので、内積を使ってもよい ? ベクトル(a,b)と(c,d)のなす角θが – 0° < θ < 90°のとき ac+bd > 0 – θ = 90°のとき ac+bd = 0 – 90° < θ < 180° のとき ac+bd < 0
?AtCoder Inc. All rights reserved. 18 D問題 アルゴリズム ? さっきの方法だと計算量は O(N^3) ? 部分点は間に合うが、 満点はとれない ? これ以上早く計算するには、複数の三角形をまとめ て数える必要がある
?AtCoder Inc. All rights reserved. 19 D問題 アルゴリズム ? 三角形の特徴に注目する ? 直角三角形は、1個が直角、他は鋭角 ? 鈍角三角形は、1個が鈍角、他は鋭角 ? 直角、鈍角となる∠ABCの組の個数を求めれば、直 角三角形、鈍角三角形の個数が分かり、全体から 引くと鋭角三角形の個数も計算できる。
?AtCoder Inc. All rights reserved. 20 D問題 アルゴリズム ? ∠ABCのBの部分を固定して、A,Cの組を数えること にする ? ある点から他の全ての点に対して半直線を引くとこ うなる (プログラムでは、角度だけをもてばよい。角 度はatan2等で計算できる。)
?AtCoder Inc. All rights reserved. 21 D問題 アルゴリズム ? これらの角度をソートし、左側を固定する – どこまでが90°未満だろう？ – どこまでが90°だろう？ – どこまでが180°未満だろう？ ? これらは二分探索やしゃくとり法でまとめて高速に 計算できる。二分探索ではO(N log N)、尺取だと O(N) ? ただし環状になっているので、角度の扱いは少し複 雑で気をつける必要がある。(2周分配列をもったり、 内積?外積で求めると楽かもしれない)
?AtCoder Inc. All rights reserved. 22 D問題 アルゴリズム ? 全体をまとめると – 一点選ぶ – そこから他の全て点へのベクトルの角度を求め、ソートす る。 – 二分探索やしゃくとり法で鈍角、直角の個数を数える – 鋭角三角形の個数を、全体から鈍角、直角の個数を引く ことで求める ? 計算量は合計で O(N^2 logn) (しゃくとり法の場合)
?AtCoder Inc. All rights reserved. 23 D問題 アルゴリズム ? 注意 ? 2つのベクトルのなす角度が非常に小さかったり、非 常に90°に近かったり、非常に180°に近かったり することがある。 例1: (-10000,-10000), (-10000,-9999),(10000,10000) 例2: (-10000,-10000), (-9999,10000),(10000,9999) 例3: (-10000,-10000), (1,0),(10000,10000) ? 浮動小数で計算する人は注意が必要

More Related Content

AtCoder Beginner Contest 033 解説

  • 1. ?AtCoder Inc. All rights reserved. 1 AtCoder Beginner Contest #033 解説 AtCoder株式会社 代表取締役 高橋 直大
  • 2. ?AtCoder Inc. All rights reserved. 2 A問題 暗証番号
  • 3. ?AtCoder Inc. All rights reserved. 3 A問題 問題概要 ? 4桁の数が与えられる ? 各桁が全て同じ数字であるか判定せよ
  • 4. ?AtCoder Inc. All rights reserved. 4 A問題 アルゴリズム ? 実際に4文字読み込み、if文などで判定すれば よい ? 例: if(in[0]==in[1]&&in[1]==in[2]&&in[2]==in[3]) – 4桁とも同じ数字には法則性もある – 0000, 1111, 2222, …, 9999は全て 1111の倍数。 ? 1111で割り切れるかどうかを判定してもよい ? 例: if(N%1111==0)
  • 5. ?AtCoder Inc. All rights reserved. 5 B問題 町の合併
  • 6. ?AtCoder Inc. All rights reserved. 6 B問題 問題概要 ? N個の町が合併し、1つの市になる。 ? N個の町の合計人口の過半数以上の人口を持つ町 が存在すれば、新しい市の名前はその町の名前に する ? 存在しなければ、atcoderという名前にする。 ? どのような市の名前になるだろうか？ ? 2 ≦ N ≦ 1,000, 1 ≦ 町の人口 ≦ 100,000
  • 7. ?AtCoder Inc. All rights reserved. 7 B問題 アルゴリズム ? 問題文にあるとおりに実際にループを回してシミュ レートする ? 合計を計算する ? それぞれの町の人口がその合計の過半数以上ある かをifで判定し、あればそれを出力 ? なければatcoderと出力 ? 計算量は O(N)
  • 8. ?AtCoder Inc. All rights reserved. 8 B問題 アルゴリズム ? ちなみに、過半数以上の人口がある町が2つ以上存 在することはない ? (2番目に多い町の人口が過半数あるとすると、1番 目と2番目の合計が全人口を超えてしまい矛盾す る)
  • 9. ?AtCoder Inc. All rights reserved. 9 1. 問題概要 2. アルゴリズム C問題 数式の書き換え
  • 10. ?AtCoder Inc. All rights reserved. 10 C問題 問題概要 ? 1+2+3*4*5+6*7のような、各項が1桁で括弧がなく、 乗算と加算のみの数式が与えられる。 ? これらの数字をいくつか0に書き換えて答えを0にし たい。 ? 最低何個書き換えればよいか。 ? 数式の長さは100,000以下
  • 11. ?AtCoder Inc. All rights reserved. 11 C問題 アルゴリズム ? 各数字を0にする/しないを全て試すと O(2^N)かかる ため、間に合わない ? ある場所を0に書き換えると、どこまで影響が出るだ ろうか。
  • 12. ?AtCoder Inc. All rights reserved. 12 C問題 アルゴリズム ? 1*2*3の1を0にする→ 0*2*3=0 ? 2*4*6の4を0にする→ 2*0*6=0 ? 1+2+3の1を0にする→ 0+2+3 ? 3*6+9の6を0にする→ 3*0+9=0+9 ? 1+2*3+4の2を0にする→1+0*3+4=1+0+4
  • 13. ?AtCoder Inc. All rights reserved. 13 C問題 アルゴリズム ? *だけで繋がっている式のどこかに0があると、その 範囲の答えが0になる ? 0と書かれた項は+を越えた場所には影響しない ? 元の数式の答えを0にするには、+で区切られたそ れぞれの部分の答えを全て0にしなければならない ? 要は、+で区切られた部分それぞれに最低1つの0の 項が欲しい
  • 14. ?AtCoder Inc. All rights reserved. 14 C問題 アルゴリズム ? +で区切る ? 区切ったそれぞれの部分に対して、初期状態で0が 1つもなければ、1回書き換えが必要 ? この合計が必要な最小個数になる ? O(N)
  • 15. ?AtCoder Inc. All rights reserved. 15 D問題 三角形の分類 1. 問題概要 2. アルゴリズム
  • 16. ?AtCoder Inc. All rights reserved. 16 D問題 問題概要 ? 座標平面上の点 (x[i],y[i]) がN個与えられる。 ? N個のうち3つ選んで三角形を作ったとき、それが鋭 角三角形、直角三角形、鈍角三角形になるものを、 それぞれ数える。 ? N ≦ 2,000 ? 部分点: N ≦ 100
  • 17. ?AtCoder Inc. All rights reserved. 17 D問題 アルゴリズム ? 部分点解法 ? 3点を全部選んで角度を計算する ? 角度が 0°より大きく90°より小さいか、90°に等し いか、90°より大きく180°より小さいかの3種類を 分類できればよいので、内積を使ってもよい ? ベクトル(a,b)と(c,d)のなす角θが – 0° < θ < 90°のとき ac+bd > 0 – θ = 90°のとき ac+bd = 0 – 90° < θ < 180° のとき ac+bd < 0
  • 18. ?AtCoder Inc. All rights reserved. 18 D問題 アルゴリズム ? さっきの方法だと計算量は O(N^3) ? 部分点は間に合うが、 満点はとれない ? これ以上早く計算するには、複数の三角形をまとめ て数える必要がある
  • 19. ?AtCoder Inc. All rights reserved. 19 D問題 アルゴリズム ? 三角形の特徴に注目する ? 直角三角形は、1個が直角、他は鋭角 ? 鈍角三角形は、1個が鈍角、他は鋭角 ? 直角、鈍角となる∠ABCの組の個数を求めれば、直 角三角形、鈍角三角形の個数が分かり、全体から 引くと鋭角三角形の個数も計算できる。
  • 20. ?AtCoder Inc. All rights reserved. 20 D問題 アルゴリズム ? ∠ABCのBの部分を固定して、A,Cの組を数えること にする ? ある点から他の全ての点に対して半直線を引くとこ うなる (プログラムでは、角度だけをもてばよい。角 度はatan2等で計算できる。)
  • 21. ?AtCoder Inc. All rights reserved. 21 D問題 アルゴリズム ? これらの角度をソートし、左側を固定する – どこまでが90°未満だろう？ – どこまでが90°だろう？ – どこまでが180°未満だろう？ ? これらは二分探索やしゃくとり法でまとめて高速に 計算できる。二分探索ではO(N log N)、尺取だと O(N) ? ただし環状になっているので、角度の扱いは少し複 雑で気をつける必要がある。(2周分配列をもったり、 内積?外積で求めると楽かもしれない)
  • 22. ?AtCoder Inc. All rights reserved. 22 D問題 アルゴリズム ? 全体をまとめると – 一点選ぶ – そこから他の全て点へのベクトルの角度を求め、ソートす る。 – 二分探索やしゃくとり法で鈍角、直角の個数を数える – 鋭角三角形の個数を、全体から鈍角、直角の個数を引く ことで求める ? 計算量は合計で O(N^2 logn) (しゃくとり法の場合)
  • 23. ?AtCoder Inc. All rights reserved. 23 D問題 アルゴリズム ? 注意 ? 2つのベクトルのなす角度が非常に小さかったり、非 常に90°に近かったり、非常に180°に近かったり することがある。 例1: (-10000,-10000), (-10000,-9999),(10000,10000) 例2: (-10000,-10000), (-9999,10000),(10000,9999) 例3: (-10000,-10000), (1,0),(10000,10000) ? 浮動小数で計算する人は注意が必要