ABC201

Dまでは最近の自分の良さを出せていた。正確性を少ししか犠牲にせずスピードを出せている。Eで脳を破壊された。ゴミのような時間だった。Fをもっとやればよかった。

A - Tiny Arithmetic Sequence

ソートして確かめるだけなんだけど、実装で細かいミス(ゲームでいう操作ミスみたいなやつ)が続いて、1分を大きく超えてしまった。

B - Do you know the second highest mountain?

structを用意して、あとは入力を受け取ってソートして2番目を出力するだけ。

C - Secret Number

暗証番号は10000通りしかないので条件を満たすか全部チェックする。あるはずのものがない、ないはずのものがある、というのをはじく。

D - Game in Momotetsu World

おいおい、プラスルが赤でマイナンが青なのに'+'が青で'-'が赤かよ(問題文が悪いというより自分の運が悪かった)。難しそうで一瞬ビビるが、うしろから考えれば楽そう。そのマスからゲームを始めたときの手番側の得失点差でDP。右下隅を特別扱いしてそこのスコアは0。それ以外のマスでは右と下のマスを(存在すれば)見て、マスのスコアを(手番が逆なので)符号反転しマスが'+'なら1を足す(あれ、'-'のとき1を引いてないけど大丈夫!?(そっか、取った'+'の数がわかれば'-'の個数もわかるので同じことなのか(と思ったけど後述するように嘘だった)))。2つあればスコアが大きいほうを採用する。

スコアを回答させることもできるのに判定問題とすることでサンプルが弱くなって嫌らしいと思った(けどサンプル1は得点書いてあるしそうでもないか)。

'-'のとき1を引いてないので大丈夫ではなかったですね。下のケースで落ちる(正しくはAokiだがDrawを出力する)。

1 2
--

Dまでを通す速さでtokuminiさんに勝っており、いいペース。

E - Xor Distances

「距離」じゃないものにdistという名前を付けるのはいいのか?さて、この前の典型90(039)と同じじゃんって思ったけど、書いてみて思い知らされた。xorの和というのがとにかく扱いづらい。ずーっと(微妙に同じところではないけど)ぐるぐる回っていて、時間が過ぎ、脳が破壊された。残り15分を切って、いつもならワンチャンここから書き切ることを狙うのだが、今日はもう行ける気配がなかった。

wが0か1のときの問題を60回解けばいいというのは途中で気づいた。xorで和がどう変化するかを考えるとビット毎に個数を管理することになるのでそこで気づく。今にして思えば、DFSをN回やる遅い解法でまず書いてみてもよかった。全方位木DPにしても、辺に重みがあるタイプは経験がなく脳が壊れる。考察の過程で2択が多すぎた。どう立ち回るのがよかったのか、あるいはこれで最善だったのか、この辺りの(コンテスト終了後の)判断は本当に難しい。

F - Insertion Sort

左から順に、左端に移動させたもの・左端にも右端にも移動させてないもの・右端に移動させたもの、と最終的に並んでいるとしてよい。左からDPしたくなる。中央の区間については、LISを求めてそれ以外を好きな位置に移動させる操作で動かせばよさそう(それだけの操作回数は必要だし、移動させない要素は昇順になっている必要がある)。コストは、BやCがAより大きかったらAでやってもらうことにしておく(必要かわからないけどやっといたほうが安全そう)。そこから進まなかった。