ARC112の感想

AtCoder Regular Contest112に参加しましたのでその感想を書いていきます。問題はこちらから。

Tasks - AtCoder Regular Contest 112

結果はこんな感じでした。

2完（2wa）
順位 1483 / 4577
パフォーマンス 1224

いつも通りといった感じでしょうか。適度な難易度の問題をこなし、難しい問題で撃沈する。変わりません。でもまだまだ、こんな感じで良いのかなとは思ってます。言い換えるのであれば、前半問題を安定して解けてきているので、難しい問題に挑戦することができています。挑戦しなければもちろん解けません。そう考えれば進歩です。

とはいうものの、現状に甘えず精進していきます。

では感想行きます。

A問題

l以上、r以下の数で a - b = cを満たす組み合わせ数を求めます。制約をみてとりあえずは、愚直にfor文を回してはだめだと悟りました。ということで、なにかしら考えます。

まず、式を変形して

a = b + c

としました。こうすると、0以上の条件の元で

a >= b, c

であることがわかります。賢い人は元の式でもわかると思いますが、、次にaを変化させたときにb,cの組み合わせはどんな感じで変化するか考えました。入力例1の一番上。

a = 4 (2,2)
a = 5 (2,3),(3,2)
a = 6 (2,4), (3,3), (4,2)

こんな感じ。aが増えるにつれて+1個ずつされてます。あとは、aの範囲です。aの最小値は2*l 、最大値は r です。ということで、項数n = r-2*l+1 個の初項1, 公差1の等差数列の問題に落とし込めました。

あとは、クエリごとに処理するだけです。

ただし、コーナケースとしてr <= 2*l　のときは組み合わせが存在しません。注意！

追記

コーナーケースは r < 2*l ですね。境界はだいじょうぶです。

B問題

整数屋さんでお買い物をします。はじめに整数 b 、c 円を持っており

1円で整数を-1倍
2円で整数を-1

できます。さて、作れる整数の数はいくつでしょう？という問題です。

結論から申し上げますと、コーナーケースに嵌りました。たいそう悩みました。

はじめぱっとみて動的計画法で行けるかなと思いました。がこれも制約が大きくて断念。10^18ですので、かなり大きいです。for文の一重ループでもだめです。

ということで、計算で一発で求める方法を考えました。入力は正の時ばかりを考えていたので、絶対値を小さくすることはできても大きくはできないなあ、と良くわからないことばかり考えてました。

結局、数の絶対値を小さくするには正の状態にて2円払って-1、大きくするには負の状態にて2円払って-1すればいいじゃん、と気づきました。

もし、b >0であれば、負の初期状態は-b、c-1円の状態となります。b<0であれば逆です。

正状態で可能な限り絶対値を小さくする。そして、それを*-1で反転すれば負の数も作れる。また、負状態で絶対値を大きくして最後に*-1すれば正の数も作れます。ただし、反転には1円かかりますので末端の数の時に、1円残っているか注意です。残ってなければ、一つ手前の数までを反転します。

これらの操作により、

正の範囲で作ることのできる数の下限、上限
負の範囲で作ることのできる数の下限、上限

が求まります。あとは、上限 - 下限 +1 かな。を正負どちらもやって答えです。このとき、0も作れるときは足してあげましょう。

ここまでやって、提出したら1つだけwaとなりました。困った、困った。というのも、実装の問題なのですが、1円のみ持っている場合には、少々困ります。c円、またはc-1円が偶数の時に1つ手前まで反転させる、としたのですが、c-1が0のとき、つまりc=1のときは1つ手前というものがありません。

このときは、おとなしくbと-bの2つが答えとなります。

また、さらにb=0、c=1のときは答えは1つだけになります。

この2点に苦しめられました。でも、なんとかコーナーケースを見つけ出して無事AC。よかったよかった。 

追記

自分で見直してみて、何言ってるんだ？となったので、ちょっと加筆します。

b = 10, c = 5の場合、正のスタート地点はb=10,c=5ですね。負のスタート地点は1円払って反転するので、b = -10, c = 4となります。正の場合には-1を使って可能な限り0に近づけます。逆に負の場合には-1にて-11,-12とどんどん小さく（絶対値を大きく）します。

正のとき

10, 9 , 8 まで作れて、1円残る。ということは、末端の8も反転できますね。当然9もできます。

負のとき

-10, -11, -12まで作れます。ただし、お金は余らないので、反転できるのは-11までです。

以上より作れる数字は次のようになります。

8, 9, 10, [11]
[-8,-9],-10, -11, -12 

[ ]は反転して作った数字です。つまり、正の数は8～11の4つ、負の数は-8～-12（逆ですが）の5つとなって合計9個です。

こんな感じですね。このときに、正の値を減らす際には0を跨がないように注意しましょう。max(0, b-c/2)とでもしておけば大丈夫です。あとは、上で述べたように、b=0やc=1のケースに気を付けましょう。

以上です。

C問題

考えましたが、すぐに頭がパンクしました。正直なところ実力不足過ぎて方針が経ちませんでした。

その中でも考えたことを書き出すと、

高橋くんと青木くんのコイン数を持ってdfs
dfsを全パターンやると計算間に合う？
それぞれが、コインの残存状態のグラフを持つとメモリだいじょうぶ？
そもそも、最適な行動選択の評価方法がわからない。青木くんのコイン数？