ARMERIA

Rubyと競技プログラミングの話　AtCoderやCodeforcesの問題解説記事が多め。

Educational Codeforces Round 50 参加記録

Codeforces プログラミング 競技プログラミング

Dashboard - Educational Codeforces Round 50 (Rated for Div. 2) - Codeforces

結果は5完で72位！けっこう不安な問題が多かったのでシステス全部通って良かったです。

f:id:betrue12:20180908194632p:plain

A～Eを振り返ります。

A. Function Height

Problem - A - Codeforces

問題概要

底辺が2で高さが0以上の整数である三角形を n 個作り、合計面積を k にしたい。高さの最大値を最も小さくするように各三角形の高さを決めたとき、その値を求めよ。

制約

1 \le n, k \le 10^{18}

解法

底辺が2なので高さの値がそのまま面積になります。 n 個の三角形にまんべんなく高さを振り分けて合計を k にすると、その最大値は \lceil\frac{k}{n}\rceil でありこれが最適です。

ACコード

B. Diagonal Walking v.2

Problem - B - Codeforces

問題概要

以下のクエリ q 個に答えよ。

二次元平面があり、Mikhailは1回の操作で縦横斜めの近傍8マスいずれかに移動する。始点 (0, 0) 、終点 (n, m) 、操作回数 k が与えられ、始点から終点までちょうど k 回で移動する経路のうち、斜め移動の回数が最大のものを選ぶ時、その回数を求めよ。（または、 k 回で到達できないことを判定せよ。）

制約

  • 1 \le q \le 10^{4}
  • 各クエリ i について 1 \le n_{i}, m_{i}, k_{i} \le 10^{18}

解法

まず、到達できない条件を考えます。 k 回の操作で到達可能な x, y 座標の最大値は k であり、終点座標のどちらか1つでもこれを超えているとアウトです。

斜め移動を行った場合、 x, y 座標ともに偶奇が入れ替わることに着目します。可能であれば全操作で斜め移動をしたいですが、 (0, 0) から斜め移動 k 回だけを行った場合、終点座標は n, m ともに k と偶奇が一致している必要があります。

そうでない場合、例えば k が偶数で n が奇数だった場合は、全操作斜め移動というのは不可能であり、最低1回は x 座標が変わらない移動をする必要があります。 y 座標についても同様です。

このような考察から以下のように答えを求め、実際の移動を構成することができます。

  1. n, m の偶奇がどちらも k とそれぞれ一致する場合、答えは k。各操作での移動量は x, y それぞれについて、和が n, m と一致するように +1 と 1 を並べればよい。
  2. n と k の偶奇が一致し、 m と k の偶奇が一致しない場合、答えは k-1。移動量は x については1.と同様で、 y については1つだけ0を含み、残りは +1 と -1 を並べる。
  3. 2.と逆の場合、同様に答えは k-1 。
  4. n, m どちらも k と答えが一致しない場合、答えは k-2 。 x, y それぞれ移動量に1つずつ0を含む。移動量 (0, 0) は許されていないため、これらは別々の操作に配置されなければならない。残りは +1 と -1 を並べる。

最後の項目は、例えば以下のような移動量となります。 k=5, n=2, m=4 とした例です。

移動回数 x 移動量 y 移動量
1 +1 +1
2 +1 +1
3 +1 +1
4 0 +1
5 -1 0
合計 2 4

※ k=1 で n, m どちらも k と偶奇が一致しないケースが怖くなりますが、そのようなケースは (2, 2) より遠い点であればそもそも到達不可能として弾いていますし、 (n, m) = (0, 0) は制約上与えられないので、大丈夫です。

ACコード

C. Classy Numbers

Problem - C - Codeforces

問題概要

以下のクエリ T 個に答えよ。

正整数 L, R が与えられる。 L 以上 R 以下の整数で、10進数表記したときに0でない数字の個数が3個以下であるものの個数を求めよ。

制約

  • 1 \le T \le 10^{4}
  • 各クエリ i について 1 \le L_{i} \le R_{i} \le 10^{18}

解法

数値がやたら大きい、桁の値についての条件あり、ということで桁DPをやります。桁DPについては既に素晴らしい記事があるのでリンクを貼るだけに留めます。

桁DP入門 - pekempeyのブログ

今回の場合、「見ている桁」「 L を超えていることが確定しているかどうか」「 R 未満であることが確定しているかどうか」「非0の数字の個数」をパラメータとしてDPを組めます。メモ化再帰で書く場合は、非0の数字の個数が3を超えたら即0を返すような実装にすると、条件を満たさない整数をフィルタできます。

または下限の条件を外して、「 0 以上 R 以下で条件を満たす整数の個数」を求めることができるので、 R と L-1 で2回計算して引き算しても良いですね。本番でこっちを思いついていればもっと実装が楽になったでしょう…。

ACコード

D. Vasya and Arrays

Problem - D - Codeforces

問題概要

長さ n の数列 A と長さ m の数列 B があり、これらをそれぞれ以下のように分割したい。

  • 分割した部分列の個数はどちらも K 個である。
  • 全ての i = 1, ..., K について、 A の i 番目の部分列の合計と、 B の i 番目の部分列の合計は等しい。

このような条件を満たす最大の K を求めよ。（またはこのような分割が不可能であることを判定せよ。）

解法

分割が不可能である条件はすぐに分かって、 A, B の総和が一致しないことです。逆に総和が一致する場合は、最低でも K = 1 が解になります。

最適な分割方法を考えます。 A, B の前からの部分列をそれぞれ伸ばしていって、できるだけ小さい値で部分列同士の総和が一致すれば、その点で分割するのが最適です。つまり A, B の部分列のうち、その時点での総和が小さい方を1伸ばして判定、を繰り返すことが最適です。

ACコード

E. Covered Points

Problem - E - Codeforces

問題概要

二次元平面に n 本の線分があり、以下の条件を満たす。

  • 線分の両端点は格子点（座標が全て整数である点）である。
  • どの2線分も同一直線上にない。

少なくとも1本の線分に含まれる格子点の個数を求めよ。

制約

  • 1 \le n \le 1000
  • 全ての線分の端点の座標は -10^{6} \le x, y \le 10^{6} を満たす。

解法

この問題は、以下の2つのことを計算できると解けます。

  1. 線分それぞれについて独立に数えた、その線分に含まれる格子点の個数の総和
  2. 線分同士が交差する格子点と、その格子点を通る線分の個数のリスト

1で重複を気にせず独立に数え、2で数え過ぎた分を引く、という流れです。

まず1についてですが、これは最大公約数が使えます。両端点が格子点で、 x 座標が a 、 y 座標が b 変化する線分に含まれる格子点の個数は \gcd(a, b) + 1 となります。ただしどちらかが0の時は例外で、0でないほうの値を c として c+1 個です。

次に2についてです。交点の座標は連立方程式を解けば良いので計算できますが、コーディングだと色々面倒があります。私は以下の式を使いました。線分同士が平行である場合には0除算が起こったりするので注意。

月の杜工房 - 2直線の交点を求める

「線分の交点が存在して、かつそれが格子点」である場合を抽出します。直線の交点を求め、それが線分上にあってかつ格子点であるかを判定します。これを異なる線分全ペアについて試し、出てきた格子点とその出現回数をmapなどで集計します。

得られた重複格子点それぞれについて、重複分を引いていきます。線分 k 本が交差する格子点である場合、その格子点の出現回数は \frac{k(k-1)}{2} 回であり、引くべき個数は k-1 個です。出現回数から線分の本数を逆算するmapなどを作っておくと、集計した情報から引くべき個数が求められます。

ちょっと大変ですが、これでなんとか解けました…

ACコード

このコードでは線分の交点を求める際に「線分の交差判定をやってから交点座標を求める」という処理をしていますが、解法で書いたように先に交点を求めてしまったほうが楽だと思います。

さいごに

今回でこどふぉのレートが紫になりました！

f:id:betrue12:20180908205340p:plain

こどふぉはレートがガンガン変動しますね。またここから上がったり下がったりするとは思いますが、まだまだ上の色を目指して頑張ります。