おーじのゆるゆる精進日記
前書き～
自分に変化を与えさらなるレート向上を図るため、解法の整理や何がダメだったかを言葉にするという目的から精進日記をつけることにしました.
緩いです(多分)
チップ・ストーリー ～白銀編～
感想
コンテスト中に解けなかったのでとても悲しかった.
解法は出ていたが数学ができず...
問題概要
100 × 100 のマスにP[i] × Q[j]を入れる.
PとQは何通りかな？
解法
Nが100000以下であることからO(N)ができることに気づく.
ここで数列Pの最大値maxPを回すことができる.
この時maxQはN / maxPとなる.
後はこれが何通りあるかを下記の式で求めます.
(maxP^10 - (maxP - 1)^10) × maxQ^10
注意点
maxP^10 - (maxP - 1)^10の計算の際に負の世界に突っ込んでしまうことがある.
その時はMODを足しといて余りを取ろう！
以上です～(ドワンゴのB問題も書こうかな)
