【競プロ精進日記】AtCoder 日立製作所社会システム事業部プログラミングコンテスト2020

2020.03.09
競プロ

1. はじめに
2. A
3. B
4. C
5. D
6. E
7. F

はじめに

当ブログは問題の解説がメインではなく、筆者の解法やアイデアの保存がメインです。
したがって、読者の期待に沿えないことがあると思いますがご了承ください。

A

A – Hitachi String
1WAしました。
Sの長さが偶数で奇がh、偶がiならオッケーで判定しました。
Sの長さは最大でも10なので、”hi”,”hihi”,”hihihi”,”hihihihi”,”hihihihihi”かを判定するだけでもいいですね。
WAなければ500位程度狙えたと思います。残念です。
https://atcoder.jp/contests/hitachi2020/submissions/10674527

B

B – Nice Shopping
制約、変数が多いと問題読むのをためらいますね。
（a最小＋b最小）と\(a_{x_i}+b_{y_i}-c_i\)を比べるだけですね。
https://atcoder.jp/contests/hitachi2020/submissions/10672333

C

C – ThREE
難しいです、コンテスト中は解けませんでした。
AtCoder Problemsでも黄diffだったので、そりゃ解けないかなという感じです。
2部グラフに直せることさえ分かれば0,1,2を並べていく感じはわかりますが、距離3であることと和・積の関係で2部グラフに直せるというのはあまりわかっていません。
まず、和が3の倍数であるということは余りが1の数には余りが2の数、余りが0の数には余りが0の数と、相手にできる数は限定されます。
次に、積について考えると一方の数に3の倍数を選ぶと当然3の倍数になります。
さらに、この問題においてどのような値を選ぶかは関係なく、関係あるのは3で割った余りが0か1か2かのみです。
ここが最も重要な発想だと思いますが、頂点の距離を偶奇で分けたときに、距離が3（奇数）になるというのは、片方が偶で片方が奇のときです。
これにより、2部グラフに直せるということらしいですが、これは思いつかないですね。
2部グラフにさえ置き換えることができれば、一方を1にもう一方を2にして余った頂点を3にすれば条件を満たす順列が作れます。
精進したいと思います…
https://atcoder.jp/contests/hitachi2020/submissions/10697682