読者です 読者をやめる 読者になる 読者になる

Atcoder Grand Contest 11

参加しました。完全に忘れていて数分遅刻しました。

A問題 Airport Bus

sortして前から貪欲した。終わり。

B問題 Colorful Creatures

sortして前から足していってA[i-1]までの和S[i-1]の2倍がA[i]より大きければスルー。もしS[i-1]*2<A[i]ならばmin=iとして記録。

N-minが答え。

 

C問題 Squared Graph

グラフ問題は無理。


D問題 Half Reflector

算数ゲーの匂いがしたので、いろいろ検証しだす。

 

左端の状態がAだと最初で終わり。Bだと必ず右端から抜ける。

i番目とi+1番目が異なるとi番目は変化。同じならば変化しない。右端は必ずA。

たくさんやるとBABA...BABA or ABAB...BABA or BBABA...BA。

左端がBのi番目の状態列は1文字目を消去して反転して末尾にAをつけるとi+1番目の状態列になる。

 

などがわかる。あとは書くだけ(書けなかった)。

コードをちゃんと書きましょう。

274位 パフォーマンス1840 レート1888(-7)。

以上。

 

住建はクソ。