Code Formula 2014 予選A 解説
- 1. Code Formula 2014 予選A 解説 AtCoder株式会社 代表取締役 高橋 直大 2014/8/20 1
- 2. ?AtCoder Inc. All rights reserved. 2 A問題 立方数 1.問題概要 2.アルゴリズム 2014/8/20
- 3. A問題 問題概要 ?整数Nが与えられる ?Nが立方数かどうかを判定しなさい ?制約 ?1 ≦ N ≦ 1,000,000 2014/8/20 3
- 4. A問題 アルゴリズム ?方針1 –Nの1/3乗を求め、整数になっているかどうかを判定する ?整数になっているかは難しいので、最も近い整数に近似し、その 整数を3乗した数がNになっているのか判定するのが良い。 ?直接求めることが可能だが、誤差に注意する必要あり。 ?方針2 –1から100までの全ての数を3乗し、Nが存在するかどうか を判定する ?Nが100万以下ということは、Nの三乗根は100以下であることを利 用する ?こちらの方が確実 2014/8/20 4
- 5. ?AtCoder Inc. All rights reserved. 5 B問題 ボウリングゲーム 1.問題概要 2.アルゴリズム 2014/8/20
- 6. B問題 問題概要 ?ボウリングで倒したピンが、番号で与えられる ?グラフィカルな形式に変換しなさい 2014/8/20 6
- 7. B問題 アルゴリズム ?長さ10の配列を用意する –それぞれに0を入れておく ?1投目に倒したピンの番号に対応する配列に1を入 れる ?2投目に倒したピンの番号に対応する配列に2を入 れる ?それぞれのピンの場所に対して、配列の番号に合 わせた文字を出力する 2014/8/20 7
- 8. B問題 アルゴリズム ?よくある間違い –末尾改行を入れていない ?A問題と同じく、末尾改行が必須となります。 ?フォーマットを整える問題なので、フォーマットは統一しましょう。 –出力順序を間違えている 2014/8/20 8
- 9. ?AtCoder Inc. All rights reserved. 9 C問題 決勝進出者 1.問題概要 2.アルゴリズム 2014/8/20
- 10. C問題 問題概要 ?N = 4, K = 5の時 –最初の段階で、確定するのは以下の5人 2014/8/20 10 予選A 予選B 予選C 予選D
- 11. C問題 問題概要 ?N = 4, K = 5の時 –最初の段階で、確定するのは以下の5人 –予選Aの結果が出ても同じ 2014/8/20 11 予選A 予選B 予選C 予選D 1 2 3 4 5
- 12. C問題 問題概要 ?N = 4, K = 5の時 –最初の段階で、確定するのは以下の5人 –予選B以降は、既に通過した人の分を先に回す必要があ る ?該当する緑のマスが、2が被っているので、水色のマスが新規に 通過枠となる。 2014/8/20 12 予選A 予選B 予選C 予選D 1 2 2 1 3 3 4 4 5 5
- 13. C問題 問題概要 ?N = 4, K = 5の時 –最初の段階で、確定するのは以下の5人 –予選B以降は、既に通過した人の分を先に回す必要があ る ?該当する緑のマスが、2が被っているので、水色のマスが新規に 通過枠となる。が、この枠も被っているので、次の通過枠に。 2014/8/20 13 予選A 予選B 予選C 予選D 1 2 2 1 3 3 4 4 5 5
- 14. C問題 問題概要 ?N = 4, K = 5の時 –最初の段階で、確定するのは以下の5人 –予選B以降は、既に通過した人の分を先に回す必要があ る ?ここまで通過枠を動かした段階で、もう重複している人はいない ため、予選Bで通過が確定していく人はいない。 2014/8/20 14 予選A 予選B 予選C 予選D 1 2 2 1 3 3 4 4 5 5
- 15. C問題 問題概要 ?N = 4, K = 5の時 –最初の段階で、確定するのは以下の5人 –予選B以降は、既に通過した人の分を先に回す必要があ る ?予選Cでは以下のようになる。 2014/8/20 15 予選A 予選B 予選C 予選D 1 2 1 2 1 2 3 3 3 4 4 4 5 5 5
- 16. C問題 問題概要 ?N = 4, K = 5の時 –最初の段階で、確定するのは以下の5人 –予選B以降は、既に通過した人の分を先に回す必要があ る ?予選Dでは以下のようになる。 –説明の都合でサンプルとは少し違います。 2014/8/20 16 予選A 予選B 予選C 予選D 1 2 1 2 2 1 2 1 3 3 3 3 4 4 4 5 5 5 5 4
- 17. C問題 アルゴリズム ?注意点 –実装に混乱しないようにしよう！ ?実装するべきものはそんなに多くない！ –通過枠を1つずつ確認する処理 –通過枠を1つ増やす処理 ?増やした時、既に順位が確定していれば、そこを確認する処理も必要 –制限時間に気を付けよう！ ?通過枠を毎回頭から確認していくと、制限時間に間に合いません –今どこまでが通過枠になっているかを保持しておく 2014/8/20 17
- 18. ?AtCoder Inc. All rights reserved. 18 D問題 無刻印キーボード 1.問題概要 2.アルゴリズム 2014/8/20
- 19. D問題 問題概要 ?キートップの書かれていないキーボードが存在する ?文章を打ちたいが、キーを一部しか覚えていない ?解らない際は、覚えていないキーの中からランダム に打ち、間違えた場合は消す ?ある文章を打ちたい時に、キーを打つ必要のある回 数の期待値を出力せよ ?制約 ?文字数≦50, 文字種≦36 2014/8/20 19
- 20. D問題 アルゴリズム ?純粋な探索は到底間に合わない。 ?動的計画法も難しい –キーの種類は36種類 –どのキーが解っているかを記憶するには2^36通り覚える 必要がある ?そこで、何か工夫する必要がある。 2014/8/20 20
- 21. D問題 アルゴリズム ?各キーについて注目する –正しいタイミングで打つ必要がある回数は、打ちたい文章 の出現文字数と同じ –つまり、間違ったタイミングで打ってしまう回数の期待値を 求めれば良い ?各文字について、間違えるとしても、間違える回数は高々1回 –その場合、文字を消す処理も必要なので、打つ回数は2回増える ?間違える確率は、打たれるべき文字の前に、場所が不明な文字 が何種類あるかで決まる。 –例えば、”abc”と打ちたい時、’c’に着目すると、’a’と打ちたい時にcと 打ってしまうパターンや、’b’と打ちたい時に’c’に打ってしまうパター ンが存在し、それらを避けることが可能な確率は、’a’および’b’が’c’ より先に見つかる確率であり、これは1/3である。 –つまり、間違えない確率は、1/(手前にある不明な種類数+1)である。 ?出現しない文字も同様であることに注意 2014/8/20 21
- 22. D問題 アルゴリズム ?注意点 –動的計画法で解く場合も、残り文字数に着目すれば解け なくはない。 ?だが、単純に計算した方が実装はずっとシンプルになる –文字数の制約が50文字までだが、もちろん10万文字など でも解ける ?制約に騙されないように！ 2014/8/20 22