ARMERIA

Rubyと競技プログラミングの話 AtCoderやCodeforcesの問題解説記事が多め。

ABC100 参加記録

AtCoder Beginner Contest 100 - AtCoder

記念すべき100回目のABC!おめでとうございます! 次は目指せABC200。

ということでおめでたい回なのですが、私の成績は全完37分台で144位。うーん…2WAが痛いです。

f:id:betrue12:20180616223134p:plain

平方数賞ですね(そんなものはない)

振り返っていきます。

A - Happy Birthday!

A問題からちょっと頭を使う内容。

A - Happy Birthday!

入力例2の図が分かりやすいですが、1人が取る個数が8個までなら1個飛ばしで取ることができます。逆に9個取ってしまうと、必ずどこかが隣り合ってしまいます。

そのため両方の個数が8以下なら Yay! 、そうでなければ :( が答えです。

ACコード:Submission #2675152 - AtCoder Beginner Contest 100

素直に YES NO にしない問題が多いのは、今回のライターさん(通称「双子」さん)の特徴ですね。楽しいですが、タイプミスが少し心配になります。問題文からコピペするのが吉。

B - Ringo's Favorite Numbers

B - Ringo's Favorite Numbers

2WA出しました…ひどい:(

パッと見て問題文がよく分からなかったのですが、サンプルの記載を見るとイメージが掴めます。

  • 100でちょうど「0」回割り切れる正整数:1, 2, 3, 4, ...
  • 100でちょうど「1」回割り切れる正整数:100, 200, 300, 400, ...
  • 100でちょうど「2」回割り切れる正整数:10000, 20000, 30000, 40000, ...

そのため、  N * 100^{D} が答えになりそうです…が、  N = 100 の時は100で割り切れる回数が増えてしまうので飛ばさなくてはいけません。

これを0WAで通してる人、すごい。

ACコード:Submission #2680984 - AtCoder Beginner Contest 100

C - *3 or /2

C - *3 or /2

問題文が少し回りくどく書かれていますが、「全ての  i に対して3倍することはできず、操作後の  a_{i} の値は整数でなければならない」ということは、全ての値が2で割れなくなったら終了です。

また、「3倍する」という操作は、「2で割れるかどうか」に影響しないので考慮する必要がありません。これは3が2と互いに素だから言えることです。

というわけで、問題を単純化します。

  • 2で割れる数を1つ以上選び、2で割る。
  • 全ての数が2で割れなくなったら終了する。

「1つ以上」と書きましたが、操作回数を最大にしたいので、1つずつ選んでいくのが最善です。ということで、与えられた  a_{i} の「2で割れる回数」の総和を出力すれば答えになります。

計算量は、入力  a_{i} の最大値を  A として  O(N \log A) N \le 10000, A \le 1000000000 なので通ります。

ACコード:Submission #2676571 - AtCoder Beginner Contest 100

D - Patisserie ABC

D - Patisserie ABC

 (x_{i}, y_{i}, z_{i}) の組  N 個から  M 個選び、 x_{i}, y_{i}, z_{i} のそれぞれの「総和の絶対値」の和を最大化する問題。…数式で書いたほうが誤解がなくていいですね。

 \max ( |\sum_{i} x_{i}| + |\sum_{i} y_{i}| + |\sum_{i} z_{i}| )

さてどう考えるかですが…絶対値というのは元の数に対して、+1倍、-1倍のどちらかになります。これは当たり前のことに見えますが、「2通りしかない」というのが大きな手がかりになります。

求めたい値には絶対値が3つ含まれているので、これを8パターンに場合分けすることができます。書き下すと以下の8つです。

  •  \max ( + \sum_{i} x_{i} + \sum_{i} y_{i} + \sum_{i} z_{i} )
  •  \max ( + \sum_{i} x_{i} + \sum_{i} y_{i} - \sum_{i} z_{i} )
  •  \max ( + \sum_{i} x_{i} - \sum_{i} y_{i} + \sum_{i} z_{i} )
  •  \max ( + \sum_{i} x_{i} - \sum_{i} y_{i} - \sum_{i} z_{i} )
  •  \max ( - \sum_{i} x_{i} + \sum_{i} y_{i} + \sum_{i} z_{i} )
  •  \max ( - \sum_{i} x_{i} + \sum_{i} y_{i} - \sum_{i} z_{i} )
  •  \max ( - \sum_{i} x_{i} - \sum_{i} y_{i} + \sum_{i} z_{i} )
  •  \max ( - \sum_{i} x_{i} - \sum_{i} y_{i} - \sum_{i} z_{i} )

これを全部計算すれば答えが出ます。 全探索、「間に合う時には」シンプルで強力な解法です。

各符号を決めてしまえば、  x_{i}, y_{i}, z_{i} それぞれに符号を掛けて和を取ったものを  N 個計算し、ソートして大きい方から足していけばいいです。

計算量は  O(8 \times N \log N) です(8も一応書きました)。  N \le 1000 なので全く問題ありません。

ACコード:Submission #2678544 - AtCoder Beginner Contest 100

おわりに

A, Bと少しクセのある問題でした。Dはとても良い問題だったと思います。

ABCオンリーが続いていますが、来週はついにARCが予定されています!頑張りましょう!