AtCoder Beginner Contest 100
Updated:
はじめに
ABC 100 回おめでとうございます。 AtCoder のさらなる発展をささやかながらお祈りしております。
重かった。問題を見るのも難しかった。 judge もしばらく進んでいなかった。今までサーバー重くて問題見るのも judge 見るのも一苦労なんて一度もなかったんだけど、多くの人が来たんだろうか。それとも攻撃されたんだろうか。 (下の方に追記しました)
もしこういう重い状態が来週も続くのであれば、最初に submitter を起動した時に全問題ページローカルに保存しようかなと思う。 Selenium でどうするべきか調べる必要がある。
私は ARC/ABC の時は ARC 、ABC only は ABC に出るようにしているので、 100 回記念だから ABC 出ようとか思ってもいません。いつも参加していて、今回たまたま記念に立ち会っただけです。
解答は全部 Ruby で書いた。特に理由はないです。
Source codes
Solutions
A - Happy Birthday!
解答
$a, b \leq 8$ ならば可能、そうでないなら不可能である。
明らかだろうけど、理由
$16$ 等分のピザに順に番号を振る。奇数の番号がついたピザを E869120 君、偶数の番号がついたピザを square1001 君がとるのが最善である。この方法なら $a, b \leq 8$ ならば確かに可能である。仮に片方が 9 枚以上取ろうとすると、同じ人がとなり合うケーキをとることになるから不可能である。
B - Ringo’s Favorite Numbers
解法 1
真面目に $1$ から順番に $100$ で $D$ 回割り切れるか検討していく。最大でも $10^7$ 程度であるので間に合う。
解説放送によると、実装は再帰を使うとわかりやすい。私は while 文で書きましたが、それが良さそうですね。
解法 2
$N < 100$ ならば $N \cdot 100^D$ 、そうでないなら $(N + 1) \cdot 100^D$ である。
ポイント
「ちょうど $D$ 回割り切れる」である。たくさんの人が 1 回 WA している。もちろん私もである。これのせいで judge queue が詰まったらしい。
目覚ましかけて開始告知だけして寝てたら、開始直後のWAが大量発生した影響で無茶苦茶ジャッジが詰まっていたらしい。参加者の方々ごめんなさい＞＜
— chokudai(高橋 直大) (@chokudai) 2018年6月16日
C - *3 or /2
$3$ をかける動作により操作回数が増加することも減少することもない。ゆえに、単純に「1 個以上の好きな $a_i$ を $2$ で割る」という動作と操作回数は同じである。これの最大操作回数は $2$ で割れる回数を個別に足して和をとれば求まる。
D - Patisserie ABC
ある $M$ 個のケーキの綺麗さの合計 $A$ 、 美味しさの合計 $B$ 、人気度の合計を $C$ とする。求めるものは $\lvert A \rvert + \lvert B \rvert + \lvert C \rvert$ である。絶対値を素直に外すことを考えると、複号任意で $\pm A \pm B \pm C$ の最大値をとればよいとわかる。つまり、複号の取り方 $8$ 通りを全部試すことにして、各ケーキのスコアを $(\pm x_i, \pm y_i, \pm z_i)$ として、合計スコアを貪欲に選ぶ。
ポイント
少し迷ったが問題なくクリア。大学以降の数学に慣れていると、絶対値は自分でつけるもので、場合分けして外すものではなくなる。
Others
混雑しているせいか、こんな画面が出た。初めて見た。記念にスクショしておく。
追記
なんか昔のAtCoderはやっぱり大量提出捌けないみたいなので、順位表はbetaの方でご確認くださいな。https://t.co/UO5iFUNRxs
— chokudai(高橋 直大) (@chokudai) 2018年6月16日
まじか…