AtCoder Beginner Contest 195のきろく
パナソニックプログラミングコンテスト（AtCoder Beginner Contest 195）でレートを冷やしてしましました...
- A - Health M Death (100点)
- B - Many Oranges (200点)
- C - Comma (300点)
- D - Shipping Center (400点)
- E - Lucky 7 Battle (500点)
- F - Digits Paradise in Hexadecimal (600点): 未提出
- 結果、感想
A - Health M Death (100点)
そのままif文で処理します。C/C++はint型をそのまま突っ込めるので突っ込みます(その必要はない)。
B - Many Oranges (200点)
個のみかんを選んで重さの合計がちょうど
となったとすると
より
で
は整数より
です。
が正整数の時
であることから整数で計算できます。
上限と下限の大きさが反転しているときこのような は存在しないと判定できます。
C - Comma (300点)
のとき右から
番目のコンマは
から
までの
個の数字で用いるのでその和をとります。
D - Shipping Center (400点)
この問題で色々詰まってしまいました。最終的には解けたのですが終了後にもっと効率の良い実装を思いつきました。
箱 と 箱
について それぞれの箱に入れることのできる荷物の集合を
とし、
とすると
となるので、クエリ毎に、小さな箱から順に、その時点でその箱に入れることができる価値最大の荷物を入れていくことで最大値を得ることができます。
ここで「その時点でその箱に入れることができる価値最大の荷物」は 荷物を を基準としてソート*1することで尺取り法で優先度付きキューに
の値を入れていくことで求めることができます。
E - Lucky 7 Battle (500点)
ゲームDPだとは思っていたのですが、Dを通すのが遅れたため、あまり考察できず時間内には通すことができませんでした。DPで各状態において値をどうすればいいかについて考えていました。集合が思いつきかけたので辛い...
$$
{\mathrm{dp}}_{i+1} = \left\{
\begin{array}{ll}
\{n \mid 10n\bmod{7} \in {\mathrm{dp}}_i \lor (10n + S_i)\bmod{7} \in {\mathrm{dp}}_i \} & (X_i = \texttt{`T'})\\
\{n \mid 10n\bmod{7} \in {\mathrm{dp}}_i \land (10n + S_i)\bmod{7} \in {\mathrm{dp}}_i \} & (X_i = \texttt{`A'})
\end{array}
\right.
$$
となり、
この
std::setを要素とする配列、bitによる集合を要素とする配列、2次元配列等として実装できます。
F - Digits Paradise in Hexadecimal (600点): 未提出
素数ごとに考えるのかなぁってぐらいしか思いついてないです...
結果、感想
前回折角1700超えたのに... 次は恢復できるよう頑張ります
*1: の値でソート。
が等しい要素については
の値でソート
