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

ゆらのふなびと

競プロ, Python, C++

AOJ-ICPC 300 Line Gimmick

ICPC

問題

Line Gimmick | Aizu Online Judge

解法

実装しんどいなーと思いながら書いたら一発で通って最高↑↑な気持ちで解説を見たらすごい簡単で悲しくなったので書きます。

ある'>'(=R0)からスタートすると、向きが変わるのはR1より右側にある1つ目の'<'(=L1), R0より左側にある1つ目の'>'(=R1), R0より右側にある2つ目の'<'(=L2), ...という風に続きます。左から順にR0をすべて試すとすると、どこが最後の反射になるかをしゃくとり(?)っぽく更新していくことができます。詳しくはコードのようにやりました。

ところがしゃくとりっぽくやる必要はなくて、累積和だけわかればどこが最後の反射かわかります。

mayokoex.hatenablog.com

実は n - min(左端に連続する'<'の個数, 右端に連続する'>'の個数) でいいらしい。

http://acm-icpc.aitea.net/index.php?plugin=attach&refer=2015%2FPractice%2F%E6%A8%A1%E6%93%AC%E5%9C%B0%E5%8C%BA%E4%BA%88%E9%81%B8%2F%E8%AC%9B%E8%A9%95&openfile=D.pdf