ARC103 参加記

C問題 /\/\/\/

問題文

C - /\/\/\/

解法

偶数番目と奇数番目について何に統一するか決めればよくて,かぶってはいけないことに気をつけるとできる.
実装が難しいがmapを配列にしてソートしてforで回した.一致判定はifよりforのほうが書きやすいと思う.添字ミスって1ペナ(Cでペナ出すの何週連続だ

E問題 Tr/ee

D問題が読解大変そう&&ひらきちさんが既に解いてたのでとりあえず問題を読むとシンプルだったのでこっちから解いた

問題文

E - Tr/ee

解法

実験してみる.
まず,n個の連結成分が作れなくて1個は必ず作れるのは明らか.
また,n個の木からk個が作れるとき,n-k個も作れる.また作れないときも同様に対称性があることがわかる.
よって,最後の一要素を覗いたn-1個は回文になっていないと作れないということがわかる.回文ならすべて作れるのかを考えたい.

競プロで出される構築問題は,基本的に何らかのアルゴリズムに沿って解けるので,実験するときもそのことを意識してやる.
木なので前の要素にくっつけていくようにして生み出す方針にすると,次のことがわかる
f:id:SugarDragon5:20180929235752p:plain
これを繰り返していくといい感じにできそうでは?ってなって,実際できる(図書くのだるいので省略
結構バグるがAC.

D問題 Robot Arms

問題文

D - Robot Arms

解法

部分点はdを1だけでできそうなのでやるがWA.そのままコンテスト終了.
バグはしょうもなかったのではい.
満点は2べきにするんだと思う(まだ解いてない

結果

f:id:SugarDragon5:20180930000148p:plain
パフォーマンスは1861,レートは1668->1689(+21 highest)