精進メモ 2021/06/14~
久々にきちんと月曜に記事を作成した気がします。
Binary Trie
ARC122のDで貼るだけと言われたので早速作成です。
Trie木はいままでフルスクラッチで書く派だった上、BinaryTrieの問題をそこまで解いたことがない気がする？ので、どのような構成にすればいいのかあんまりわからずです…
https://judge.yosupo.jp/submission/50358
ZONeエナジー プログラミングコンテスト “HELLO SPACE” F - 出会いと別れ
提出
なんでコンテスト中解けなかったのかびっくりするくらいシンプルですね。AtCoder Problemsをなんとなく開いたら、黄diffでACしていなかったのがこの問題だけだったので、久々に典型90以外での精進です。
基底を取ると、その部分集合の総xorが、"可能な辺を張った場合に"から行ける場所になります。
基底を取る時、その元となった値を記録しておき、それらと、のxorを取ってUnionFindで全域木を作成していけば良いです。辺が
本になっていれば成功です。
を、
にして1ペナです。
典型90
066 - Various Arrays（★5）
となる
すべてについて、ありうるパターンを全部試せばよいです。
それぞれで転倒数が1加算される確率を求め、その和を取れば答えです。
067 - Base 8 to 9（★2）
素直に8進数を10進数に直し、それを9進数に直す方法を取ります。
になるパターンで2ペナしました…
068 - Paired Information（★5）
なので、
の偶奇どちらか一方の場合は
を
倍します。
すると、BITで管理して区間和取れば答え求められます。
いろいろバグらせて2ペナしました。
069 - Colorful Blocks 2（★3）
が答えです。
が2と1の場合はそれぞれ
になるので注意です。
070 - Plant Planning（★4）
X,Y座標独立に考えることができます。
選ぶべき点は中央値です(偶数の場合はどちらでもいいです)。
あとは愚直に計算します。
071 - Fuzzy Priority（★7）
1ペナ。
素直にDFSをすればよいです。今使える頂点のリストをセットで持っておき、その中から1つ選んで次に進みます。
ABC 206
途中まで1ページ目ワンチャンあるなぁと思っていましたがさすがに最後は順位が落ちました。
D - KAIBUNsyo
これDにあるの結構びっくりしました(まぁ解法的にEにおけるかと言われると…？)。
前から番目と後ろから
番目の文字を辺で繋ぐことを考えます。
連結成分については、最終的に全て同じ文字になっている必要があります。
すると、最低でも(連結成分 - 1)回操作をすると、その連結成分の文字を揃える必要があります。なので、それぞれの(連結成分 -1)を足したものが答えになります。
E - Divide Both
脳みそ破壊されるシリーズです。
をまず固定します。
このとき、と
の公約数が
となっているような
の選び方は包除原理で求めることができます。
欲しいのはのパターン数です。
が大きい方から計算していくと楽に計算できます。
そして、このときにのどちらかが1になっているものを引きます。
あとはこれを全てのについて求めればよいです。
F - Interval Game 2
知識ゲーと典型を組み合わせているので、こちらの方がサクっと解けました。面白かったです。
ある区間が残っているとき、選べる区間は最初から決まっています。
それぞれの区間を選んだ時のグランディ数を求めることができれば、今見ている区間についてのグランディ数も求めることができます。
選ぶ区間を一つ決めたとき、今見ている区間は2つ(1つの場合もありますが)に分かれます。
それぞれについて、次のターンからは好きな方を選べるので、分けた区間それぞれのグランディ数を求め、そのxorを考えます。これが、今選んだ区間についての遷移先のグランディ数になります。
あとは、それを選べる区間それぞれについて求めれば、定義通り計算できます。
グランディ数 + 区間DPです。
精進メモ 2021/06/07~
最近暑いです。
競プロ典型 90 問
060 - Chimera（★5）
右からと左からでLISを求めていけばいいです。
LIS(典型) + 左右からみる(典型)で割と好きです。
061 - Deck（★2）
vectorを二本持ちました。
添え字に脳みそをやられて時間がかかりましたがなんとかノーペナです。
062 - Paint All（★6）
から
、
に辺をはると、BFSで解くことができます。
となっている頂点群を始点とすればいいです。
063 - Monochromatic Subgrid（★4）
選ぶ行をビット全探索します。チェックやカウントは愚直でいいです。
063 - Monochromatic Subgrid（★4）
階差を取って差分更新です。
ARC122
Dが間に合わなくて悔しいです。Eも見ておくべきでした。
A - Many Formulae
ある値について正負を決めた時、右と左のパターン数をかけてあげればよいです。パターン数はDPで計算できます。
B - Insurance
を全探索すればいいです。
中途半端なについてはどちらかに寄せると値が小さくなります。
C - Calculator
操作3,4を繰り返すと出現する値はフィボナッチになります。
途中で操作1,2を割り込ませて、その操作に対する寄与をうまく考えればいいです。
D - XOR Game
大きいビットから貪欲に、再帰的に決めていけばいいです。
一番上のビットが0,1それぞれ偶数であった場合、それぞれのグループの同士で組み合わせにしたときの最大値が答えです。
そうでない場合、0のものと1のものをペアにしたものの最小値が答えです。
この後は、2つのグループを持ちながら再帰的に解きます。
このパートも、ほぼ似たようなことをすればいいです。
E - Increasing LCMs
後ろからみて問題無いです。今残っている要素について、
を満たすがあれば、選択できます。
これを繰り返せばよいです。
典型90問 065 - RGB Balls 2（★7）
赤と緑で個以下は、青が
個以上、という条件と同値です。
全てこれを適用すると、三色それぞれが一定の個数以上で、合計個選ぶようなパターン数を求める問題になります。
これは二項係数 + NTTで解くことができます。
同値条件の言い換え、明後日の方向に行っていました…
ABC205
久々に成功しました。
C - POW
が奇数なら1、偶数なら2に置き換えればいいです。
あとは素直に累乗して比較です。
無限場合分けが実は必要ないので好きです。
D - Kth Excluded
にぶたんで答えを求めます。
判定部分でもにぶたんをします。境界を丁寧に詰めないと破滅します。
E - White and Black Balls
カタラン数を知っていると、「カタラン数 折り返し」でググると本質が出てきます。
手元でうんうんうなっていると、が答えということがわかります。
そもそも答えが0になるケースを除外し忘れないようにしましょう(1ペナ)
F - Grid and Tokens
ソース -> 行 -> 駒 -> 駒 -> 列 -> シンク
としてマッチングをします。
精進メモ 2021/05/31~
もう6月です。気分はまだ2020年の春休み。
競プロ典型 90 問
048 - I will not drop out（★3）
部分点と、満点部分を分解してソート、貪欲に取って終了です。
049 - Flip Digits 2（★6）
をコスト
で結ぶ辺として最小全域木です。
難しいですね…
050 - Stair Jump（★3）
すなおにDPします。遷移は2パターンです。
051 - Typical Shop（★5）
半分全列挙して、候補を二分探索で求めていきます。
052 - Dice Product（★3）
式変形すると、それぞれのダイスの和を求め、その総積を計算すればOKです。
054 - Takahashi Number（★6）
論文から著者、著者から論文に辺を張ってBFSすればOKです。
055 - Select 5（★2）
枝刈りして全探索です。積を和だと思ってペナを出しました。
056 - Lucky Bag（★5）
頑張ってDPの復元をします。
個福袋を買い終えて、総和が
円になるとき、最後に買った福袋の種類
と定義して遷移をしていけばOKです。
ABC203 F - Weed
提出
高橋君の操作が回で収まるのがポイントでした。この手のポイントに気づくのが苦手です…
高橋君が
回操作をして、
までの草を抜き終えたとき、必要な青木君の操作回数
とすると、が
以下になっているような
の最小値が答えです。
遷移は、青木君が操作をするのが
です。
高橋君が操作をするのが、
番目の草を抜いたときに同時に抜くことのできる草のidの最小値
として、
です。
HUPC2016(RUPCセット)
チーム練でした。
C: 成長する点
点と直線、点と点の距離公式を使って頑張る問題です。
距離の最小値を配列でメモしておき、で候補を探せばよい…です。コンテスト中は見落としていました。
競プロを始めたばかりの後輩に押し付けて良い問題ではないです。
D: Complex Oracle
のクエリを
回飛ばすと、左側から順に値が確定していきます。
まだ選んでいない数の中で、転倒数の差分 + 1番目に小さいものになります。
E: Arai's
二部マッチングを素直にします。面談回数をコストにして辺を張り、容量を1ずつ流していきます。
を超えないコストの中で流せたフローが答えです。
F: きっちり
数列を半分で折りたたみ、差分を考えます。前半パートは正、後半パートは負として考えると、判定条件は、の長さの数列について、全ての要素が0になっていることです。
区間加算を行い、セグ木で数列の最大と最小がどちらも0になっていればOKです。
G: 運命力
4秒前の状態まで持って、の行列累乗です。
シャッフルの遷移3パターンは頑張ります。
典型90 053 - Discrete Dowsing（★7）
黄金分割探索です。
切り捨てる範囲を、...8,5,3,2,1とフィボナッチ数列にしていくように、数列の長さをうまく決めると良いらしいです。
これなら、誤差を気にする必要がありません(1500より大きい部分については適当に-1が入っていると考えればいいです)。
ABC204
Eの考察にハマりました。
もう少し早くできたと思います、悔しい。
C - Tour
CにBFS,DFSってありましたっけ…
驚きながら実装しました。
D - Cooking
オーブン1を使う料理を決めると、オーブン2を使う料理は自動的に決まります。総和から、オーブン1を使う料理分ひくだけです。
までの料理を決めて、片割れのグループの時間が
となるようにできるかどうか
とすると、まで決めて、
が作成できるとき、
の最小値が答えです。
E - Rush Hour 2
想定解がわかりません。
秒に
の辺を通ると、
秒に目的地に着くのですから、これを微分してあげると、だいたい
になっていればいいことがわかるので、この周辺で辺の移動を開始するパターンを探索してあげます(すでに
が大きければ、そのまま直で移動)。
あとはダイクストラです。
F - Hanjo 2
今最後に見た列の状態が、となっているようなパターン、として、遷移を行列にし、DPを行列累乗で解きます。
ビット全探索を行って、1 × 2を縦に置くパターン、横に置くパターン、一つ前の状態、の3つをループして遷移行列を書きました。
精進メモ 2021/05/24~
気づいたらもう土曜日です。おかしいですね…
ARC121
橙パフォを1カ月ぶりに出しました。だんだん出るようにはなっている気がします。
A - 2nd Greatest Distance
X, Y座標それぞれで大きいものと小さいものを2つずつくらいとってきて、全探索すればOKです。
念のため余裕を持って4つずつくらいとりました。
B - RGB Matching
RGBの偶奇は、000か011を並び替えたものの2択です。
前者は明らかに答えが0です。
後者は、11の中で一番値が小さくなるペアを選びます。このパターンだけ考慮してペナを吐くまでが1セットです。
Rが0、GBが1としたとき、RGとRBでそれぞれペアを作るパターンも存在します。
例えば、Rが[1,10], Gが[1]、Bが[10]のときです。
このパターンでは、RGとGBそれぞれで、一番値が小さくなるようなペアを選べばよいです。
もしRが同じ犬🐶になった場合、GBペアを直接選んだ場合が最適解になるので、特に問題はありません。
値をとすると、
のときは最適解が同じになります。
の場合はGBペアを選んだ方が最適になります(逆サイドも同様)。
C - Odd Even Sort
転倒している部分で選べる箇所があればそれを選択、なければのどちらかを適宜選択すれば間に合うらしいです。
E - Directed Tree
ある頂点が違反するには、
の子の部分木の頂点とペアにする必要があります。
違反しない方を考えると、親だけでなく、別の枝についても考慮しないといけないため大変です。
を頂点とする部分木について考えた時、少なくとも
個違反する頂点があるような、違反するペアの選び方
とすると、これはNTTです(オーダーが悪くなりますが楽です)。
順列のパターン数にするには、木の根の部分のを計算した後、残った個数分階乗をかければいいです。
あとは、の個数で正負をわけ、包除原理に落とし込むと答えが求まります。
ABC203
Fみたいな問題に気づくのすごい苦手です…(今回は謎の嘘解法に走っていました、久々にやらかした気がします)
D - Pond
感覚がマヒしていますが、冷静になるとこの位置にある割に難しいですね。
中央値の最小値は、二分探索をすると見通しがよくなります。
ある以下にできるかどうか、を考えると、
は
以下であるかどうか、0,1の二択にすることができます。
の領域の中で、1の個数が半数以上になっていればいいです。
二次元累積和を頑張って書けばOKです。
E - White Pawn
にたどり着くことができるかどうか、を考えます。
すると、これはシンプルなDPで書くことができます。
遷移は、1つ前の行のみが必要なので、配列のサイズをに抑えることができます。
さらに、1行上の値から違う値に更新されうるのは、たかだか黒いポーンがある列と、その左右にです。なので、その部分だけ愚直に更新するようにすればいいです。これで、配列サイズをにおさえて一次元で書けるようになりました。
今回、は大きいので、mapなんかを用いた座標圧縮を行ってあげれば、サイズが
に抑えられます。
精進メモ 2021/05/17~
圧倒的睡眠不足になりました。毎日10時間は寝たいです。
競プロ典型 90 問
042 - Multiple of 9（★4）
最終的に作成した数が9の倍数になるかどうかは、が9の倍数かどうかで決まります。
が小さいので、
桁和が
になるような数のパターン
としてDPできます。
043 - Maze Challenge with Lack of Sleep（★4）
一つ前は縦、横どっちから来たか、を添え字に持ってDPです。
01BFSになります。
045 - Simple Grouping（★6）
ある集合に対して部分集合を列挙するのを高速にすると、任意の集合に対して部分集合を走査するのがで収まるテクを使います。
グループ数と、既に決めた点の集合を持ったDPです。
046 - I Love 46（★3）
modでまとめて、個数の配列に直すテクを使います。
あとは雑に3重ループでも大丈夫です。
047 - Monochromatic Diagonal（★7）
対角線は、縦のprefixと横のsuffix、もしくはその逆で長さが同じものを列挙するのと同じです。
縦のprefixに対して、それを用いた対角線が最終的にある色になると決め打つと、横のsuffixが満たすべき文字列は一意に定まります。
満たすべき文字列は、一番長い対角線上に対するものさえ求めておけば、あとは連続部分文字列になります。
連続部分文字列と、横のpre(suf)fixの一致はローリングハッシュを使えばOKです。これを全ての色に対してチェックします。
ABC202
D - aab aba baa
パスカルの三角形を利用して、を求めておけば、前から決まっていきます。
a , b がそれぞれ個のとき、
を満たしていれば、
a を選べばよいです。、もしくは上の条件を満たさない時は
b を選びます。
E - Count Descendants
すごい好きです。
オイラーツアーをします。というクエリがあった際、オイラーツアー中に
に入ったタイミングで、(それまでに通った、根から距離
の頂点の個数)を引きます。
から出るタイミングで、(それまでに通った、根から距離
の頂点の個数)を足します。すると、
に対する答えが求まっています。
は
パターンしかないですから、クエリを先読みし、1回のDFSで上記の計算を全部やってしまえば間に合います。
オイラーツアーとは言いましたが、オイラーツアーのライブラリは全く必要ない(ただDFSするだけ)ので、実装も軽いです。他のいろいろなライブラリを使う必要もありませんでした。
ARC120
A,C,Dの速度は良かったのですが、Bで詰まりすぎました。
A - Max Add
まず、の最大値が
回足されます。
あとは、が
に対して足されます。
あとは、足される数の総和を、前から累積和を取りつつ計算していけば良いです。
B - Uniformly Distributed
まわりが全員通していたのですごい焦りました。
左下から右上に線を引いていくと、その斜線上で色が統一されていなければなりません。
あとは、そこで違う色が含まれていたら0、そうでなければ、全て色が決まっていない個数に対して
が答えです。
RやBと.が混在していても2倍をしていて、ペナを出しました。
C - Swaps 2
と置き換えます。
も同様です。
こうすると、与えられた操作は隣接2点のswapです。
数列の要素が異なる場合-1です。
それ以外の場合、転倒数を求める問題に帰着できます。
D - Bracket Score 2
上から番目に大きい値までに
+、そうでない方に -を割り振るよう、括弧列を作れば理論値になります。
先頭は ( にしなければならないため、 (とします。その際、+ と- どちらだったかをメモします。
それ以降、閉じカッコが対応していない開き括弧が存在する限り、メモした符号と同じであれば (を追加し、そうでなければ)を追加して開き括弧を一つ消します。
対応していない開き括弧がなくなったら、最初の操作に戻ります。
これを繰り返すだけで理論値に対応する括弧列が作成できます。
一か所だけ配列サイズを間違えてにしてしまい、1ペナしました。
精進メモ 2021/05/10~
もう金曜日ですね。
ReoNaさんのニューシングルカップリング、いいです。
ReoNa 『まっさら』-Music Video- - YouTube
ReoNa 『あしたはハレルヤ』-Lyric Video- - YouTube
ReoNa 『生きてるだけでえらいよ』-Lyric Video- - YouTube
- 典型90 036 - Max Manhattan Distance（★5）
- 典型90 037 - Don't Leave the Spice（★5）
- 典型90 039 - Tree Distance（★5）
- 典型90 040 - Get More Money（★7）
- 典型 041 - Piles in AtCoder Farm（★7）
- GCJ
- ABC201
- ARC119
典型90 036 - Max Manhattan Distance（★5）
+-全探索です。
が
なので、
は
になります。
あとはここに、と
を当てはめれば良いです。回転もいりません。最近ARCで見ました。
典型90 037 - Don't Leave the Spice（★5）
DPをセグ木で更新すれば良いです。
番目の香辛料までみて、使った量が
になるような組み合わせの中での価値最大、とします。
もらうDPを考えると、遷移元の量がの区間になっているので、セグ木で最大値を取り出せばいいです。
典型90 039 - Tree Distance（★5）
寄与を考えるいつものです。頂点1を根とする木を考えます。
頂点を根とする部分木のサイズを
とすると、
とその親を繋ぐ辺が使われる回数は、
になります。
よって、木DPで部分木のサイズを求めれば答えを求めることができます。
典型90 040 - Get More Money（★7）
†燃やす埋める†
典型 041 - Piles in AtCoder Farm（★7）
凸包を作り、辺それぞれに対して、辺以下にある格子点をfloor_sumで計算し、上側の個数から下側の個数を引き、最後に下側の辺上の点を足します。
縦に直線になっているパターンに注意。
GCJ
ついにRound 2突破しました！！！！競プロを始めた時からの夢だったので、とても嬉しいです。その日は興奮してなかなか眠れませんでした。
A:ぐっとにらむと毎回全体の最小値選ぶだけ
B:最小でXを使うと、(N-X)/Xで同じ問題に帰着できる、初手だけ3以上なのが注意
C:セグ木 + コンビネーションで再帰的にやる
d:フロー
とツイートに書いてあります。内容はもう忘れました。
B,Cは面白かったという記憶だけ残っています。
ABC201
Eで苦しみました。
D - Game in Momotetsu World
MinMaxの素直なDPです。
頭がこんがらがりやすいので、丁寧にやりました。
E - Xor Distances
bitごとにやります。
木DPで、今見ている頂点からどこかの子へのパスと、子同士のパス、の2つに分けて数え上げていきます。
自身の子から
へのパスで、今見ているbitのxorが
になるようなもののパターン数
をがんばって数えます。
60回DFSをするとTLEしますが、頑張って定数倍高速化しました。
F - Insertion Sort
については、
とのminを取ることで、右端と左端に送る操作をした時のコストが決まります。
( )(いじらない or
消費)(
)
という3パターンに分かれます。
左右は累積和を取ることで簡単に求められます。
真ん中は、いじらないと決めた値があったら、つぎにいじらない選択肢を選べる
は、元の順列で
以降にある値です。
ということで、
元の順列で
番目の値を最後にいじらないとしたとき、
個の要素を並べ終えた段階におけるコストの最小値
とすると、をインデックスにもつ遅延セグ木によって高速化できます。
ARC119
D,Eは難しくて現時点だと解ききるのが難しいです。
A - 119 × 223 + 1
については、
を決めた上で残った値を使えばいいので無視してかまいません。
を固定すると、これは60通りくらいにしかなりません。
が一番大きくなるには、
を
で割り切り捨てた値を選べばいいです。
あとは、余った値をにして計算し、全探索します。
B - Electric Board
まずは問題文を丁寧に読みます。
0の個数は変化しないので、個数が違っていたらそもそも -1 です。
結局、0の位置は一回の操作で、"最も近い0を超えない範囲で"自由に入れ替えることができます。なので、一番左側から揃えていくしかありません。よって、に含まれる
番目の0の位置が異なっているような
の個数が答えになります。
C - ARC Wrecker 2
判定を一回行うだけなら、左側から貪欲に0になるよう調整していけば良いです。
このとき、として、次に
を計算し、次はこの値を
から引き…
と、よく見ると毎回正負を入れ替えて引いていることになります。
この手の問題は、を先に、+-+-...としてしまえば上手く計算できます。
ということで、奇数番目は、偶数番目は
として累積和を取っていくと、累積和が0となるような区間の個数を求める問題になります。
これはzero sum rangesという問題で有名な解き方で、からの累積和の値に対する個数をmapで管理し、現時点での累積和と同じ値のmapの要素を参照して答えに加算していけば良いです。
精進メモ 2021/05/03~
最近は少しだけ忙しくて典型を埋めるので精いっぱいです(モンハンをしながら)
典型90 029 - Long Bricks（★5）
遅延セグ木で殴ります。
が与えられた際に、その区間の最大値を取得し、値 + 1を計算すれば答えです。
区間に対して、計算した値で再び更新することも忘れないようにすればOKです。
典型90 030 - K Factors（★5）
迷走して結構悩みました。
エラトステネスの篩と同じ感覚で、素因数の種類をカウントすれば間に合います。
典型90 031 - VS AtCoder（★6）
5乗オーダーが通ることを信じて投げると通ります。
4乗ってツイートを見かけた気がするのですがわからず…
については何も気にしなくてよくて、1つあたりのゲームのグランディ数がわかればxorをとっておしまいです。
は最大50、
が最大1325になります。ありうる
の組み合わせについて、グランディ数を求めれば良いです。
素直に遷移先のグランディ数を求め、そこに含まれない最小の整数を計算します。
状態が3乗分で、遷移はを減らすパターンが2乗分かかります。
ABC200
いまいちでした。Dでペナ出したのでEで落ち着こうと思ったのですが、Eももたつきました。
Fも間に合わず、コンテストが終わってかなり時間が経ってからの
のACになったので悔しいです。
D - Happy Birthday! 2
DPでごり押しです。
番目の値まで見て、総和
が
になるような組み合わせがある場合、最後に使用するID
として更新していくと、遷移先に既にIDが書かれていた場合、経路が二つあるので、答えが決まります。
復元を頑張ると通ります。コーナーっぽいケースに阻まれペナを出しました。
E - Patisserie ABC 2
に直して解き、最後に1足しました。
まずは総和を決め打ちます。
総和が0のパターンから順番にどれくらいあるか数えていきます。
Python/Ruby/PHP/Golang(Go)で上限のある重複組み合わせ - Qiita
こんな感じで包除すれば良いです。上記の記事は、最低1使う、としているので要注意です。コンビネーション部分は愚直ループで計算すれば良いです。ここがです。
総和が決まると、次は1つめの要素を決めます。
こちらも、を小さい方から見ていけば良いです。パターン数は上記と同様です。ここも
です。
1つ目の要素が決まると、あとは2番目の要素を決めたら3番目の要素が自動的に決まるので、2番目の要素を小さい方から順番に試していけば良いです。これもです。
ということで、一つ一つ決めていけば答えを出すことができます。
F - Minflip Summation
左端が1の場合、 10となっているような箇所を数えれば答えになります。左端が0の場合はその逆です。
と言うことで、左端を01の二通り試します。
10となっている箇所のカウントは、通り試して、
倍すればだいたいOKです。 先頭を最初に決め打っているので、その周辺だけ丁寧に場合分けをする必要があります。
それ以外は、2の、01以外の部分の?の個数乗を計算すればOKです。
のパターンもコーナーケースになりやすいので気を付けましょう。
ARC118
A問題で詰まりました。
A - Tax Included Price
↓の問題と同じ感じで、ある値までに、1つ飛ばしになった数字の個数が割り算で求められます。
なので、それを二分探索すれば、答えを知ることができます。
F - Modularness
B - Village of M People
maxminは二分探索、
は
にバラして最大値を求めても問題ない、
定数倍してもmaxの結果は変わらない、
の区間でそれぞれ選んで
にできるかどうかは
で判定、
と、典型を組み合わせていけば自然と解法が出てきました。
組み合わせの分、実装は少し大変だったかもしれませんが、丁寧にノートに書いていたのでなんとかなりました。
C - Coprime Set
↓の問題を解いていたので、この問題の解法はすぐに思いつきました。6,10,15の倍数で10000以下のものをひたすら詰めていけば良いです。
