ABC096

とうとうARCに番号が追いついたね。ABC初の20分切りを目指したが、WAのペナルティで成らなかった(ペナルティがなければ20分を切っていた)。

A - Day of Takahashi

これを「高橋」と呼ぶ概念、(自分は問題ないけど)人によってはわかりにくいんじゃないかと思った。何日あるか?12日に決まってるだろうと思いながら問題を読み進め、ああこれはけっこう厳しいやつだと思った。bの値によって答えが変わる。まあ1月1日からと書いてあるので1月1日は含まれるのだろう(ここでだいぶ気楽になった)。5月5日というコーナーケースもサンプルにあるし、あとはa-(a?b)みたいな感じで書けばいい(間違っていればサンプルに引っかかる)。不等号の種類をしっかり考えて、AC。67秒。そこまで単純な問題でもないが、1分強で無難に切り抜けて好調。(たった1分の思考をこんな長い文章にできるのすごくない?)

B - Maximum Sum

これは一番大きい数を2倍にしていけばいいという典型。3つの数を扱うのが面倒なので、int n = 3; としてn個の整数を受け取る。intの範囲で大丈夫なことを確認し、sortする。a[2]をk回左シフトし、(合計を求める問題であることを確認し)a[i]の和を出力すればいい。合計をfor文で求めるか迷った。for文自体はすぐ書けるが、和を保持する変数を用意するのに時間がかかりそうだと思い、ベタ書きを選択。
2分弱でAC。こうしてみるとA問題より単純じゃないかとすら思えるが、やはりループやソート、シフト、合計と要素がかなり多く、イメージ通り2分は速いほうだと思っていいだろう。

C - Grid Repainting 2

厄介そうな判定問題だが、隣接する2マス、つまりドミノみたいな単純な塗り方なので、そんなに難しくないことが予想できる。ある黒マスに注目すると、隣に黒マスがあれば問題なく塗れる(なければ塗れない、というところまでは詰めてなかった気がする(今考えれば塗れないのは自明だけど))。つまり、全ての黒マスについて、4方向の隣に黒マスが存在するか確認すればいい。
実装は、まず char s[50][51]; の配列を用意していたが、これを char s[52][51] = {}; に変更。これでタテにもヨコにも壁があるようにできた。'#'でないなら'.'や0なので黒マスでない。そういえば、キャンバスからはみ出すようにドミノスタンプを押すことは考えなかったな。s[i][j + 1] == '#' || と書き、それをコピーして4つにし手で修正。そうでないときNoになる。4方向見る必要はない気がしたが、高速コンテスト中なので深く考えず(実際どうなんだろ、シンプルには書けないのかな)。

D - Five, Five Everywhere

合成数とか言ってて、難しそうな構成ゲー。サンプルを見て、「なにカッコつけて素数にしてるんだ、全部偶数にすればよくない?」と思い問題文をよく読むと、素数と書いてある。全部素数じゃないといけないのか!素数の和ってどうなんだろ、合成数になりそうなイメージもあるけど(適当にやってOKという可能性も少し考える)。まあ素数を列挙してみる。55555以下の素数は5637個。しかし、どの5個を選んでもって相当きつい条件だよな。例えばサンプル2のように2を含む和なら必ず偶数になるからいいが、でも一般のNでは2を含まない選び方が大量に現れる。あるいは、全部奇数にすれば合計も奇数になる。3で割ったあまりが1,1,2,2,...みたいにしたら?うまく合わさればいいけど、都合の悪い選び方が普通にあるからダメ。制約はN<=55なので全探索もきつそう(具体的にどう全探索するかのイメージはしていない)。5で割ったあまりなら?あまりを揃えれば、5個足したら5の倍数になる!合計は5より大きいので、問題なく合成数だ。素数が変な性質を持っていると困るので、5で割って1あまる素数を数えた。ちゃんと1/5くらいの素数がそうなっている。カッコつけて4とか2とかあまる素数を使おうかとちょっと思ったが自重。あとは発見した順に出力すればよい。
いやあ。初の20分切りが来たかと思ってしまって、「20分まで少しあるしもうちょっと確認するか?いや少しでも早く」とか5秒くらい考えてそのまま提出し、WAの表示を見る前に間違ってると気づいた(地味に珍しいな)。常に5個しか出力してない。Nを使ってない。出力をサンプルと目視で比較したが、サンプルは桁数が小さい数なので長さが同じくらいに見えてしまったというのもあるか。死ね死ねバカすぎる。やはりメンタルが弱いというか、いざというときに頭が弱い。しかしよくこんな問題思いつくな。解いたあとだと、問題名がヒントに思えてくる。しかしそうか、素数という縛りがないときの「全部偶数にする」は思いついてたんだよなあ。3で割ったあまりも、全部1あまるようにすると合計で2あまってダメというのは無意識に判断してたろうし、5で割ることを考えた瞬間解けたしなあ。400点なんだから難しく考えすぎとも言えるが、まあそういう(点数を解くための情報にする)のは別にやる必要ないよね。はい、コンテスト楽しかったです。