脳log[20201202] AtCoder Regular Contest 109／A,B,C,D

最終更新: 2020-12-03T19:37+0900

♪ [AtCoder] AtCoder Regular Contest 109／A,B,C,D

先月28日土曜日の振り返り。ARC なので A 問題が 300 点からスタートする。２問解けたらまあまあという感じ。配点が同じ 300 点、400 点でも、ABC のと比べるとちょっと手強い印象を持っている。

時間は長めの２時間。ABC と違って C、D、E、F 問題にはだいたい取り付く島さえないので、時間が足りなくなるということはまずない。簡単すぎるテストと難しすぎるテストは時間が余るという点で共通する。

 A 問題 Hands

上の階に上がるのに階段と廊下の２種類の手段があるというのが不思議な設定だが、床の高さが半階分ずれた２棟が上りと下りのスロープで結ばれていると解釈するツイートを読んだ。なるほど。ところですべてのフロアが渡り廊下で連結されているなら、それも水平１本ではなく三角形で繋がっているなら、２棟は一体の構造物として設計されているのでは？ そのとき「廊下」はどのような形態になりますか？

 提出 #18452990 (AC)

11分ちょっとで提出している。こうだったらこうだな、こうだったらああだなと考えながらとりあえず書き出してみてそれをそのまま提出した。

 B 問題 log

考えたこと。

• 長さによらずコストが同じであるし、切れ端を捨ててもいいのだから、とりあえず長い方から買えば良い。
• そしてもちろん、長い丸太から切り出して買うのを節約する丸太は、短い方から順に揃える。
• n がいくつのとき、何本分の節約ができるかが問題。
  • 順番に書き出してみれば、長さ１を１本分節約するのに１本の購入が必要。(n=2)
  • そこからもう１本節約するには長さ２を１本用意しなければいけないので、追加で２本の購入が必要。(n=2+3=5)

節約する本数 k から n (の下限)を求める式が n ≧ Σ(k+1) = k+k*(k+1)/2 だということはすぐにわかったけど、n が与えられたときに k の最大がいくつになるのかを求めるのに、sqrt を使ってずっと考えていた。B 問題に取りかかってから最初の提出まで 46 分。

 提出 #18463725 (AC)

n の制約上限は 10^{18} であり、(10**18).bit_length は 60。なんだ探索すればいいじゃないと気がついたらもう問題は残っていなかった。

 C 問題 Large RPS Tournament

RPS って Rock, Paper, Scissors なんだな、たぶん。本番中はよく考えなかったけど。

k の上限は高々 100 ではあるけれど、2^k 通りの勝敗を考えるには大きすぎる数だ。まあ頭の中で考える分にはあまり関係がないので、トーナメントをシミュレーションして、その際に文字列 s のどの部分を参照するのかを確かめていた。優勝者の手、準優勝者の手、準々優勝者の手……がどこからやってくるのか、逆方向のシミュレーションもした。

 提出 #18467915 (AC)

最初の提出まで 30 分。C 問題という段階で解けなくてもともとなので、あせる理由はどこにもない。

 D 問題 く

残り時間は 30 分だったけど考えるだけ考えた。

• 移動方法は３通り。軸となる２つの石を選べば決まる。
• 石の配置は単位正方形を基準にして分類できる。すなわち、ある一角(たとえば左上)の座標と、くの字の折れ曲がり部分の位置(左上、右上、左下、右下)の組み合わせで決まる。
• さて最小の移動回数は？

四角形の座標移動をまず考えた。

• 水平方向、垂直方向に１移動するには２手かかって、くの字の向きが変わる。
• 水平垂直同時に１ずつ移動するには３手かかって、くの字の向きはそのまま。

ここまで考えたが、この安定した移動に入る前と出るときに何手かかるのか数え切れなかった。B 問題のことを思い出して探索すればいいじゃない、ということには気がついたが、その探索がどういう形になるのかおぼろにも想像ができなかった。

というわけで D 問題はひとつの提出も用意できないまま放置している。

あ、３通りじゃないや、５通りある。じゃあいろいろ変わってきちゃうね。

え？ ７通りある？ だから最初から最後まで機械に数えさせるべきなんだな。