狠狠撸

狠狠撸Share a Scribd company logo

AtCoder Beginner Contest 006 解説

?
?
A
AtCoder Inc.

AtCoder Beginner Contest 006 解説

1 of 57
Downloaded 50 times
AtCoder Beginner Contest 006 解説 AtCoder株式会社 代表取締役 高橋 直大 2014/4/5 1
競技プログラミングを始める前に ? 競技プログラミングをやったことがない人へ – まずはこっちのスライドを見よう！ – http://www.slideshare.net/chokudai/abc004 2014/4/5 2
?AtCoder Inc. All rights reserved. 3 A問題 世界のFIZZBUZZ 1. 問題概要 2. アルゴリズム 2014/4/5 3
A問題 問題概要 ? 1ケタの数字Nが与えられる ? Nが3の倍数、または3が含まれるはYES、そうでない ならNOと出力しなさい 2014/4/5 4
A問題 アルゴリズム ? 基本的なプログラムの流れ – 標準入力から、必要な入力を受け取る ? 今回の場合は、nという1つの整数 – 問題で与えられた処理を行う ? 今回は、3で割り切れる、または、3を含むかを調べる – 標準出力へ、答えを出力する 2014/4/5 5
A問題 アルゴリズム ? 入力 – 1つの数字を、標準入力から受け取る ? Cであれば、scanf(“%d”, &n); など ? C++であれば、cin >> n; ? 入力の受け取り方は、下記の練習問題に記載があります。 – http://practice.contest.atcoder.jp/tasks/practice_1 2014/4/5 6
A問題 アルゴリズム ? 整数nが、以下の条件を満たすかどうか判定する – 3で割り切れるかどうか – 文字3を含むかどうか – これは、if文と、||などの論理演算子を組み合わせること で表記できる。 ? If((3で割り切れる) || (文字3を含む)) print(“YES”); ? もし条件を満たすのであればYES、満たさないのであ ればNOを出力する 2014/4/5 7
A問題 アルゴリズム ? 3で割り切れるかどうか – 余剰を計算する演算子を使用する ? 大抵の言語においては% たまにmod – 7%3を計算すると、1が出てくる、みたいな使い方が出来る – これが0になっているかどうか判定するだけ ? 3を含むかどうか – そもそも、今回の問題では、nが1ケタ – 3を含むnは、n=3の場合のみ ? これは、3で割り切れる数字でもあるので、上の条件に含まれる ? よって、考慮しなくても良い。 2014/4/5 8
A問題 アルゴリズム ? 3を含むかどうか – もし、nが何桁もあった場合 ? 13など、3の倍数でないが、3を含むnが存在する – やり方は何通りか存在する ? nを文字列として持ち、文字3を含むか調べる – Findなどの、文字列検索を行うアルゴリズムを使う – Forループやforeachなどで1文字ずつ調べても良い ? 1ケタずつ整数として調べる。 – まず、%10を使い、1ケタ目の数字だけ取り出す – 次に、それが3であれば終了し、そうでなければ、/10して次の桁に 移行する。 2014/4/5 9
A問題 アルゴリズム ? 1ケタずつ整数として調べる。 – まず、%10を使い、1ケタ目の数字だけ取り出す – 次に、それが3であれば終了し、そうでなければ、/10して 次の桁に移行する。 – 1342 % 10 = 2 ←3でないので、次の値は10で割って134 – 134 % 10 = 4 ←3でないので、次の値は10で割って13 – 13 % 10 = 3 ←3なので終了 2014/4/5 10
A問題 アルゴリズム ? 出力 – 求めた答えを、標準出力より出力する。 – 言語によって違います。 ? printf(“YES?n”); (C) ? cout << “YES” << endl; (C++) ? System.out.println(“YES”); (Java) ? 各言語の標準出力は、下記の練習問題に記載があります。 – http://practice.contest.atcoder.jp/tasks/practice_1 2014/4/5 11
?AtCoder Inc. All rights reserved. 12 B問題 トリボナッチ数列 1. 問題概要 2. アルゴリズム 2014/4/5 12
B問題 問題概要 ? 整数nが与えられる ? トリボナッチ数列の第n項を答えなさい – ただし、数字が大きくなるので、10007で割った余りを出力 しなさい。 ? トリボナッチ数列とは、3つ前の数字までを足した数 字が、次の数字になる数列の事を言います。 – 0,0,1,1,2,4,7,13,24…みたいなの 2014/4/5 13
B問題 アルゴリズム ? 入力 – 整数nを受け取る ? さっきと同じです！ 2014/4/5 14
B問題 アルゴリズム ? 処理 – 4番目から順番に求める ? 1,2,3番目は、予めコンピュータに入力しておく。 – やり方は主に2通り ? 1つ前、2つ前、3つ前の数字を、変数に入れておく – a = 0, b = 0, c = 1のような感じ – １巡したら、a = 0, b = 1, c = 1のようにローテーションさせる ? 過去の全ての結果を配列に確保してしまう。 – 入力が100万までなので、長さ100万の配列を確保する – 計算するときは、ar[n] = ar[n-1] + ar[n-2] + ar[n-3]といった感じ 2014/4/5 15
B問題 アルゴリズム ? 注意点 – B問題の答えは、数字が非常に大きくなる！ ? Int型やlong型では収まりません – 答えるべきものは、10007で割った余り – この時、途中の計算式でも、10007で割った余りを使って 良い ? 最後にだけ計算しようとすると、途中で桁溢れが起きてしまいま す。 2014/4/5 16
B問題 アルゴリズム ? 出力 – A問題と同じく、答えを出力するだけ – Print(ar[n])みたいな感じ 2014/4/5 17
B問題 アルゴリズム ? おまけ – 再帰関数でやると、計算量が膨大になります。 ? 動的計画法みたいにやりましょう。 ? メモ化再帰でもOK 2014/4/5 18
?AtCoder Inc. All rights reserved. 19 C問題 スフィンクスのなぞなぞ 1. 問題概要 2. アルゴリズム 2014/4/5 19
C問題 問題概要 ? スフィンクスがなぞなぞを出します。 ? 「この街には人間が N 人いる。人間は、大人、老人、 赤ちゃんの 3 通りだ。 この街にいる人間の、足の数の合計は M 本で、大 人の足は 2 本、老人の足は 3 本、赤ちゃんの足 は 4 本と仮定した場合、存在する人間の組み合わ せとしてあり得るものを1 つ答えよ。」 – 答えられないと留年する ? NとMが入力されるので、答えを返すプログラムを作 りなさい。 – 答えが存在しない場合は-1 -1 -1を出力する 2014/4/5 20
C問題 問題概要 ? 制約 – 部分点1 ? N<=100 ? M<=500 – 部分点2 ? N<=1500 ? M<=7500 – 満点 ? N<=100000 ? M<=500000 2014/4/5 21
C問題 アルゴリズム ? N,Mに対して、 – N = a + b + c – M = 2a + 3b + 4c – a,b,c ≧ 0 ? なお、大人の人数がa、老人の人数がb、赤ちゃんがcとする ? の連立方程式を解かなければならない？ 2014/4/5 22
C問題 アルゴリズム 部分点１ ? N≦100の時、a,b,cを全て調べることが可能 – a,b,c = {0,0,100}, {0,1,99}….{100,0,0}のように全チェック ? もしこれで、足の本数がMと一致していたら、それを出力 – 全てのa,b,cの組み合わせで条件を満たさなかった時は、 正しい組み合わせは存在しないので、-1 -1 -1を出力 2014/4/5 23
C問題 アルゴリズム 部分点２ ? N≦1500の時、a,b,cを全て調べることが不可能？ – 高速に計算できる方法を考える ? a,bが決まった時、c = N – a – b ? これを使うと、やはり全列挙が可能となる。 – 同様に、それぞれの組み合わせに対して、足の本数が一 致する組み合わせが存在するか調べるだけ。 2014/4/5 24
C問題 アルゴリズム 満点解法 ? 解法1 つるかめ算 – a,b,cのどれかを決めてしまう。 ? 例えば、b=0としてみる。 – すると、M = 2*a + 4*c ? これはただのつるかめ算 – 大人、老人、子供のどれか1つの人数だけ全探索を行い、 残りの2つを、つるかめ算により求める。 ? 人数が負になったり、整数にならない場合は失敗 – 成功する組み合わせがあったらそれを出力 – ダメだったら-1 -1 -1を出力 2014/4/5 25
C問題 アルゴリズム 満点解法 ? 解法2 老人の数の固定 – 老人が2人いた場合 ? 子供１、大人１に変換することが可能 – つまり、老人が2人以上いる組み合わせは、全て老人が1 人以下の組み合わせに変換することが出来る – つまり、老人が0人いる場合と、1人いる場合だけ考えれ ば良い！ – そこまで分かれば全探索すれば良い 2014/4/5 26
C問題 アルゴリズム 満点解法 ? おまけ – 解法1と解法2を組み合わせると、満点解法で解けます – 老人を0,1の２パターンに固定する以外にも、O(1)で解け る解き方はいくつか存在します。 ? 回答が複数ありますが、偶奇さえきちんと合わせれば、大体つじ つまを合わせられます。 – 回答が複数あるので、連立方程式ライブラリとかで解こう とするのは非推奨です。 2014/4/5 27
?AtCoder Inc. All rights reserved. 28 D問題 トランプ挿入ソート 1. 問題概要 2. アルゴリズム 2014/4/5 28
D問題 問題概要 ? 1～Nまでの数字が書かれたカードがN枚存在する ? 山札からカードを1枚抜き取り、任意の場所に挿入 することが可能 ? 山札をソートしたい時に、並び替える必要のある最 小数を求めなさい ? 実は、多くのコンテストに出題されている、超典型問題です。 2014/4/5 29
D問題 問題概要 ? 問題のイメージ – 以下のようなカードが与えられる – カードを抜いて入れ替える 2014/4/5 30 1 3 5 2 4 6
D問題 問題概要 ? 問題のイメージ – 以下のようなカードが与えられる – カードを抜いて入れ替える ? これを繰り返してソートさせる 2014/4/5 31 1 3 5 2 4 6
D問題 問題概要 ? 問題のイメージ – 以下のようなカードが与えられる – カードを抜いて入れ替える ? これを繰り返してソートさせる – ソートが完了するまでの最小手数を出力する ? 今回の場合は2 2014/4/5 32 1 3 5 2 4 6
D問題 問題概要 ? 制約 – 部分点1 ? N≦16 – 部分点2 ? N≦1000 – 満点 ? N≦30000 2014/4/5 33
D問題 アルゴリズム ? 考察 – 全ての並び替えパターンは、n!通り存在する ? これを全て考えるのは不可能 – 何か工夫をしなければ、解くことは難しい 2014/4/5 34
D問題 アルゴリズム 部分点1 ? 先ほどのサンプルでは、「２」と「４」のカードを動かす ことになった。 2014/4/5 35 1 3 5 2 4 6
D問題 アルゴリズム 部分点1 ? 先ほどのサンプルでは、「２」と「４」のカードを動かす ことになった。 – 1個ずつ動かしたが、図のように一気に複数抜いて、一気 に複数差し込んでも良い。 2014/4/5 36 1 3 5 2 4 6
D問題 アルゴリズム 部分点1 ? 先ほどのサンプルでは、「２」と「４」のカードを動かす ことになった。 – 1個ずつ動かしたが、図のように一気に複数抜いて、一気 に複数差し込んでも良い。 – この時、差し込んでソートできる条件は、取り除いた列が ソート済みになっていること 2014/4/5 37 1 3 5 6
D問題 アルゴリズム 部分点1 ? つまり、「どのカードを残すか」を全探索することに よって、その残されたカードがソート済みになってい るかどうか調べれば良い。 – この組み合わせは、Nに対して2^N通りしか存在しない。 ? Nが16程度であれば間に合う ? 2^N通りに対し、全列挙を行い、増加列になっている ものの中で、最も残す数が多いものを調べれば良 い。 – ABC002 D問題「派閥」と同じ考え方 ? 002のDと同じアルゴリズムが10点でごめんなさい＞＜ 2014/4/5 38
D問題 アルゴリズム 部分点1 ? 2^n全列挙の仕方 – 深さ優先探索を使う ? 普通に1つずつ、使う使わないを判定する ? 自然な実装になりやすい？ – 整数のbitを用いた探索を使う ? ABC002と同様 ? 時間がないので後で書いて再アップロードします＞＜ 2014/4/5 39
D問題 アルゴリズム 部分点2 ? さらに計算を早くするには？ – 残す列がソート済みになっていれば良い、という点に着目 する ? 「どのように入れ替えるか」ではなく、「カードを抜い てソートされた状態にするとき、残ったカードの数が 最大にする方法」を考える 2014/4/5 40
D問題 アルゴリズム 部分点2 ? 増加列を求める方法 – 普通に深さ優先探索をすると前回と同じ – 動的計画法を使おう！ ? 左から順番に、「最後にそのカードを使った時の、最大の列の長 さはいくつか」を計算していく ? 最初は1 2014/4/5 41 1 3 5 2 4 6 1
D問題 アルゴリズム 部分点2 ? 増加列を求める方法 – 普通に深さ優先探索をすると前回と同じ – 動的計画法を使おう！ ? 左から順番に、「最後にそのカードを使った時の、最大の列の長 さはいくつか」を計算していく ? 最初は1 ? 次の値は、前の値を利用して、最大値から計算する 2014/4/5 42 1 3 5 2 4 6 1 2
D問題 アルゴリズム 部分点2 ? 増加列を求める方法 – 普通に深さ優先探索をすると前回と同じ – 動的計画法を使おう！ ? 左から順番に、「最後にそのカードを使った時の、最大の列の長 さはいくつか」を計算していく ? 次の値は、前の値を利用して、最大値から計算する 2014/4/5 43 1 3 5 2 4 6 1 2 3 2 3
D問題 アルゴリズム 部分点2 ? 計算量の考察 – 各カードを選ぶ部分がO(n) – そのカードから前のカードの部分列の最大値を選ぶ部分 がO(n) – 併せてO(n^2) 1000程度であれば計算可能となる。 2014/4/5 44 1 3 5 2 4 6 1 2 3 2 3
D問題 アルゴリズム 満点解法 ? さらに計算を早くするには？ – データの持ち方を変えよう！ – ここまで出てきた中で、k枚の部分列が作れるもののうち、 もっともカードの値が小さいものを持つ 2014/4/5 45 1 3 5 2 4 6 増加列 0 1 2 3 4 5 カード -INF INF INF INF INF INF
D問題 アルゴリズム 満点解法 ? さらに計算を早くするには？ – データの持ち方を変えよう！ – ここまで出てきた中で、k枚の部分列が作れるもののうち、 もっともカードの値が小さいものを持つ 2014/4/5 46 1 3 5 2 4 6 1 増加列 0 1 2 3 4 5 カード -INF 1 INF INF INF INF
D問題 アルゴリズム 満点解法 ? さらに計算を早くするには？ – データの持ち方を変えよう！ – ここまで出てきた中で、k枚の部分列が作れるもののうち、 もっともカードの値が小さいものを持つ 2014/4/5 47 1 3 5 2 4 6 1 2 増加列 0 1 2 3 4 5 カード -INF 1 3 INF INF INF
D問題 アルゴリズム 満点解法 ? さらに計算を早くするには？ – データの持ち方を変えよう！ – ここまで出てきた中で、k枚の部分列が作れるもののうち、 もっともカードの値が小さいものを持つ 2014/4/5 48 1 3 5 2 4 6 1 2 3 増加列 0 1 2 3 4 5 カード -INF 1 3 5 INF INF
D問題 アルゴリズム 満点解法 ? さらに計算を早くするには？ – データの持ち方を変えよう！ – ここまで出てきた中で、k枚の部分列が作れるもののうち、 もっともカードの値が小さいものを持つ 2014/4/5 49 1 3 5 2 4 6 1 2 3 2 増加列 0 1 2 3 4 5 カード -INF 1 2 5 INF INF
D問題 アルゴリズム 満点解法 ? さらに計算を早くするには？ – データの持ち方を変えよう！ – ここまで出てきた中で、k枚の部分列が作れるもののうち、 もっともカードの値が小さいものを持つ 2014/4/5 50 1 3 5 2 4 6 1 2 3 2 3 増加列 0 1 2 3 4 5 カード -INF 1 2 4 INF INF
D問題 アルゴリズム 満点解法 ? さらに計算を早くするには？ – データの持ち方を変えよう！ – ここまで出てきた中で、k枚の部分列が作れるもののうち、 もっともカードの値が小さいものを持つ 2014/4/5 51 1 3 5 2 4 6 1 2 3 2 3 増加列 0 1 2 3 4 5 カード -INF 1 2 4 6 INF 4
D問題 アルゴリズム 満点解法 ? 考察 – このカードの配列は、絶対に昇順になっている ? よって、足すべき部分は1か所しかなく、二分探索で求めることが 可能である ? 下図は、今見ているカードを3だとする 2014/4/5 52 増加列 0 1 2 3 4 5 カード -INF 1 2 4 6 INF
D問題 アルゴリズム 満点解法 ? 考察 – このカードの配列は、絶対に昇順になっている ? よって、足すべき部分は1か所しかなく、二分探索で求めることが 可能である ? 下図は、今見ているカードを3だとする 2014/4/5 53 増加列 0 1 2 3 4 5 カード -INF 1 2 4 6 INF
D問題 アルゴリズム 満点解法 ? 考察 – このカードの配列は、絶対に昇順になっている ? よって、足すべき部分は1か所しかなく、二分探索で求めることが 可能である ? 下図は、今見ているカードを3だとする 2014/4/6 54 増加列 0 1 2 3 4 5 カード -INF 1 2 4 6 INF
D問題 アルゴリズム 満点解法 ? 考察 – このカードの配列は、絶対に昇順になっている ? よって、足すべき部分は1か所しかなく、二分探索で求めることが 可能である ? 下図は、今見ているカードを3だとする こんな感じで求まる 2014/4/6 55 増加列 0 1 2 3 4 5 カード -INF 1 2 4 6 INF
D問題 アルゴリズム 満点解法 ? 考察 – このカードの配列は、絶対に昇順になっている ? よって、足すべき部分は1か所しかなく、二分探索で求めることが 可能である – よって、計算量はO(nlogn)となる。 2014/4/5 56 増加列 0 1 2 3 4 5 カード -INF 1 2 4 6 INF
D問題 アルゴリズム ? おまけ – 最長増加部分列(Longest Increasing Subsequence)と呼ば れる有名なアルゴリズムです。 ? 動的計画法に慣れていれば、知らなくても解ける問題ではありま す。 2014/4/5 57

More Related Content

AtCoder Beginner Contest 006 解説

  • 1. AtCoder Beginner Contest 006 解説 AtCoder株式会社 代表取締役 高橋 直大 2014/4/5 1
  • 3. ?AtCoder Inc. All rights reserved. 3 A問題 世界のFIZZBUZZ 1. 問題概要 2. アルゴリズム 2014/4/5 3
  • 4. A問題 問題概要 ? 1ケタの数字Nが与えられる ? Nが3の倍数、または3が含まれるはYES、そうでない ならNOと出力しなさい 2014/4/5 4
  • 5. A問題 アルゴリズム ? 基本的なプログラムの流れ – 標準入力から、必要な入力を受け取る ? 今回の場合は、nという1つの整数 – 問題で与えられた処理を行う ? 今回は、3で割り切れる、または、3を含むかを調べる – 標準出力へ、答えを出力する 2014/4/5 5
  • 6. A問題 アルゴリズム ? 入力 – 1つの数字を、標準入力から受け取る ? Cであれば、scanf(“%d”, &n); など ? C++であれば、cin >> n; ? 入力の受け取り方は、下記の練習問題に記載があります。 – http://practice.contest.atcoder.jp/tasks/practice_1 2014/4/5 6
  • 7. A問題 アルゴリズム ? 整数nが、以下の条件を満たすかどうか判定する – 3で割り切れるかどうか – 文字3を含むかどうか – これは、if文と、||などの論理演算子を組み合わせること で表記できる。 ? If((3で割り切れる) || (文字3を含む)) print(“YES”); ? もし条件を満たすのであればYES、満たさないのであ ればNOを出力する 2014/4/5 7
  • 8. A問題 アルゴリズム ? 3で割り切れるかどうか – 余剰を計算する演算子を使用する ? 大抵の言語においては% たまにmod – 7%3を計算すると、1が出てくる、みたいな使い方が出来る – これが0になっているかどうか判定するだけ ? 3を含むかどうか – そもそも、今回の問題では、nが1ケタ – 3を含むnは、n=3の場合のみ ? これは、3で割り切れる数字でもあるので、上の条件に含まれる ? よって、考慮しなくても良い。 2014/4/5 8
  • 9. A問題 アルゴリズム ? 3を含むかどうか – もし、nが何桁もあった場合 ? 13など、3の倍数でないが、3を含むnが存在する – やり方は何通りか存在する ? nを文字列として持ち、文字3を含むか調べる – Findなどの、文字列検索を行うアルゴリズムを使う – Forループやforeachなどで1文字ずつ調べても良い ? 1ケタずつ整数として調べる。 – まず、%10を使い、1ケタ目の数字だけ取り出す – 次に、それが3であれば終了し、そうでなければ、/10して次の桁に 移行する。 2014/4/5 9
  • 10. A問題 アルゴリズム ? 1ケタずつ整数として調べる。 – まず、%10を使い、1ケタ目の数字だけ取り出す – 次に、それが3であれば終了し、そうでなければ、/10して 次の桁に移行する。 – 1342 % 10 = 2 ←3でないので、次の値は10で割って134 – 134 % 10 = 4 ←3でないので、次の値は10で割って13 – 13 % 10 = 3 ←3なので終了 2014/4/5 10
  • 11. A問題 アルゴリズム ? 出力 – 求めた答えを、標準出力より出力する。 – 言語によって違います。 ? printf(“YES?n”); (C) ? cout << “YES” << endl; (C++) ? System.out.println(“YES”); (Java) ? 各言語の標準出力は、下記の練習問題に記載があります。 – http://practice.contest.atcoder.jp/tasks/practice_1 2014/4/5 11
  • 12. ?AtCoder Inc. All rights reserved. 12 B問題 トリボナッチ数列 1. 問題概要 2. アルゴリズム 2014/4/5 12
  • 13. B問題 問題概要 ? 整数nが与えられる ? トリボナッチ数列の第n項を答えなさい – ただし、数字が大きくなるので、10007で割った余りを出力 しなさい。 ? トリボナッチ数列とは、3つ前の数字までを足した数 字が、次の数字になる数列の事を言います。 – 0,0,1,1,2,4,7,13,24…みたいなの 2014/4/5 13
  • 14. B問題 アルゴリズム ? 入力 – 整数nを受け取る ? さっきと同じです！ 2014/4/5 14
  • 15. B問題 アルゴリズム ? 処理 – 4番目から順番に求める ? 1,2,3番目は、予めコンピュータに入力しておく。 – やり方は主に2通り ? 1つ前、2つ前、3つ前の数字を、変数に入れておく – a = 0, b = 0, c = 1のような感じ – １巡したら、a = 0, b = 1, c = 1のようにローテーションさせる ? 過去の全ての結果を配列に確保してしまう。 – 入力が100万までなので、長さ100万の配列を確保する – 計算するときは、ar[n] = ar[n-1] + ar[n-2] + ar[n-3]といった感じ 2014/4/5 15
  • 16. B問題 アルゴリズム ? 注意点 – B問題の答えは、数字が非常に大きくなる！ ? Int型やlong型では収まりません – 答えるべきものは、10007で割った余り – この時、途中の計算式でも、10007で割った余りを使って 良い ? 最後にだけ計算しようとすると、途中で桁溢れが起きてしまいま す。 2014/4/5 16
  • 17. B問題 アルゴリズム ? 出力 – A問題と同じく、答えを出力するだけ – Print(ar[n])みたいな感じ 2014/4/5 17
  • 18. B問題 アルゴリズム ? おまけ – 再帰関数でやると、計算量が膨大になります。 ? 動的計画法みたいにやりましょう。 ? メモ化再帰でもOK 2014/4/5 18
  • 19. ?AtCoder Inc. All rights reserved. 19 C問題 スフィンクスのなぞなぞ 1. 問題概要 2. アルゴリズム 2014/4/5 19
  • 20. C問題 問題概要 ? スフィンクスがなぞなぞを出します。 ? 「この街には人間が N 人いる。人間は、大人、老人、 赤ちゃんの 3 通りだ。 この街にいる人間の、足の数の合計は M 本で、大 人の足は 2 本、老人の足は 3 本、赤ちゃんの足 は 4 本と仮定した場合、存在する人間の組み合わ せとしてあり得るものを1 つ答えよ。」 – 答えられないと留年する ? NとMが入力されるので、答えを返すプログラムを作 りなさい。 – 答えが存在しない場合は-1 -1 -1を出力する 2014/4/5 20
  • 21. C問題 問題概要 ? 制約 – 部分点1 ? N<=100 ? M<=500 – 部分点2 ? N<=1500 ? M<=7500 – 満点 ? N<=100000 ? M<=500000 2014/4/5 21
  • 22. C問題 アルゴリズム ? N,Mに対して、 – N = a + b + c – M = 2a + 3b + 4c – a,b,c ≧ 0 ? なお、大人の人数がa、老人の人数がb、赤ちゃんがcとする ? の連立方程式を解かなければならない？ 2014/4/5 22
  • 23. C問題 アルゴリズム 部分点１ ? N≦100の時、a,b,cを全て調べることが可能 – a,b,c = {0,0,100}, {0,1,99}….{100,0,0}のように全チェック ? もしこれで、足の本数がMと一致していたら、それを出力 – 全てのa,b,cの組み合わせで条件を満たさなかった時は、 正しい組み合わせは存在しないので、-1 -1 -1を出力 2014/4/5 23
  • 24. C問題 アルゴリズム 部分点２ ? N≦1500の時、a,b,cを全て調べることが不可能？ – 高速に計算できる方法を考える ? a,bが決まった時、c = N – a – b ? これを使うと、やはり全列挙が可能となる。 – 同様に、それぞれの組み合わせに対して、足の本数が一 致する組み合わせが存在するか調べるだけ。 2014/4/5 24
  • 25. C問題 アルゴリズム 満点解法 ? 解法1 つるかめ算 – a,b,cのどれかを決めてしまう。 ? 例えば、b=0としてみる。 – すると、M = 2*a + 4*c ? これはただのつるかめ算 – 大人、老人、子供のどれか1つの人数だけ全探索を行い、 残りの2つを、つるかめ算により求める。 ? 人数が負になったり、整数にならない場合は失敗 – 成功する組み合わせがあったらそれを出力 – ダメだったら-1 -1 -1を出力 2014/4/5 25
  • 26. C問題 アルゴリズム 満点解法 ? 解法2 老人の数の固定 – 老人が2人いた場合 ? 子供１、大人１に変換することが可能 – つまり、老人が2人以上いる組み合わせは、全て老人が1 人以下の組み合わせに変換することが出来る – つまり、老人が0人いる場合と、1人いる場合だけ考えれ ば良い！ – そこまで分かれば全探索すれば良い 2014/4/5 26
  • 27. C問題 アルゴリズム 満点解法 ? おまけ – 解法1と解法2を組み合わせると、満点解法で解けます – 老人を0,1の２パターンに固定する以外にも、O(1)で解け る解き方はいくつか存在します。 ? 回答が複数ありますが、偶奇さえきちんと合わせれば、大体つじ つまを合わせられます。 – 回答が複数あるので、連立方程式ライブラリとかで解こう とするのは非推奨です。 2014/4/5 27
  • 28. ?AtCoder Inc. All rights reserved. 28 D問題 トランプ挿入ソート 1. 問題概要 2. アルゴリズム 2014/4/5 28
  • 29. D問題 問題概要 ? 1～Nまでの数字が書かれたカードがN枚存在する ? 山札からカードを1枚抜き取り、任意の場所に挿入 することが可能 ? 山札をソートしたい時に、並び替える必要のある最 小数を求めなさい ? 実は、多くのコンテストに出題されている、超典型問題です。 2014/4/5 29
  • 30. D問題 問題概要 ? 問題のイメージ – 以下のようなカードが与えられる – カードを抜いて入れ替える 2014/4/5 30 1 3 5 2 4 6
  • 31. D問題 問題概要 ? 問題のイメージ – 以下のようなカードが与えられる – カードを抜いて入れ替える ? これを繰り返してソートさせる 2014/4/5 31 1 3 5 2 4 6
  • 32. D問題 問題概要 ? 問題のイメージ – 以下のようなカードが与えられる – カードを抜いて入れ替える ? これを繰り返してソートさせる – ソートが完了するまでの最小手数を出力する ? 今回の場合は2 2014/4/5 32 1 3 5 2 4 6
  • 33. D問題 問題概要 ? 制約 – 部分点1 ? N≦16 – 部分点2 ? N≦1000 – 満点 ? N≦30000 2014/4/5 33
  • 34. D問題 アルゴリズム ? 考察 – 全ての並び替えパターンは、n!通り存在する ? これを全て考えるのは不可能 – 何か工夫をしなければ、解くことは難しい 2014/4/5 34
  • 35. D問題 アルゴリズム 部分点1 ? 先ほどのサンプルでは、「２」と「４」のカードを動かす ことになった。 2014/4/5 35 1 3 5 2 4 6
  • 36. D問題 アルゴリズム 部分点1 ? 先ほどのサンプルでは、「２」と「４」のカードを動かす ことになった。 – 1個ずつ動かしたが、図のように一気に複数抜いて、一気 に複数差し込んでも良い。 2014/4/5 36 1 3 5 2 4 6
  • 37. D問題 アルゴリズム 部分点1 ? 先ほどのサンプルでは、「２」と「４」のカードを動かす ことになった。 – 1個ずつ動かしたが、図のように一気に複数抜いて、一気 に複数差し込んでも良い。 – この時、差し込んでソートできる条件は、取り除いた列が ソート済みになっていること 2014/4/5 37 1 3 5 6
  • 38. D問題 アルゴリズム 部分点1 ? つまり、「どのカードを残すか」を全探索することに よって、その残されたカードがソート済みになってい るかどうか調べれば良い。 – この組み合わせは、Nに対して2^N通りしか存在しない。 ? Nが16程度であれば間に合う ? 2^N通りに対し、全列挙を行い、増加列になっている ものの中で、最も残す数が多いものを調べれば良 い。 – ABC002 D問題「派閥」と同じ考え方 ? 002のDと同じアルゴリズムが10点でごめんなさい＞＜ 2014/4/5 38
  • 39. D問題 アルゴリズム 部分点1 ? 2^n全列挙の仕方 – 深さ優先探索を使う ? 普通に1つずつ、使う使わないを判定する ? 自然な実装になりやすい？ – 整数のbitを用いた探索を使う ? ABC002と同様 ? 時間がないので後で書いて再アップロードします＞＜ 2014/4/5 39
  • 40. D問題 アルゴリズム 部分点2 ? さらに計算を早くするには？ – 残す列がソート済みになっていれば良い、という点に着目 する ? 「どのように入れ替えるか」ではなく、「カードを抜い てソートされた状態にするとき、残ったカードの数が 最大にする方法」を考える 2014/4/5 40
  • 41. D問題 アルゴリズム 部分点2 ? 増加列を求める方法 – 普通に深さ優先探索をすると前回と同じ – 動的計画法を使おう！ ? 左から順番に、「最後にそのカードを使った時の、最大の列の長 さはいくつか」を計算していく ? 最初は1 2014/4/5 41 1 3 5 2 4 6 1
  • 42. D問題 アルゴリズム 部分点2 ? 増加列を求める方法 – 普通に深さ優先探索をすると前回と同じ – 動的計画法を使おう！ ? 左から順番に、「最後にそのカードを使った時の、最大の列の長 さはいくつか」を計算していく ? 最初は1 ? 次の値は、前の値を利用して、最大値から計算する 2014/4/5 42 1 3 5 2 4 6 1 2
  • 43. D問題 アルゴリズム 部分点2 ? 増加列を求める方法 – 普通に深さ優先探索をすると前回と同じ – 動的計画法を使おう！ ? 左から順番に、「最後にそのカードを使った時の、最大の列の長 さはいくつか」を計算していく ? 次の値は、前の値を利用して、最大値から計算する 2014/4/5 43 1 3 5 2 4 6 1 2 3 2 3
  • 44. D問題 アルゴリズム 部分点2 ? 計算量の考察 – 各カードを選ぶ部分がO(n) – そのカードから前のカードの部分列の最大値を選ぶ部分 がO(n) – 併せてO(n^2) 1000程度であれば計算可能となる。 2014/4/5 44 1 3 5 2 4 6 1 2 3 2 3
  • 45. D問題 アルゴリズム 満点解法 ? さらに計算を早くするには？ – データの持ち方を変えよう！ – ここまで出てきた中で、k枚の部分列が作れるもののうち、 もっともカードの値が小さいものを持つ 2014/4/5 45 1 3 5 2 4 6 増加列 0 1 2 3 4 5 カード -INF INF INF INF INF INF
  • 46. D問題 アルゴリズム 満点解法 ? さらに計算を早くするには？ – データの持ち方を変えよう！ – ここまで出てきた中で、k枚の部分列が作れるもののうち、 もっともカードの値が小さいものを持つ 2014/4/5 46 1 3 5 2 4 6 1 増加列 0 1 2 3 4 5 カード -INF 1 INF INF INF INF
  • 47. D問題 アルゴリズム 満点解法 ? さらに計算を早くするには？ – データの持ち方を変えよう！ – ここまで出てきた中で、k枚の部分列が作れるもののうち、 もっともカードの値が小さいものを持つ 2014/4/5 47 1 3 5 2 4 6 1 2 増加列 0 1 2 3 4 5 カード -INF 1 3 INF INF INF
  • 48. D問題 アルゴリズム 満点解法 ? さらに計算を早くするには？ – データの持ち方を変えよう！ – ここまで出てきた中で、k枚の部分列が作れるもののうち、 もっともカードの値が小さいものを持つ 2014/4/5 48 1 3 5 2 4 6 1 2 3 増加列 0 1 2 3 4 5 カード -INF 1 3 5 INF INF
  • 49. D問題 アルゴリズム 満点解法 ? さらに計算を早くするには？ – データの持ち方を変えよう！ – ここまで出てきた中で、k枚の部分列が作れるもののうち、 もっともカードの値が小さいものを持つ 2014/4/5 49 1 3 5 2 4 6 1 2 3 2 増加列 0 1 2 3 4 5 カード -INF 1 2 5 INF INF
  • 50. D問題 アルゴリズム 満点解法 ? さらに計算を早くするには？ – データの持ち方を変えよう！ – ここまで出てきた中で、k枚の部分列が作れるもののうち、 もっともカードの値が小さいものを持つ 2014/4/5 50 1 3 5 2 4 6 1 2 3 2 3 増加列 0 1 2 3 4 5 カード -INF 1 2 4 INF INF
  • 51. D問題 アルゴリズム 満点解法 ? さらに計算を早くするには？ – データの持ち方を変えよう！ – ここまで出てきた中で、k枚の部分列が作れるもののうち、 もっともカードの値が小さいものを持つ 2014/4/5 51 1 3 5 2 4 6 1 2 3 2 3 増加列 0 1 2 3 4 5 カード -INF 1 2 4 6 INF 4
  • 52. D問題 アルゴリズム 満点解法 ? 考察 – このカードの配列は、絶対に昇順になっている ? よって、足すべき部分は1か所しかなく、二分探索で求めることが 可能である ? 下図は、今見ているカードを3だとする 2014/4/5 52 増加列 0 1 2 3 4 5 カード -INF 1 2 4 6 INF
  • 53. D問題 アルゴリズム 満点解法 ? 考察 – このカードの配列は、絶対に昇順になっている ? よって、足すべき部分は1か所しかなく、二分探索で求めることが 可能である ? 下図は、今見ているカードを3だとする 2014/4/5 53 増加列 0 1 2 3 4 5 カード -INF 1 2 4 6 INF
  • 54. D問題 アルゴリズム 満点解法 ? 考察 – このカードの配列は、絶対に昇順になっている ? よって、足すべき部分は1か所しかなく、二分探索で求めることが 可能である ? 下図は、今見ているカードを3だとする 2014/4/6 54 増加列 0 1 2 3 4 5 カード -INF 1 2 4 6 INF
  • 55. D問題 アルゴリズム 満点解法 ? 考察 – このカードの配列は、絶対に昇順になっている ? よって、足すべき部分は1か所しかなく、二分探索で求めることが 可能である ? 下図は、今見ているカードを3だとする こんな感じで求まる 2014/4/6 55 増加列 0 1 2 3 4 5 カード -INF 1 2 4 6 INF
  • 56. D問題 アルゴリズム 満点解法 ? 考察 – このカードの配列は、絶対に昇順になっている ? よって、足すべき部分は1か所しかなく、二分探索で求めることが 可能である – よって、計算量はO(nlogn)となる。 2014/4/5 56 増加列 0 1 2 3 4 5 カード -INF 1 2 4 6 INF
  • 57. D問題 アルゴリズム ? おまけ – 最長増加部分列(Longest Increasing Subsequence)と呼ば れる有名なアルゴリズムです。 ? 動的計画法に慣れていれば、知らなくても解ける問題ではありま す。 2014/4/5 57