日立製作所 社会システム事業部 プログラミングコンテスト2020

A - Hitachi String

どうやって問題文の解釈の正しさに確信を持てばいいかわからなかった(何しろ"hitachi"がhitachi文字列じゃない)。まあ普通に解釈して、実装は、文字数が偶数かつ(0-indexedで)偶数番目がhで奇数番目がiであることをチェックした。

B - Nice Shopping

企業コンの200点ということでこの複雑そうな見た目は警戒してしまう。よく読めば別に難しくない。割引券を使う場合と使わない場合を考えればいい。使うときはM通りを調べる。使わないときは最安の2つを買う(コーディングにかかる時間を最小化するためソートした)。

600が解けない可能性も考え、できるだけ速く解いたが、順位表を見ると速くなかった。仕方ない。ノンペナで2問解けたのでよかった。

C - ThREE

600がたくさん解かれる可能性もある。あまりのんびりはできない。

Nが3以下ならどんな順列でもいい。重要なのは3で割ったあまりで、1234567は1201201のようになる。ダメなのは11と22のみ。距離3はかなり色々な場所へ行けるので何も思いつかない。開始30分くらいでDへ行く。

15分くらいDを考えて戻ってきた。否定とってみるかと思い、やってみる。あるijについて、11か22かつ距離が3。1と2だけ見ればいい。n/3個くらいある1を距離3にならないよう配置できるか。枝分かれがなかったら? あれ、交互にやればいいのでは(根付き木で考えて深さが偶数のところを1、奇数を2にして、その一部を0にして個数を合わせる)。慌てて実装にかかろうとするが、個数に偏りがあるとダメだ。まあ、少し別のことやってると違う発想が出るんだよね。話が進んでよかった。

ここから、色々考える。うにを辺でくっつけたやつを考えると、個数に差があるときまずい。まずいけど、多すぎる2を1に変えて、その1が影響する範囲を0にすればいけそう。構成できない例は思いつかないが、プログラムで全部構成させないといけないのはつらい。ジャッジどうやって書くんだこれと思ってそこから解法につながらないか考えるが何も出てこない。残り40分くらいになり、全く解ける気がしなくなった。つまらないね。せっかくのARCを楽しめないのは残念。時間を捌くために、偏ってない場合の実装を書いた。これが(コンテスト中にCを通すために)役立つ可能性は低いけど、何かやっていれば違う発想が出るかもしれない。

残り10分くらいになったとき、ふと「2/3以上が2なら残りを全部0にできて上手く行くんじゃ?」と気づいて慌てて実装した。途中まで実装してあったのが奏功した(!)。1が0より多いことがあるんだけど、高々1多いだけなので、1が足りないならその1は全部0にできる。で、2のうち1の正しい個数だけ1にすればいい。余った2は既に書いてあった処理で必要なだけ0に変える。確認するためのサンプルもないのに、なんと一発AC。実装の天才か?

D - Manga Market

aがでかいほど先に行きたくなる。まあ両方小さいのがいい。aもbも小さいとあとで行ける。店毎に、いつまでに入店しないといけないかがわかる。最後に店iに行くとすると、それに間に合うように別の店に行くならいつまでに行けばいいかが店i以外の各店についてわかる。店は1秒早く行くと1+a_i秒早く買える。というあたりまで考えて、解ける気がしないので以降Cをやっていた。