AtCoder Regular Contest 105 出場記

AtCoder を初めて一年以上経つけれど、Regular Contest は初めての参加。 自分のレートは想定されるレンジよりも低めなので気軽なお気持ちで臨んだのだけど、久々にレート上昇させることができたのでちょっとテンションが上がった。 今回のARCはC以降がすごい難しくて、強者でもB完で速解き勝負っぽくなっていたもよう。

A - Fourtune Cookies

なつかしさを感じるタイトルだけど、Fortune と4枚を示す Four がかかっている。 4枚のうち 1, 2, 3 枚クッキーを食べたときのパターンを計算すればよい。 bit全探索とか呼ばれるやつで 4つのBooleanを全パターン上げてACを得た。 ABCのA問題よりはさすがに難易度が上という印象。

B - MAX-=min

データの扱い方を最初に考えて、以下を試みた - 数列のうち重複は取り除いても良さそうだったので最初に省いた。 - 最小値は滅多に動かず、最大値は頻繁に入れ替わりそうだったのでバイナリヒープを使った。

あとは問題の通りに計算をしてサンプルの入出力が一致させることができた。 ここまで早めに実装できたので、AC取れたらおいしいなーと思って投げたけどTLEになった。なるほど。

最大値が1億、最小値が1だとそれだけで1億ループしてしまうことになるので、 Max -= min の繰り返しをできる限り掛け算で省略してやることが必要とされる。どこまで省略するかの閾値を「次の最大値まで」「最小値まで」どっちにするかで迷った。

「次の最大値まで」だとあまり計算量が縮まらないケースもありそうなので、思い切って「最小値を超えない」とこまで一気に引き算してみた。この結果サンプルはいずれも通っていたので提出してみたところACを得た。あまり深く考えていないのでラッキーACという印象。あとで解説を読む。

C - Camels and Bridge

時間いっぱいつかってWAだった。脳みそはたくさんつかったので記録を残す。

考えたこと

• 橋のパーツのうち、ネックとなる部分さえ通せればとりあえず良さそう
• ラクダは最大で8頭いて、1個から8個のグループに分けることができれば良さそう
  • グループ内のラクダは間隔0, つまり密着した状態
• このグループのうち、合計重量が最大のものがネックとなる橋を通れたら良さそう
• 通れた時、 (グループ数 -1) * ネックとなる橋パーツの長さ を解とすれば良さそう

これらをコードに落としたのは下のもの。 atcoder.jp

そもそもサンプル4が合ってないので、前提として考えたことのいくつかが間違っているようだ。 答えのずれ方からして、ネックとなる橋以外についても考慮する必要がある気がする。解説を読んで復習する。

D以降

未だ見ず