CODE FESTIVAL 2014 予選A 解説
- 1. CODE FESTIVAL 2014 予選A 解説 AtCoder株式会社 代表取締役 高橋 直大 2014/9/20 1
- 2. ?AtCoder Inc. All rights reserved. 2 A問題 CODE FESTIVAL 2014 2014/9/20
- 3. A問題 ?問題概要 –文字列Sが与えられる。 –文字列Sの末尾に”2014”を付け加えた内容を出力してくだ さい。 ?解説 –文字列Sに、”2014”を加えて出力。 –もしくは、Sを出力した後、”2014”を出力 ?Sを出力する際に、改行をしないことに注意！ 2014/9/20 3
- 4. ?AtCoder Inc. All rights reserved. 4 B問題 とても長い文字列 2014/9/20
- 5. B問題 問題概要 ?文字列Aが与えられる。 ?文字列Sは、文字列Aを大量に連結させた文字列で ある。 ?文字列SのB番目の文字を出力しなさい。 ?制約 –1 ≦ |A| ≦ 20 –1 ≦ B ≦ 1,000,000,000 2014/9/20 5
- 6. B問題 アルゴリズム ?文字列Sを真面目に作ると、時間がかかってしまう。 –必要な分まで生成すれば良い。 ?B文字目まで生成すると、部分点が取れる。 ?満点を取るには、文字列Sを作らず、B文字目を予測 しなければならない。 –文字列Sは、文字列Aの繰り返しなので、Aの長さで割った 余りから、B文字目の文字を予測出来る！ 2014/9/20 6
- 7. ?AtCoder Inc. All rights reserved. 7 C問題 2月29日 2014/9/20
- 8. C問題 問題概要 ?A年元旦から、B年大晦日までに、2月29日が何回あ るかを出力しなさい。 ?制約 –1 ≦ A ≦ B ≦ 2,000,000,000 2014/9/20 8
- 9. C問題 アルゴリズム ?A年からB年のそれぞれの年に対し、計算すれば、 部分点は得られる。 –満点の制約は満たせない ?満点を取るには、上手くまとめて数えなければなら ない。 –しかし、上手く数えるのは難しい。 –そこで、工夫して数える必要がある。 2014/9/20 9
- 10. C問題 アルゴリズム ?まず、「西暦0年からA年までのうるう年の数」を求め る関数calc(A)について考える。 –これは、0年が基準となっているため、以下の３つが簡単 にカウントできる。 ?4の倍数となる西暦年 ?100の倍数となる西暦年 ?400の倍数となる西暦年 –これらを纏めてカウントする。 ?あとは、calc(B) – calc(A-1)を計算すれば、求めたい 値を求めることが出来る。 2014/9/20 10
- 11. ?AtCoder Inc. All rights reserved. 11 D問題 壊れた電卓 1.問題概要 2.アルゴリズム 2014/9/20
- 12. D問題 問題概要 ?整数Aが与えられる。 ?高橋君の電卓は、K+1回種類以上の数字を入力す ると壊れてしまう。 ?Aに出来るだけ近い整数を入力したい。 ?その差の大きさはいくつか。 ?制約 –1≦A≦ 10^15 –1≦K≦10 2014/9/20 12
- 13. D問題 アルゴリズム ?部分点を取るだけであれば、1から100,000の全ての 数について、条件を満たすか調べ、条件を満たした 数のうち、最も差の小さいものを採用すれば良い。 –この方法だと、満点は間に合わない。 ?満点解法は、何か工夫する必要がある。 –工夫の仕方は色々 ?bitDP ?貪欲法 ?条件を決めて全探索 –今回はこれを紹介！ 2014/9/20 13
- 14. D問題 アルゴリズム ?今回の問題の制約上、以下のようなことが解る –出来るだけ左の桁は一致させたい。 ?右の方の桁は、間違えていても大きな違いにならない。 –右の方の桁は、「最大値」や「最小値」を目指すことになる ため、同じ数字しか使わない。 ?よって、以下のような処理を行えば良い。 –左からP桁目までは、整数Aと同じにする –左からP+1桁目の桁をQにする –左からP+2桁目以降の桁をRにする –この、P,Q,Rについて全探索を行えば良い。 2014/9/20 14