AtCoder: diverta 2019 Programming Contest

published: ,
last modified: .

lang: ja

category: competitive_programming

tags: atcoder ocaml

A. Consecutive Integers

区間を覆う問題は何度か解いたので記憶していた.図を描けばわかりやすい. 解答例

選ぶ連続した整数を区間と見る.例えばN=8,K=3N=8,K=3のとき, ooo..... のようになり,'.'の数だけ区間を右にずらせる.'.'の数はNKN-Kであるから,答えは初期位置も含めてNK+1N-K+1

B. RGB Boxes

解答例

各色について買う箱の個数を決め打ちすることを考える:例えば赤ならそれぞれ00個以上N/R\lfloor N/R \rfloor個以下[1]G,BG,Bも同様).これだとO(N3)O(N^{3})であり間に合わないが,2種類だけ決めれば残りに必要な箱の個数は求まる:箱の個数をそれぞれr,g,br,g,bとおくとb=N(rR+gG)Bb=\frac {N-(rR+gG)} {B}.これが割り切れかつ先の範囲内でなければならない.この方針ならO(N2)O(N^2)であるから間に合う.

ところでeditorialがそうしているようにr,gr,gの上限はNNでも,NNの上限の30003000でもよい(どうせbbが負になるため).

C. AB Substrings

コーナーケースに引っ掛かっていると思って色々試行錯誤した挙句元々の解法が間違っていた. 解答例

まず各文字列の中のABの個数を数える.次に末尾にAや,先頭にBがあるものを組み合わせてABが作れることに注意する(文字列の中のABとは重ならないので安心).両方を兼ね備える文字列に注意:パターンBAとおく.そうでなく末尾にA,先頭にBがあるものをそれぞれパターンXA, BXとおく.これらの組み合わせ方を考えたい(どちらでもないパターンはどう組み合わせても意味が無いので以下無視する).

はじめばXABX,およびBAをそれぞれ独立に組み合わせた後で合体させればよいと考えていたが,誤りである:例えばBA=3,XA=2,BX=2のとき,XABX+XABX+BABABAとなって5個であるが,最適なのはXABX+XA+BABABA+BXの6個である.このようにBA...BAの先頭および末尾にあるB,Aを活用してそこにXA, BXを組み合わせたほうが得をする.

以上より:

  • BAがあるとき:
    • BA...BAの中にABBA1\text{BA}-1
    • さらに両側にそれぞれXA, BXを追加できる
      • XA, BXのそれぞれについて,それが1個以上あればABが1個増える(XA, BXも1個減る).これらは破壊的に更新されたとする.
    • 余ったXA, BX同士を組み合わせてXABX...XABXを作る:ABmin{XA,BX}\min \{\text{XA}, \text{BX}\}
    • 従ってAB+BA1+min{XA,BX}\text{AB} + \text{BA} - 1 + \min \{\text{XA}, \text{BX}\}
  • BAがないとき:
    • XA, BXの組み合わせのみ.従ってAB+min{XA,BX}\text{AB} + \min \{\text{XA}, \text{BX}\}

文字列の中の特定文字列の個数を数える関数が見当たらなかったので適当な実装をした.最初はStr.split結果のlengthから1引いたものとしていたが,JavaScriptなどと異なりこれは特定文字列が先頭や末尾にある場合に空文字列が入らないためズレてしまう[2].そこで単純にループによる数え上げで実装した.あるいは検索対象の先頭に適当な文字(例えば本問では小文字は出ない)を入れたりJavaScript版を再現したりすれば大丈夫.

D. DivRem Number

感触は300点,数学要素も考慮すると簡単目な400点問題な気がする. 解答例

500点問題ということで最初数分は難しく考えすぎてしまったが,素直にN=pm+qN=pm+qと表示すればよい:p=Nmp=\lfloor \frac {N} {m} \rfloorq=Nmodmq=N \bmod m.これらが等しくなるようなmmを求めたい:N=pm+p=p(m+1)N=pm+p=p(m+1).よってNNの約数ddが分かればmmの候補m=d1m = d - 1が得られる.あとは元々の条件N/m=Nmodm\lfloor N/m \rfloor = N \bmod mを確かめればよい(00除算にならないように注意).


  1. 一応証明しておく.N=pR+q (0q<p)N=pR+q\ (0 \le q \lt p)とおくとp=N/Rp=\lfloor N/R \rfloor.このときpRN=pR+qpR \le N = pR+q <pR+p=(p+1)R\lt pR+p = (p+1) Rであるから,N/R+1\lfloor N/R \rfloor + 1個以上は買えない. ↩︎

  2. "abxabyab""ab"splitする場合,JavaScriptでは["","x","y",""]となるが,OCamlでは["x","y"]となる. ↩︎

copyright © 2024 sk0

Next.js-powered!