だんだん、「これ昔やった問題に似ているな」となることが増えてきました。進研ゼミの「これ進研ゼミでやった問題だ！」というのはこういう状態なのでしょうか。
1.ABC131C
キーワード:整数問題,最大公約数,最小公倍数
ある範囲内の整数Cでも整数Dでも割り切れない整数の個数を求める問題です。
CでもDでも割り切れないというところで、最小公倍数を使うというのがわかります。なのでとりあえずCとDの最小公倍数を求めます。
次に、1~Bまでの中でCでもDでも割り切れない数の個数を数えます。真面目に数えるとTLEするので、数学AでやったA∨Bのベン図を思い浮かべると良さそうです。全体集合{1,2,…,B}の要素の個数からCで割り切れる数の個数(B/C)とDで割り切れる数の個数(B/D)を引いて、CとDの最小公倍数で割り切れる数の個数(B/lcm(C,D))を足し合わせます。これをcountBとします。
更に、1~A-1までの中でもCでもDでも割り切れない数の個数を数えます。計算はさっきと同じです。これをcountAとします。
最後に、countBとcountAの差を出力して終わりです。
最初、真面目にA~Bの間の数を、みたいなことをやってWAを出しました。そういえば、範囲内の条件を満たす要素の個数の問題で、２つの範囲を考えてあげて、その差を求めるという問題を数学Aでやりましたね。忘れてました。
実装では最小公倍数を求めることが必要です。C++17からgcdとlcmが関数として追加されたので、どちらの関数も自分で実装せずに使うことができますが、この問題でコードを提出する場合、C++14しか対応していないのでgcdとlcmを自分で実装する必要があります。まあ、これも勉強じゃ。
2.ABC109C
問題:C – Skip
キーワード:一次元,移動,最大値,最小公約数
ある座標Xから出発して、1回の移動でDだけ前か後ろに進めるという条件のもとで、全ての都市を訪ねることができるDの最大値を求めよという問題。
これも提出する時はC++14までだったので、gcdとlcmは自力で実装する必要がありました。簡単に実装できるので別にいいかなあとは思いますが。
さて、とりあえず訪れるべき都市の座標をvectorに取ってsortします。この時、vectorには出発する座標であるXも入れておきます。そうすると、Xから出発するということを考えなくてもよくなり、単純に前から考えられるようになります。これは、結局Xは最初に訪れた都市とみなせば、訪れるべき都市とも捉えることができるからです。
後は、vectorの前から要素間の差の最小公約数を求めてあげるとDの最大値が求まります。また、訪れるべき都市とXは一致しないと制約条件にあるので、これは考えなくてもOKです。
最小公約数を求める理由としては、この問題では移動距離Dでしか移動できず、Dは一定なので一度通り過ぎた都市はどうやっても戻ってきて到達することはできません。したがって、隣の都市との距離をDの倍数で表せるかという問題に帰着し、Dの最大値とは都市間の距離の最小公約数であるとわかります。また訪れる順番で、訪れることが可能な都市は変化しないので、前から順番に差を出していくことが可能です。
実装でちょっと面倒だなと思ったのは、最小公約数の初期値です。今思えば、最初の都市間距離を最小公約数の初期値に設定してやればよかったと思います。問題を解いてたときは律儀に、"0番目と1番目の都市の距離"と"1番目の都市と2番目の都市の距離"の最小公約数を初期値にしていました。
3.ABC116C
キーワード:操作,最小回数,sort不可
ある範囲の花の高さを1高くするという操作を繰り返して、全ての花の高さを等しくする問題。詳しい証明は解説にあります。
さて、高さを揃えるのはめんどくさいので、逆に高さを1減らすことを考えます。そしてイメージするのは複数のダルマ落としを一気に1段落としていく遊びです。
1操作で複数のダルマ落としの高さを1低くすることができます。なので、全てのだるまの高さが1以上ならば、最初から最後までのダルマを指定して操作を行えます。しかし、途中に高さ0のダルマがあると、それ以前の範囲に対してしか操作が行なえません。(高さがマイナスのダルマは存在しないため)
つまり、高さ0の花がないならば、最初から最後までを一括で操作が行え、途中で高さが0の花があるならば範囲を区切って操作をする必要があるということです。
例えば、花の高さを{1,2,3,1,2}とすれば、花の高さの遷移は、{1,2,3,1,2}→(全体に操作)→{0,1,2,0,1}→(2~3番目と5番目に操作)→{0,0,1,0,0}→(3番目に操作)→{0,0,0,0,0}となります。
次に、どうやって範囲を区切るかといえば、高さ0の花が出て、以前に高さ0でない花があったならば操作を行うという実装を私はやりました。高さ0でない花があったというのは今まで出てきた最小値を更新し、最小値が初期値と異なっているかどうかで判定しました。
多分この最小値を使うともっと高速に求められた気がするのですが、要素数が100程度、高さも最大100で十分間に合うと思ったので、1ずつ削るように実装しました。
さらに言えば、ループを抜ける判定を、高さの和を求めることで行っているので、毎回100要素を足し合わせるのは無駄かなあと思いましたが、いい方法が思いつきませんでした。
無限ループを書くのは勇気がいるけど、
while(sum!=0){}
って書けばよかったのでは？と今思いました。
4.ABC117C
キーワード:ゲーム,一次元,移動,最小回数
再び、与えられた全ての地点を訪ねる問題です。ABC109C問題と違うのはスタートは自分で決められる点です。
・・・と思ったらこれすでに解いていました。なぜか計算用紙に書かれていたのでここまで書いたのですが。
そういうわけで、ABC117C問題を解いた時のはこちらになります。
5.みんなのプロコン2019 C問題
キーワード:操作,規定回数,最大化
整理して考えれば難しくない問題でした。
最初に考えるのは、交換しない方が得か、交換する方が得かということです。交換する場合は2回の操作を消費してビスケットを増やします。つまり、2回の操作で交換しない場合に増えるビスケットの数(2枚)と、日本円に交換して再度ビスケットに交換したときのビスケットの差枚を比較し、後者の方が多い場合は交換を行います。この差枚は一定なので、差枚≧2ならば交換することにします。これで最終的なビスケットの枚数を最大化できました。
次にビスケットの枚数を求めます。
交換しない場合のビスケットの枚数を求めるのは、K回の操作でK枚増えるので1+K枚を出力して終わりです。
交換する場合は、ビスケットの枚数の初期値は1枚であり、日本円に交換可能な枚数がa枚からなので、aが1でない場合は手持ちのビスケットをa枚まで増やす必要もあります。さらに、残り操作回数Kが奇数の場合は、最後に日本円をビスケットに戻す操作ができないため、このときはビスケットを叩いて1枚増やす操作を行う必要があります。
私が最初に実装した時、問題文を読み間違えてA枚を1円に交換できるのだから、n×A枚ならばn円に交換できると思っていました。この場合は入力例1から合わないので、そういう残念なコードを提出しないで済んだのは幸いでした。
6.おわりに
C++17では競プロでつかうことが関数で用意されているので、自分で実装しなくていいって思ってましたが、そういう関数があろうがなかろうが、どういうアルゴリズムで実装できるかぐらいは覚えてないとダメだなと思いました。
memo:最小公約数はユークリッドの互除法で実装できます。