2015-01-12

■ [CodeChef]January Challenge 2015 21:24 はてなブックマーク - January Challenge 2015 - TopCoderの学習のお時間


http://www.codechef.com/JAN15

2年ぶりくらいに参加した。

このコンテスト形式、マイペースに取り組めて良いので今後も出ようと思う。

Chef and Stones(CHEFSTON)


やる

http://www.codechef.com/viewsolution/5713322

Gcd Queries(GCDQ)


配列を前から見ていった累積GCDと後ろから見ていった累積GCDを覚えておく

http://www.codechef.com/viewsolution/5713655

Sereja and Votes(SEAVOTE)


取り得る和の上限と下限を求める

http://www.codechef.com/viewsolution/5713840

One Dimensional Kingdoms(ONEKING)


よくあるGreedy

最初、区間の開始・終了をオブジェクトとしてソートしていたらTLEした

座標の範囲が狭かったので座標をキーにしてソート無しでやった

http://www.codechef.com/viewsolution/5714255

Chef and A Large Permutation(CLPERM)


実装も知識も無く考察のみで解ける愉快な問題

存在するカードを昇順に並べた配列をBとする。

B_1〜B_n のカードを使って S=ΣB_i(1<=i<=n) までの全ての整数を表せるとすると、B_n+1 を考えると次のようになる

  • B_n+1 <= S+1 の場合
    • B_1〜B_n+1 のカードを使って ΣB_i(1<=i<=n+1) までの全ての整数を表せる
  • B_n+1 > S+1 の場合
    • S+1が表せない

これをそのままやるとO(N-K)だが、カードの数が連続している範囲をまとめて処理するとO(K)になる

http://www.codechef.com/viewsolution/5717846

Queries on the String(QSET)


count[x][y] := (文字列先頭からx文字目まで見たときの数値 % 3 == y) ? 1 : 0

上記の値をSegmentTreeで管理する

この問題が今回の中で一番難しかった気がする

http://www.codechef.com/viewsolution/5716782

Xor Queries(XRQRS)


永続SegmentTree

xor最大化やk-th smallestのクエリに対しては、上から1bitずつ決めていく

http://www.codechef.com/viewsolution/5867272

Sereja and LCM(SEALCM)


D（なぜかコード中ではUという名前にしてしまった）を素因数の冪に分解して、包除原理で補集合の要素数を求める

http://www.codechef.com/viewsolution/5872152

Ranka(RANKA)


白を下から埋めていく→黒を1つ置いて白を全滅させる

を繰り返す

黒が最後まで行ったらいったん黒を全滅させ、盤面を90度回転させた形で同様のことをやる

http://www.codechef.com/viewsolution/5873615

Sereja and Number Division 2(SEAND2:タイブレーク)


焼きなましただけ

ΣB の値が大きいケースに長く時間をかけるようにした

http://www.codechef.com/viewsolution/5729963

CodeChefではJavaはC++の2倍時間を使えるけど、有利なのかどうかはよくわからない

結果

  • 10問中10問AC
  • 14位/7943人

2014-12-01

■ [部活][MM] MarathonMatchトレーニングのための過去問レビュー 01:01 はてなブックマーク - MarathonMatchトレーニングのための過去問レビュー - TopCoderの学習のお時間


これは Competitive Programming Advent Calendar 2014 1日目の記事です。

MarathonMatchで成績を上げていくには、他のスポーツと同じく実践が不可欠だと思います。

しかし、最近は通常の（=TCO予選みたいな組み合わせ最適化を問う）MarathonMatchの開催回数が少ないのでなかなかその機会が得られません。

信じられないかもしれませんが、2008年ごろは月1回以上のペースでMarathonMatchが開催されていたんです…。

ならば過去の問題ストックを使って自主練するしかない！

ということで、過去に自分が参加したMarathonMatchについて、問題をジャンルわけしてコメントを付け、オススメ度を☆で表しています。

ジャンルわけは便宜上という側面が大きく、この方針ではないとダメ！　というわけではないです。

あと、ネタバレありなので要注意。

リンク先はPracticeの問題文です。

Practiceが存在しないものがいくつかあって、それらにはリンクを張っていません。

なお、Practiceにないものも含めて過去のMarathonMatchの一覧を見るには、Match Winners のページがよさそうです。

焼きなまし


ざっくりいえば焼きなましをするんだけど、もちろん焼きなましただけではだめで、その適用形態は多彩です。

  • TCO14 Round3 CollageMaker [☆☆☆]
    • そもそも、焼きなまし（というか、逐次的改善）可能な形にできたかどうかが上位との分かれ目といった感じでした
    • 解の探索以外でちょっと面倒な要素が多いので、練習するなら他の問題の方が良いかなぁ
  • TCO13 Round3 CirclesSeparation [☆☆☆]
    • 良い近傍の取り方がとても難しい
    • 僕は本番でまともな方法を実装できずに撃沈しました
  • Marathon Match 78 FixTheFence [☆☆☆☆☆]
    • 良い近傍の取り方が難しい
    • 問題としてはシンプルなので練習によさそう
    • ところで本番1位の人の解法は焼きなましではなく他の人たちと全然違う方針でした。かっこいい
  • TCO10 Round2 CellularAutomaton [☆☆]
    • 完全に高速化ゲー。高速化の訓練としては良いかもしれませんが…
  • TCO10 Round1 Planarity [☆☆]
    • これもかなり高速化ゲーの印象（12時間しかやってないけど）
  • Marathon Match 56 EnclosingCircles [☆☆☆☆]
    • よくMarathonMatchの問題例として取り上げられる、理解しやすい問題
    • 本番の結果は意外とばらけていて、焼きなましの職人芸スキルで差がついた、という印象
  • Marathon Match 54 TilesPuzzle [☆☆☆]
    • 本番で自分が焼きなましでやったのでここに入れましたが、forumを見る限りは焼きなましてる人は少数派っぽい
    • いろいろなヒューリスティック探索ができそう

ビームサーチ


最近ビームサーチばかりやってる気がするけど、挙げてみたら思っていたより少なかった。

  • TCO14 Round1 SquareRemover [☆☆☆]
    • 高速化寄り
    • アルゴリズムにやらせると、人力で遊んだ場合より遙かに良い点数を出すのが面白かった（どうでもいい）
  • TCO13 Round2 FragileMirrors [☆☆☆☆]
    • 良い評価関数を作ることがもちろん大切なんだけど、もっと重要な要素がひとつあって、それを見つけられないと勝負にならない感じだった
    • 問題の性質をよく考える訓練になって良い
  • TCO12 Round1 BlackAndWhiteGame [☆☆]
    • 探索が可能な形をつくるのが全く自明ではなくて大変
    • 正のスコアを出すまでちょっと遠いので練習としてやるにはつらいかもしれない

マルチエージェント系


複数のユニットを動かして、協調して何かやらせる問題。

実装が難しくなることが多いです。

  • TCO13 Final GatheringResources [☆☆☆]
    • 実装ゲーに近かったと思う
    • とはいえ12時間しかやっていないのでもっと時間かけたときにどうなるかは未知数かな
  • Marathon Match 55 CoalMining [☆☆☆]
    • あまり印象に残っていない…。オーソドックスな問題だったと思います

パターン決め系


良い解では全体がどのような形になるかを見出すことが最重要になる問題たち。

後はそのパターンの中で細かく探索をしたりする。

他人の解をビジュアライザで見ると面白いことが多い。

  • TCO14 Round2 RectanglesAndHoles [☆☆☆]
    • パターンを想定するまではできても、それを実装するのが難しい問題だったと思います
  • Marathon Match 74 AntiTravelingSalesperson [☆☆☆☆]
    • 格子点にしか置けないという制約がある中でうまいパターンを作るには、適当にやってもダメでよーく考えないといけない
    • これも1位の人は違った方針でやっていてかっこよかった
  • TCO09 Round2 Gearing [☆☆☆☆]
    • 逐次的な改善が可能な形でパターン決めてあげないと良いスコアにはならない
    • 本番に自分が参加したときは、greedy的な方針で決めうちしてしまってイマイチな結果でした
  • Marathon Match 49 MegaParty [☆☆☆☆☆]
    • 問題の性質をよく考えて、全体の形を作る事が最重要。教育的です
    • 本番に自分が参加したときは、何も考えず単純に焼きなましただけだったのでイマイチな結果でした

不完全情報・確率評価系


初めに情報が全部は与えられないタイプの問題。結果の期待値を評価しながら次の一手を選んでいくプログラムになる。

個人的にはこの形式はけっこう好き。

  • TCO12 Final PolygonEstimation [☆☆☆]
    • 本番で方針が大きく2つに分かれて結果も拮抗していたのが面白かった
    • なかなか実装Hardです
  • TCO11 Round1 ImageScanner [☆☆☆]
    • colunさんがガチ確率評価をやって圧勝したことで有名（？）な回
    • 問題テーマとしては、情報科学的な観点でもとても面白いものではある
    • 外部のデータファイルを処理しないといけないので少し取っつきづらいかな？
  • TCO10 Final CollapsingMaze [☆☆]
    • 確率的に即0点になってしまうという大味な問題。どこまで攻めるかの調整が肝
    • Practiceではテストケース数が限られるから運ゲー要素が強くなってしまいそう
  • Marathon Match 65 CuttingFigures [☆☆☆☆☆]
    • ある手を指したときの期待値をしっかり評価することが求められる
    • ルールもシンプルだし、良い練習になりそうな問題です
  • Marathon Match 53 TilesMatching [☆☆☆☆]
    • とにかく良い評価関数を作れるか勝負
    • これもう一回やりたいのだけどなんでPracticeにないんだ…
  • TCO09 Round1 ReliefMap [☆☆☆☆]
    • 取れる選択肢の自由度が非常に高くて、次に何をするかをどうやって決めたら良いか難しい
    • 実装も大変で、Round1（当時ルール）にしておくにはもったいない良問でした

その他・ノンジャンル・総合力


  • TCO11 Round2 QualityPolygons [☆☆☆☆☆]
    • いろいろな方針が考えられて、まさに総合力といった感じ
    • がっつり練習したかったら、ここに挙げた中で一番オススメです
  • TCO10 Round3 SubgraphIsomorphism [☆☆☆☆]
  • TCO09 Round3 BounceOff [☆☆☆☆]
    • まず、ある程度まともに動作する解を作れるかどうかが難しくて、Round3（当時ルール）に進んだ人たちでもかなり苦労していた
    • この問題は特に、SRM的な発想では全く方針決められない気がします。その意味では良い例題
    • ビジュアライザが楽しいです
  • Marathon Match 48 WatermarkSequence [☆☆☆☆]
    • Marathon史上最良問との呼び声もある問題。僕が初めてMarathonに参加した回でもある
    • めちゃめちゃ面白いけどだいぶ難しいので、練習にやってみるなら覚悟して

特殊・非推奨


ちょっと特殊なところがあってあまりお勧めできない問題たち。


やったことないやつら


問題文を読んだだけでコードを書いたことがない回もたくさん残っていました。それらの中で面白そうなのを列挙します。

自分が練習会をするとしたら、この中から選ぶことになります。

（この記事の公開と同時に練習会を始めようかとも思っていましたが、CodeVSやKaggleが出てきたのでまたいずれ）

2014-06-15

■ [TCO][MM] TCO14 Marathon Round2 18:45 はてなブックマーク - TCO14 Marathon Round2 - TopCoderの学習のお時間

http://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=15982&pm=13189

問題


ランダムな大きさの長方形がN個与えられる。長方形の各辺の長さは[1,1000]、Nの範囲は[100,1000]の一様分布。

こいつらを平面内に配置して穴を作る。

(穴の個数)^2 * (穴の面積合計) を最大化せよ。

やったこと


大きな穴を1つ作る+小さな穴をたくさん作る が最適になるのはまあ直感的にわかる。

colunさんに倣ってBigHoleとManyHolesと呼ぶ。

ManyHolesに何個の長方形を回すかは、実験してみたらN*0.54くらいが良さそうだった。

ManyHolesを作るときは、BigHoleで使われている長方形も利用した方がManyHolesに寄与する長方形の数を稼げる（その結果穴の数が増える）ので、BigHoleにくっつけて作る。

ManyHolesの領域はできるだけ表面積を小さくした方が良い（N個の長方形から作れる穴の数の最大値はNが大きいとほぼN個なんだけど、領域の外側に出ている長方形の個数分その限界から遠ざかっていく）ので、ManyHolesの部分は丸い感じになるようにする。

そのため、BigHoleの作り方を工夫して一部を外側に張り出すようにした。それでできた空間に小さい長方形を詰めていく。

小さい穴をたくさん作る方法なんだけど、賢い配置を考えて決めるのは泥沼っぽい気がして探索することにした。

長方形を小さい順に取って、既存の長方形の右側か左側に接するところを試す。他の長方形に接する一番端の箇所を見つけて、隙間ができていたらそれを穴ができたと見なす。

      |               |   |
      |               |   |
      |               +---+
 -+   |                 +---+
  |   +----             |   |
  |+----+      や     -+|   |
  ||    |              |+---+
  ||    |              |
  |+----+              |
  |                    |
 -+                   -+

こんな感じだと良い配置。

時間制限いっぱいまで、使う長方形の順序をちょっと変えながらこれを繰り返す。本当はビームサーチしたほうが良いのだと思うけど、実装時間が足りなくて断念してしまった。

あと、BigHoleの内側にManyHolesを作るのではなく外側に作ったら、面積が2%くらい増えるなーと思ってたけど、どうやっても穴の個数が減ってしまってうまくいかなかった。

画像


seed=1の例。

全体：

f:id:tomerun:20140615183106p:image

上部：

f:id:tomerun:20140615183105p:image

ビジュアライザには次の変更を加えた。

  • 穴になった部分が赤く塗られていたけど気持ち悪かったので消した
  • スクロールやズームを可能にした
  • 縮尺を表示するようにした
  • ビジュアライズ部分をテスタと分離して別プログラムにして、テスタ実行時に表示するのではなくスタンドアローンで起動できるようにした
    • テスタではログに出力しておいて、ビジュアライザにはそれを読み込ませる

結果

  • provisional score : 954551.54（各ケースで1位を100万点とした相対スコアの平均）
  • provisional rank : 9 / 170
  • final score : 954969.99
  • final rank : 10 / 170
  • レーティング : 2188->2250

意味のあるスコアを出すまでの実装が大変なのでやっぱり参加者少なかったですね。

2014-05-04

■ [TCO][MM] TCO14 Marathon Round1 21:23 はてなブックマーク - TCO14 Marathon Round1 - TopCoderの学習のお時間

http://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=15938&pm=13132

問題


yowaさんのスライドを参照。

http://topcoder.g.hatena.ne.jp/yowa/20140424

やったこと


問題読む→はい、いつものビームサーチのパターンですね

2次元グリッド上でなんかゲームやって、1手ごとならビームサーチ、全体を構成するのなら焼きなまし、というパターン最近多すぎて飽きてきた…

ターン数が10000と多くて、評価関数で色々やろうとするとビーム幅小さくなってどうやってもスコア下がってしまうので、評価関数はごく簡単にしてひたすら高速化を頑張った

探索空間


C=4の場合は1手で消せるところ、C=5,6の場合は1手か2手で消せるところを全探索

始めは高速化のため、前回動かしたところの周辺だけ探す、ということをやっていたけれど意味なかった

ビーム幅は、時間をいっぱいまで使えるよう実行中に残り時間を見ながら動的に変える

評価関数の要素


  • 累計の得点
    • 連鎖を全部シミュレートしてしまうのはあまり意味がなく、得点が0か1か2以上か、だけ判定した
  • 2×2のブロック中に3つ同色がそろった箇所・2つ同色がそろった箇所が、盤面内に何個あるか

データ構造と探索方法


struct Board{
    uint64_t f[20];   // 各セルがどの色か。最高6色、番兵として使う無効分も入れて7色なので1セル3bitで収まる。周囲2マスずつ番兵にするので20*20分確保
    uint64_t v[15];   // 各2×2の領域がどのような状態か。15×15個分確保。
                      // 3つ同色のパターン:4個、2つ同色*2のパターン:3個、2つ同色*1のパターン:6個、同色無しのパターン:1個 で合計14個なので1つ4bit
    uint64_t v2[15];  // 高速化用。基本的にはvと同じだけど、一度探索してみた結果1手や2手では消せないとわかった箇所は、
                      // 0（無効を意味する）で上書きして再度調べないようにする
};

探索するときは、たとえばv2が「3箇所そろっていて右下だけ違う色」を示しているときは、次のような状態になっている。

 AA
 AB

下の図のXの箇所を調べ、そこの色がAだった場合、それをBの箇所に持ってくる動きを候補として採用する。

 AA_
 ABX
 _X_

C=5,6でXの箇所が候補にならなかった場合は、次に、2手で揃えられる箇所として、下の図のYの位置も調べる。

 __Y__
 _AAY_
 YABXY
 _YXY_
 __Y__

v2が「2箇所そろっている」の場合も、同じように2手で揃えられるパターンを全列挙してそこに揃えたい色が入っているかを調べる。

反省


  • 同一盤面の除去をやらなかった
  • 評価関数のパラメタ調整をやらなかった

同一盤面の除去を軽く入れてみたら2%くらい上がったので、もっとこの辺をちゃんとやっていたら通過ラインくらいまで行けていた可能性もある。

詰めが甘いです

結果

  • provisional score : 950346.80（各ケースで1位を100万点とした相対スコアの平均）
  • provisional rank : 10 / 333
  • final score : 952155.96
  • final rank : 10 / 333
  • レーティング : 2334->2371 highest更新

2013-12-24

■ [部活] 国別レーティングヒストリー 01:03 はてなブックマーク - 国別レーティングヒストリー - TopCoderの学習のお時間

これは Competitive Programming Advent Calendar 2013 25日目の記事です。

TopCoder Algorithm部門の国別レーティングについて、これまでの推移が気になったのでデータフィードから計算してグラフにしてみました。

http://tomerun.info/article/tc_ratings/index.html

眺めてみると次のようなことがわかります。

  • 日本での流行り具合は、2007-2008年に一度波が来て、少し間を置いて2010年-2011年にまた伸びてます
    • 前者はITMedia記事効果？
    • 後者は最強最速アルゴリズマー講座と蟻本効果？
  • りんごさんの引退は2012年4月頃に効いてきてるはずだけど、そこまで変化ないですね。ユーザーが数百人いたら、1人ぐらいではあまり影響しないのか
  • 最近レーティングが伸びてきてるのは、台湾とカザフスタンです。今後に注目
  • 2008年に中国のアクティブユーザー数が爆発しているのは中国専用イベントがあったからだと思われます
  • 近年では、4月〜6月にアクティブユーザー数が増えて年末に向けて減っていく傾向が見られます。TCO効果だろうか
  • 2012年12月に全体的に一度レーティングががくっと下がってるけど理由がわからない。集計ミスかなあ
  • ここ2年くらいは全体的にユーザー数が頭打ちなのが見て取れます
    • 中の人ならずとも今後の行方が気になります…
    • CodeforcesやCodeChefが出てきたのも影響？

と過去を振り返りつつ未来を思いつつ、2014年も good luck & have fun!

2013-06-02

■ [TCO][MM] TCO13 Marathon Round2 20:26 はてなブックマーク - TCO13 Marathon Round2 - TopCoderの学習のお時間

http://community.topcoder.com/longcontest/stats/?module=ViewOverview&rd=15648

問題


yowaさんのスライドを参照。

http://topcoder.g.hatena.ne.jp/yowa/20130516

やったこと


まず問題読んで、これ去年のRound1と似てるなあ、はいはいビームサーチでしょ、と書いてみたらなぜか50点くらいしか出なくて涙目

評価関数みたいなので探索順序を決めるDFSを書いてみる→73点くらい

それから探索順序をいろいろ工夫してみるけど全然スコア上がらなくて早くも心が折れそうになる

ランキングを見ると64点くらいの人が多数現れていて、この人たちは一手ごとに一番たくさん鏡が壊れるところを選ぶGreedyをやってるのだろうと推測される

ビームサーチでそれより低いスコアしか取れないのはありえないので、なんかおかしいのだろうと書き直してみる→85点くらい出た。どこかでバグってたらしい

同一盤面除去をやるとあっさり90点越えた

ちょこちょこ評価関数を調整して97点くらいになったので提出

DFSで悩んでたのも、その間に偶奇性とか評価関数の要素を考えられたから無駄ではなかったと思うが

あとはC++で書き直しての高速化と、Nの偶奇で係数を分けたりの細かい調整で103点くらいまではチマチマ伸ばしたけど最後の方は全然改善しなくなってしまった

評価関数、探索順序について


  • 評価関数の要素にはこれらを使った
    • 残った鏡の数（少ない方が良い）
    • 行・列ごとの鏡の数の偶奇（偶数の方が良い）
    • 空になった行・列の数（多い方が良い）
  • 同じ盤面から分岐する数は一定以下になるよう制限を付けた
  • 評価関数の高い順に残すのではなく、いくつか下の方からもランダムにとってくる
    • これが効くのって評価関数がいまいちだからだよね…

評価関数の要素に、鏡が固まって残っていること、例えば16個残っていたら2*8よりも4*4の方が良い、ということを含ませようとしたけどうまくいかなかった。

評価の計算方法があまりうまくなかった。参照：https://twitter.com/tomerun/status/334719466153848832

二乗和は、数が大きい方を大きく評価しすぎてしまう。小さいところがあるのが悪い、というのを評価したいのだから不適切だった

このあたりの数式的な考察がテキトー過ぎてよくない

高速化について


  • 盤面の持ち方は、各マスが上下左右の隣接する鏡までの距離を持つ2Dリンクリスト的なので
    • 各マスの情報は、鏡の状態がLかRか破壊済みかで2bit、4方向の隣接する鏡までの距離が7bit*4で、1つの32bit整数に押し込められる
    • 別の方針として、空になった行が発生したら随時詰めていくのもやってみたけどこっちの方が速かった
  • 盤面の同一性判定はZobrist Hashingで
    • 使用済みのハッシュ値は全体で1つのsetに入れるのではなく、残っている鏡の個数で区別してN*N個のsetに分けて入れる（setは重い）
  • 盤面のメモリは最初に全部確保しておいて使い回す
  • 評価のためのビームのシミュレートは、壊す→戻す のではなく、「何回目のシミュレートで壊されたか」情報を盤面と別にマスごとに持っておくことで、元に戻すフェーズを無くした
  • 鏡を壊した数が4個以下のビームについては、それが出てきたところから入れるビームは同じ経路を逆に辿るだけなので省略する
  • ある盤面から1手進めるとき、盤面をコピーしてビームをシミュレートして新しい盤面を作るのだけど、同じ親から別れる盤面のうち1つだけは、盤面をコピーするのではなくswapで済んでコピーコストを減らせる
  • 盤面の中に、同じ行・列に他の鏡がない孤立した鏡がある場合は、適用する遷移はその孤立した鏡を壊すビームだけにする

結果


  • provisional score : 103.88（100ケースの合計）
  • provisional rank : 7
  • final score : 2094.61（2000ケースの合計）
  • final rank : 7 / 247
  • レーティング : 2326->2354 highestを2だけ更新

2013-04-27

■ [GCJ] Google Code Jam 2013 Round1A 18:40 はてなブックマーク - Google Code Jam 2013 Round1A - TopCoderの学習のお時間


Round1B・1CはTCOマラソン期間中になるのでここで通過しておきたいという事情があってScalaではなくC++で


  • A

オーバーフローに気をつけつつ二分探索する。

// #includeは略
using namespace std;
typedef long long ll;

ll r,t;

ll solve() {
	scanf("%lld %lld", &r, &t);
	ll left = 0;
	ll right = (ll)sqrt(t) + 1;
	while(left + 1 < right) {
		ll mid = (left + right) / 2;
		ll sum = mid * (2 * r + 2 * mid - 1);
		if (sum > t || (2 * r + 2 * mid - 1) > (ll)2e18 / mid + 1) {
			right = mid;
		} else {
			left = mid;
		}
	}
	return left;
}

int main() {
	int T;
	scanf("%d", &T);
	for (int tc = 1; tc <= T; ++tc){
		printf("Case #%d: %lld\n", tc, solve());
	}
}

  • B

Greedyに使う。O(N^2)。

後の作業で今の位置のものより価値が低いのがあったら、その分のエネルギーは今の所で使っておいた方が良い。今の位置の以上の価値のものが出てきたらストップ。みたいな感じ

// #includeは略
using namespace std;
typedef long long ll;

ll E,R,N,V[10001];

ll solve() {
	scanf("%lld %lld %lld", &E, &R, &N);
	for (int i = 0; i < N; ++i) {
		scanf("%lld", V+i);
	}
	ll ans = 0;
	int e = E;
	for (int i = 0; i < N; ++i) {
		ll use = max(0LL, E - R);
		for (int j = i+1; j < N && use > 0; ++j) {
			if (V[j] >= V[i]) break;
			use = max(0LL, use - R);
			if (j == N-1) use = 0;
		}
		if (i == N-1) use = 0;
		if (use < e) {
			ans += (e - use) * V[i];
			e = use;
		}
		e = min(E, e + R);
	}
	return ans;
}

int main() {
	int T;
	scanf("%d", &T);
	for (int tc = 1; tc <= T; ++tc){
		printf("Case #%d: %lld\n", tc, solve());
	}
}

  • C small

3と5の数は、それぞれ一番大きな因数の数。

2と4の数は、2の因数が奇数個のものがあったら少なくとも2は1つ含まれている…みたいな感じで適当に

// #includeは略
using namespace std;
typedef long long ll;

int R,N,M,K;

int count(int& v, int div){
	int ret = 0;
	while(v % div == 0) {
		v /= div;
		++ret;
	}
	return ret;
}

void solve() {
	scanf("%d %d %d %d", &R, &N, &M, &K);
	for (int r = 0; r < R; ++r) {
		int c2 = 0;
		int c3 = 0;
		int c5 = 0;
		bool odd2 = false;
		for (int k = 0; k < K; ++k) {
			int v;
			scanf("%d", &v);
			int count2 = count(v, 2);
			odd2 =  odd2 || count2 % 2 != 0;
			c2 = max(c2, count2);
			c3 = max(c3, count(v, 3));
			c5 = max(c5, count(v, 5));
		}
		int all = c3 + c5 + c2 / 2;
		for (int i = 0; i < c3; ++i) {
			printf("3");
		}
		for (int i = 0; i < c5; ++i) {
			printf("5");
		}
		for (int i = 0; i < c2 / 2; ++i) {
			printf("4");
		}
		if (odd2) {
			printf("2");
			++all;
		}
		for (int i = all; i < N; ++i) {
			printf("2");
		}
		printf("\n");
	}
}

int main() {
	int T;
	scanf("%d", &T);
	for (int tc = 1; tc <= T; ++tc){
		printf("Case #%d:\n", tc);
		solve();
	}
}