高橋カレンダーの問題
第一回日本最強プログラマー学生選手権-予選-、A問題、高橋カレンダー。問題文、今日は8月24日、年に5日しかない世紀の日です。
Dが2桁の整数で、Dの1の位をD1、10の位をD10とした時に、M、D1、D10がすべての、次の条件をすべて満たす場合、M月D日を世紀の日と呼びます。
D1大なりイコール2、D10大なりイコール2、D1×D10イコールM。高橋くんはこの日をもっと増やしたいと考え、1年が1月からM月までの合計Mか月、どの月も1日からD日までの合計D日からなる高橋歴を誕生させました。
高橋歴において、世紀の日は年に何日あるでしょうか。
世紀の日。 Dが2桁の整数で、1の位をD、1の位×10の位。
Dが2桁の整数、M月D日、だから、
10日から、ってことですね。
どう? 入力がMとDが与えられます。入力例1は15と40、出力例は10。
年に訪れる世紀の日は次の10日間です。 最大Mが100、Dが99だから、
M解法文の中で、
D解法文を回せばいいかな。 1回ちょっと入力例1で組んでみましょうか。
MとDイコールマップ、インとインプット、
ドットスプリット、フォー、アイ、イン、レンジ、
1からMプラス1までかな。 1以上100以下。
の前にアンサーイコール0にしておいて、
4Mインレンジ、1からMプラス1まで。 4Dインレンジ、
1から2する? どうしようかな。
11からにしとこうか。 11から
Dプラス1まで。
DイコールSD、
D1とD10を作っておいて、イコール
STRのDの
0番目と、 違う、1番目か。
D1は1桁の方ですね。
STR、Dの
0番目がD10。
インとD1かける
D1かけるD10、インと
D10。 イコールイコールMだったら
アンサープラスイコール1。 最後プリントアンサーで
とりあえず見た感じこれで できそうな気はするんですが
標準入力は15と40で、 21が出てきたね。違うね。
じゃあ ここのif文のところで
プリント
MとDを出して
何月何日が引っかかっているかを確認。 1月11日。
Dが2桁の整数。
D1ダイナリイコール2か。
D10もダイナリイコール2だから22からだな。 22スタートですね、Dは。
11、1個多いな。 4月22から始まるけど
3月31日が引っかかってる。 31が引っかかってますね、これ。
じゃあ if D1イコールイコール1
or D2イコールイコール1だった場合
コンティニューしたらいいんじゃないかな。 エラーになった。
D2は入れてないや。D10ですね。 1、0、10、5
入力例2は5個。5個ですね。 入力例3が11なので0。
はい、OKそうなので提出しておきましょう。 プリントMDを消して
提出。2019年8月の大会ですね。 大会って言っていいのかな。
B問題-クリーンインバージョン
はい、ACしたのでB問題いきます。 B問題。クリーンインバージョン。
問題文。長さNの整数列A。 A0からAのN-1があります。
Aを軽快繰り返した長さK×Nの整数列をBとします。 例えばAイコール1、3、2、Kイコール2の時
Bイコール1、3、2、1、3、2です。 Bの点灯数を10の9乗プラス7で割った余りを求めてください。
ここでBの点灯数は整数の順序対IJ。 0小なりイコールI小なりJ小なりイコールK×N-1であって
BI大なりBJを満たすものの個数として定義されます。 点灯数についてちょっと調べてみましょうか。
自分より左にいるのに自分より大きい数の個数を足していった時の相和が点灯数。
個数…数じゃない…数じゃないわ。 その数そのものはカウントしなくていいんだな。
1、2、3、4、5の点灯数は0。 1、2、3、5、4の点灯数は1。 5、1、2、3、4の点灯数は4。
4。左にあるくせに大きいやんけ。 さてことか。
入力例1。 NKが2、2。 Aは2と1。出力例は3。このケースではBイコール2、1、2、1です。
B0大なりB1。B0大なりB3。 B2大なりB3。
あー、なるほど。 で、10の9乗個あるから
4分ではこれ間に合わない気がしますが、一旦愚直にやってみましょうか。 NとKが与えられ…
これなんか、わざわざBを作らなくてもいけそうな気はしますね。感覚的に。 Aイコールリスト
マップイントインプットロットスプリット。 で、Bイコール
A×K
プリントB。 うん、大丈夫ですね。
で、4iインレンジ
レン… まあいいか。レンB
一回やって 4jインレンジ
iプラス1から
レンBまで。で、if Bのi番目が
大なりBのjだったら
アンスプラスイコール1。で、アンスを一番最初に定義しておいて
プリントアンサー。 これが
パッと思いつく方法ですね。入力例1は3。 入力例2は0。0。
入力例3は…あ、そうか。 10の9乗プラス7で割った余りを出力することに注意してください。だから
アンスパーセント
10の9乗プラス7
はい、エラーが出ましたね。メモリエラー。Bを作るときにもう
アウトっぽいですね。Nが10、Kが 9982万。ちゃうわ。
9億9千80…ん? 9億9千8百24万4千353っていう
入力例が出てきたので、これはダメだねとなったわけで
1個目の
列で… なんか計算できそうですけどね。
1個目で作って、それを倍にして、0以上だったらプラス1してとかそういう
計算はどうだろう。いやーちょっと違うっぽいな。解説見ましょうか。
B問題。 Bを構成するK項のAを順にA1A2…AKとします。
Bの点灯数はあるAIの内部で発生するものと、AIとAJ、I≠Jの間で発生するものに分かれます。
前者の相和はAの点灯数にKをかけたものに等しく、Aの点灯数は愚直な全探索でオーダーNの2乗で求めることが可能です。
さっきやった20ループですね。後者の相和は2つのAの間で発生する点灯数にKこのものから2つを選ぶ
選び方。2分のK×K-1をかけたものに等しいです。 ここで2つのAの間で発生する点灯数はAの各要素についてそれより小さい要素が
Aにいくつ存在するかを調べることで求めることができます。 愚直に計算してもこれはオーダージョーの計算量で
実行可能です。以上より全体でオーダーN次乗の計算量でBの点灯数を計算することができます?
コード例も特にないのでちょっと他の定数例を見ておきましょうか。点灯数初めて聞いた概念ですね。
勉強しておきます。ではまた次回お疲れ様です。