CODE FESTIVAL 2014 予選A 解説 AtCoder株式会社 代表取締役 高橋 直大 2014/10/06 1 A問題 CODE FESTIVAL 2014 2014/10/06 ©AtCoder Inc. All rights reserved. 2 2 A問題 • 問題概要 – 文字列Sが与えられる – 文字列Sの末尾に”2014”を付け加えた内容を出力してくだ さい • 制約 – 1≦|S|≦20 2014/10/06 3 A問題 • 解説 – 文字列Sを、標準入力から受け取る • 標準入力が解らない場合は次のページをチェック – 文字列Sに、”2014”を加えて出力 • 標準出力が解らない場合も次のページをチェック – もしくは、Sを出力した後、”2014”を出力 • Sを出力する際に、改行をしないことに注意！ 2014/10/06 4 A問題 • 標準入力、標準出力について – 言語によってさまざま • C言語なら、scanfで入力、prinEで出力 • C++なら、cinで入力、coutで出力 • その他の言語は、以下の解答例でチェックしよう！ – hHp://pracKce.contest.atcoder.jp/tasks/pracKce_1 2014/10/06 5 B問題 とても長い文字列 2014/10/06 ©AtCoder Inc. All rights reserved. 6 6 B問題 問題概要 • 文字列Aが与えられる。 • 文字列Sは、文字列Aを大量に連結させた文字列で ある。 • 文字列SのB番目の文字を出力しなさい。 • 制約 – 1 ≦ |A| ≦ 20 – 1 ≦ B ≦ 1,000,000,000 2014/10/06 7 B問題 アルゴリズム • 文字列Sを真面目に作ると、時間がかかってしまう – 必要な分まで生成すれば良い • B文字目まで生成すると、部分点が取れる • 満点を取るには、文字列Sを作らず、B文字目を予測 しなければならない – 文字列Sは、文字列Aの繰り返しなので、Aの長さで割った 余りから、B文字目の文字を予測出来る！ 2014/10/06 8 B問題 アルゴリズム • 具体的な予測方法 – Aが”abc”の場合 • Sは、”abcabcabcabcabc….” – 1,4,7,10文字目はa – 2,5,8,11文字目はb – 3,6,9,12文字目はc • つまり、文字数である3で割った余りから、文字が予測出来る • ○○で割った余り、を求める方法 – 剰余を計算する演算子は大抵の言語に実装されている • 殆どの言語で%、一部の言語でmod • これを使えば、A[B%A.Length]などで簡単に求められる 2014/10/06 9 C問題 2月29日 2014/10/06 ©AtCoder Inc. All rights reserved. 10 10 C問題 問題概要 • A年元旦から、B年大晦日までに、2月29日が何回あ るかを出力しなさい。 • 制約 – 1 ≦ A ≦ B ≦ 2,000,000,000 2014/10/06 11 C問題 アルゴリズム • A年からB年のそれぞれの年に対し、計算すれば、 部分点は得られる – 満点の制約は満たせない • 満点を取るには、上手くまとめて数えなければなら ない – しかし、上手く数えるのは難しい – そこで、工夫して数える必要がある 2014/10/06 12 C問題 アルゴリズム • まず、「西暦0年からA年までのうるう年の数」を求め る関数calc(A)について考える – これは、0年が基準となっているため、以下の３つが簡単 にカウントできる • 4の倍数となる西暦年 • 100の倍数となる西暦年 • 400の倍数となる西暦年 – これらを纏めてカウントする • あとは、calc(B) – calc(A-‐1)を計算すれば、求めたい 値を求めることが出来る 2014/10/06 13 C問題 アルゴリズム • 具体的な実装例 – 1年からN年までの、うるう年の回数を求めるとすると、 • N/4 – N/100 + N/400 • 上記の式で求めることが出来る – 4年に1回、100年に1回、400年に1回を別々に求めている – 他にも、400年で97回なのを利用して、端数をforループで 調べる、などの方法もある • 一部、4年飛ばしで調べた回答がACになったようですが、かなり早 い言語を選択しない限り間に合いません 2014/10/06 14 D問題 壊れた電卓 1. 問題概要 2. アルゴリズム 2014/10/06 ©AtCoder Inc. All rights reserved. 15 15 D問題 問題概要 • 整数Aが与えられる • 高橋君の電卓は、K+1回種類以上の数字を入力す ると壊れてしまう • Aに出来るだけ近い整数を入力したい • その差の大きさはいくつか • 制約 – 1≦A≦ 10^15 – 1≦K≦10 2014/10/06 16 D問題 アルゴリズム • 部分点を取るだけであれば、1から100,000の全ての 数について、条件を満たすか調べ、条件を満たした 数のうち、最も差の小さいものを採用すれば良い – この方法だと、満点は間に合わない • 満点解法は、何か工夫する必要がある – 工夫の仕方は色々 • Bitを利用した桁DP • 貪欲法 • 条件を決めて全探索 2014/10/06 17 D問題 アルゴリズム • Bitを利用した桁ごとの動的計画法 – 「どの数字を使ったか」というデータは、1つの数字に付き、 「使った」「使ってない」の2通りなので、10進法では2^10 • 1024通りしか存在しない – 「どの数字を使っている時に」「目標としている数字を越え ているか否か」を状態とし、それらの最大値・最小値を更 新していく • 状態は、1024 * 2 * 2通りしか存在せず、遷移は10通り • 計算量は十分間に合う • 桁DPに慣れていれば無難な回答だが、慣れていな いとイメージがつかみにくい 2014/10/06 18 D問題 アルゴリズム • 条件を決めて全探索する方法 • 今回の問題の制約上、以下のようなことが解る – 出来るだけ左の桁は一致させたい • 右の方の桁は、間違えていても大きな違いにならない – 右の方の桁は、「最大値」や「最小値」を目指すことになる ため、同じ数字しか使わない • よって、以下のような処理を行えば良い – 左からP桁目までは、整数Aと同じにする – 左からP+1桁目の桁をQにする – 左からP+2桁目以降の桁をRにする – この、P,Q,Rについて全探索を行えば良い 2014/10/06 19 D問題 アルゴリズム • 貪欲法 – そもそも、組み合わせを何通りも試す必要があるのか？ • 実はそんなことはない！ – 「A以上の数のうち、入力できる最小のもの」 – 「A以下の数のうち、入力できる最大のもの」 – この2パターンを求めてあげれば良い！ • これらは、貪欲法で求めることが出来る！ 2014/10/06 20 D問題 アルゴリズム • どのように貪欲法を用いるか？ – 上の桁から決めていくにしても、決め方が難しい • 特定の数字を置ける、置けない、の判定が難しい – 最も簡単なのは、深さ優先探索を用いた手法 • 置けるかわからないのであれば、とりあえず置いてみる • 置いた結果、先の結果で破綻したら、違う数字を置きなおす • 再帰的に処理するので、連続して破綻していても大丈夫 – 計算量は？ • 余程変な実装をしなければ大丈夫！ 2014/10/06 21
© Copyright 2024 ExpyDoc
