Web備忘録 プログラミングを中心に技術的な事柄を忘れないように書き残します。

AtCoder Beginner Contest 160 に参加した記録

AtCoder Beginner Contest 160 に参加した記録
目次

AtCoder Beginner Contest 160 に C# で参加した記録

AtCoder Beginner Contest 160 – AtCoder

ABC160 に参加しました。結果はABCDEの5問ACでした。

E問題が普段より易しく感じたのは数学チックな問題ではなかったからかもしれません。

E問題まで解けたのはよかったのですが、D問題で不用意なWAを重ねたことと、勘違いしてE問題を飛ばしてF問題をEだと勘違いして10分くらい無駄にしてしまったのが心残りです。

パフォーマンスは1284、レートは微々増でした。

問題は総じて面白かったです。振り返ります。

A – Coffee

A – Coffee

ある長さ 6 の英小文字からなる文字列がcoffeeに似ているとは、3 文字目と 4 文字目が等しく、5 文字目と 6 文字目も等しいことを言います。与えられる文字列 S がcoffeeに似ているか判定してください。

制約

  • S は長さ 6 の英小文字からなる文字列である。

言われた通りに与えられた文字列の3文字目と4文字目、5文字目と6文字目を比較します。文字列のインデックスは0から始まるのに注意します。

if (S[2] == S[3] && S[4] == S[5])
{
    Console.WriteLine("Yes");
}
else
{
    Console.WriteLine("No");
}

B – Golden Coins

B – Golden Coins

高橋君は金色の硬貨が好きです。自分が持っている 500 円硬貨 1 枚につき 1000、5 円硬貨 1 枚につき 5 の 嬉しさ を得ます。

高橋君は X 円を持っています。これを高橋君の嬉しさが最大になるように両替したとき、高橋君の嬉しさはいくらになりますか？

(なお、利用できる硬貨は 500 円玉、100 円玉、50 円玉、10 円玉、5 円玉、1 円玉の 6 種類とします。)

制約

  • 0≤X≤109
  • X は整数

嬉しさを最大化するには500円硬貨をできるだけ多くなるように両替し、残りのお金を5円硬貨ができるだけ多くなるように両替すればよいです。なぜなら、500円硬貨1枚と5円硬貨100枚だと、1000>500で500円硬貨のほうが嬉しさが大きいからです。

long ans = X / 500 * 1000;
ans += (X % 500) / 5 * 5;
Console.WriteLine(ans);

制約と問題文をちゃんと確認すれば答えが32bit整数に収まるのは明らかなのですが、面倒なのでlong型(64bit整数)を使っています。入力例3に最大ケースの1000000000があるのでちゃんと入力例を実行すればオーバーフローがないこともわかります。

C – Traveling Salesman around Lake

C – Traveling Salesman around Lake

1 周 K メートルの円形の湖があり、その周りに N 軒の家があります。

i 番目の家は、湖の北端から時計回りに Ai メートルの位置にあります。

家の間の移動は、湖の周りに沿ってのみ行えます。

いずれかの家から出発して N 軒すべての家を訪ねるための最短移動距離を求めてください。

制約

  • 2≤K≤106
  • 2≤N≤2×105
  • 0≤A1<…<AN<K
  • 入力中のすべての値は整数である。
A1---A2---A3
|          |
A6----A5--A4

上のように円周上にA1..ANの家あります。1周KメートルなのでA1からぐるっと1周してA1に戻ってくるまでの距離がKメートルになります。

好きな家からスタートして、すべての家をめぐる最短移動距離を求める問題です。

まずわかることは折り返すという移動方法は無駄だということです。

...A1--A2==A3...

例えば上記のようにA2からスタートしA3で折り返してA2に戻り、A1に行くくらいなら、折り返す先のA3から始めてまっすぐA1に向かったほうが明らかに短い距離で済みます。

なので折り返しをせずに一直線に進むときの最短経路を求めます。

A1------A2
|        |
A4------A3

そうすると、上のような4つの家で考えると、経路は

  1. A1-A2
  2. A2-A3
  3. A3-A4
  4. A4-A1

の4つあります。となるとこの中から1番長い経路を通らない場合が最も短い距離ですべての家を訪問する距離になります。例えばA1-A2が最も長いとすると、A2-A3-A4-A1と順番に訪問するのが最短距離です。

ここですべきなのは A4-A1 の距離です。A1とA4の距離は K-A4+A1 になります。これがわかれば後は実装するのみです。

var maxd = K - A[N - 1] + A[0];
for (int i = 1; i < N; i++)
{
    maxd = Math.Max(maxd, A[i] - A[i - 1]);
}
var ans = K - maxd;
Console.WriteLine(ans);

最も長い隣り合う距離を探し、それをKから引いて答えを求めています。

D – Line++

D – Line++

1 から N までの番号がつけられた N 個の頂点を持つ無向グラフ G があります。 G には、以下のように合計 N 本の辺があります。

  • i=1,2,…,N−1 について、頂点 i と頂点 i+1 の間に辺があります
  • 頂点 X と頂点 Y の間に辺があります

k=1,2,…,N−1 について、以下の問題を解いてください。

  • 整数の組 (i,j)(1≤i<j≤N) であって、 G において頂点 i と頂点 j の最短距離が k であるようなものの数を求めてください

制約

  • 3≤N≤2×103
  • 1≤X,Y≤NX+1<Y
  • 入力はすべて整数である。

2WAをやらかしたD問題です。いかにも典型っぽいにおいがします。いわゆる最短経路問題です。すべての2点間の距離を求める必要があります。

最初に思ったのがワーシャルフロイドを使って全ペアの最短経路を求めればいいじゃんということです。ということでワーシャルフロイドで実装してTLEになりました。

ワーシャルフロイドは頂点数の3乗くらいの計算量で最短経路を頂点全ぺアの間で最短経路を求められます。今回だと頂点数が103なので、計算量が O(10^9) くらいになってTLEします。制約も見たんですがなぜかいけると判断してしまいました。

ということで次の方法として考えたのが、全頂点について2点間の最短経路を求めるという方法です。つまり全頂点について単一始点の最短経路問題として解く方法です。単一始点の最短経路とくれば ダイクストラ のアルゴリズムです。

ダイクストラのアルゴリズムは計算量が O((E+N)*logN) くらい(Nは頂点数、Eは辺数)になるはずです。ということですべての頂点についてこのアルゴリズムを実装すると、O(N*(E+N)*logN) の計算量がかかり、今回は辺数がNなのでこれは O(10^7) くらいなのでTLEせずに行けそうです。

ということで実装しました。

var N = sc.ReadInt();
var X = sc.ReadInt() - 1;
var Y = sc.ReadInt() - 1;

// パスを追加する
var dij = new Dijkstra(N);
dij.Add(X, Y);
for (int i = 0; i < N - 1; i++)
{
    dij.Add(i, i + 1);
}

// 距離の数を数えておく
var ans = new int[N];

// 2点(i, j)を選ぶ
for (int i = 0; i < N; i++)
{
    // 頂点iを始点として最短経路を求める
    var dp = dij.Calc(i);
    for (int j = i + 1; j < N; j++)
    {
        // (i, j) の距離を数える
        ans[dp[j]]++;
    }
}

for (int i = 1; i < N; i++)
{
    Console.WriteLine(ans[i]);
}

X, Y は -1 しておきます。後は問題文の通りにパスを追加しておきます。あとはすべての頂点について最短経路を計算してます。

ダイクストラの実装は以下の記事にあります。

[C#] ダイクストラ法で最短経路を見つけるための実装方法 │ Web備忘録

なお、editorial.pdf によると、(i, j)間の最短経路は数式 min{|j − i|, |X − i| + 1 + |j − Y|, |Y − i| + 1 + |j − X|} で O(1) で求められるみたいです。

youtube の解説放送だとBFSで求めてました。私の解法は冗長すぎるみたいです。

一応コンテスト用のライブラリとして、ダイクストラ、ワーシャルフロイド、ベルマンフォードを用意しています。使える問題があればこれを使って解いてます。

E – Red and Green Apples

E – Red and Green Apples

あなたは、X 個の赤色のリンゴと Y 個の緑色のリンゴを食べようとしています。

あなたは A 個の赤色のリンゴを持っており、美味しさはそれぞれ p1,p2,…,pA です。

あなたは B 個の緑色のリンゴを持っており、美味しさはそれぞれ q1,q2,…,qB です。

あなたは C 個の無色のリンゴを持っており、美味しさはそれぞれ r1,r2,…,rC です。

無色のリンゴは食べる前に着色することで、赤色のリンゴもしくは緑色のリンゴと見なすことができます。

以上のリンゴの中から、できるだけ美味しさの総和が大きくなるように食べるリンゴを選びます。

0 個以上の無色のリンゴに適切に着色したとき、食べる X+Y 個のリンゴの美味しさの総和が最大でいくつになるか求めてください。

制約

  • 1≤X≤A≤105
  • 1≤Y≤B≤105
  • 1≤C≤105
  • 1≤pi≤109
  • 1≤qi≤109
  • 1≤ri≤109
  • 入力はすべて整数である。

一目E問題としては簡単だなという印象でした。実際Difficultyは1000くらいで緑中位でした。

赤と緑だけに限ると、食べる候補はAの美味しさが大きいほうからX個、Bの美味しさが大きいほうからY個です。この中から幾つかを無色に置き換えると美味しさが最大化します。赤緑のりんごX+Y個から小さい順に取り出し、無色のりんごと置き換えて行けばよいです。

今回の問題では何個無色のりんごに着色してもよいので、単純にすべての無色のりんごも食べる候補としてもよいです。

ということでX+Y個の赤緑のりんごと、無色のりんごC個から大きい順にX+Y個選べばよいです。

// すべて大きい順に並べ替えておく
Array.Sort(P);
Array.Reverse(P);
Array.Sort(Q);
Array.Reverse(Q);
Array.Sort(R);
Array.Reverse(R);

// 食べる候補のりんご(X+Y個)の美味しさと無色のりんごすべてをおいしい順に並べる
var pq = P.Take(X)
    .Concat(Q.Take(Y))
    .Concat(R)
    .OrderByDescending(x => x);

// おいしい順にX+Y個の美味しさを求める
var ans = pq.Take(X + Y).Sum();
Console.WriteLine(ans);

コンテスト中は無駄に優先度付きキューとか使ってしまいましたが、こんな風に単純にソートしてればよかったですね。

F – Distributing Integers

F – Distributing Integers

解けなかった問題です。

解説によると、全方位木 dp なるものを使うみたいです。未学習なのでわかりません。

以上。

競技プログラミングカテゴリの最新記事