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

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

AtCoder Beginner Contest 168 に C# で参加した記録
目次

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

AtCoder Beginner Contest 168 – AtCoder

ABC168 にC#で参加しました。

結果はABCDの4問ACでレートは微微増でした。減らなかっただけ御の字です。

内容自体はD問題の解法は瞬時に浮かんで実装もライブラリほぼ貼るだけなので余裕こいていたらWAを2回やらかしました。今回はEFがかなり難しめだったらしく、この2WAが効いて青パフォがいなくなりました

C問題がめちゃくちゃ数学で焦りました。が、何とかカンニングしながら解くことができました。

ということで振り返ります。

A – ∴ (Therefore)

A – ∴ (Therefore)

いろはちゃんは、人気の日本製ゲーム「ÅtCoder」で遊びたい猫のすぬけ君のために日本語を教えることにしました。

日本語で鉛筆を数えるときには、助数詞として数の後ろに「本」がつきます。この助数詞はどんな数につくかで異なる読み方をします。具体的には、999 以下の正の整数 N について、「N 本」と言うときの「本」の読みは

  • N の 1 の位が 2,4,5,7,9 のとき hon
  • N の 1 の位が 0,1,6,8 のとき pon
  • N の 1 の位が 3 のとき bonです。

N が与えられるので、「N 本」と言うときの「本」の読みを出力してください。

var N = sc.ReadInt();
var r = N % 10;
switch (r)
{
    case 2:
    case 4:
    case 5:
    case 7:
    case 9:
        Console.WriteLine("hon");
        break;
    case 0:
    case 1:
    case 6:
    case 8:
        Console.WriteLine("pon");
        break;
    default:
        Console.WriteLine("bon");
        break;
}

単純に場合分けを10パターン書きました。if文よりわかりやすいかと思ってswitch文にしましたが、ACできれば何でもいいですね。

B – … (Triple Dots)

B – … (Triple Dots)

英小文字からなる文字列 S があります。

S の長さが K 以下であれば、S をそのまま出力してください。

S の長さが K を上回っているならば、先頭 K 文字だけを切り出し、末尾に … を付加して出力してください。

WordPressでこんな処理やりたくて調べたことがあったような気がします。まあ、なんにせよ場合分けです。

var K = sc.ReadInt();
var S = sc.ReadStr();
if (S.Length <= K)
{
    Console.WriteLine(S);
}
else
{
    var ans = new string(S.Take(K).ToArray()) + "...";
    Console.WriteLine(ans);
}

文字数がK以下の場合はそのまま出力して、Kより大きい場合は先頭K文字をちぎって、後ろに … を付けてます。

C – : (Colon)

C – : (Colon)

時針と分針の長さがそれぞれ A センチメートル、B センチメートルであるアナログ時計を考えます。

時針と分針それぞれの片方の端点は同じ定点に固定されており、この点を中心としてそれぞれの針は一定の角速度で時計回りに回転します。時針は 12 時間で、分針は 1 時間で 1 周します。

0 時ちょうどに時針と分針は重なっていました。ちょうど 時 M 分になったとき、2 本の針の固定されていない方の端点は何センチメートル離れているでしょうか。

制約

  • 入力はすべて整数
  • 1≤A,B≤1000
  • 0≤H≤11
  • 0≤M≤59

まごうことなき数学だと思います。。。

最初は針の端点の座標を求めようと思いましたがうまくいきそうにないので、余弦定理を使う方針に切り替えました。

editorial.pdf を見る限り、方針もあってました。

// 針がそれぞれ1周の何パーセントくらい動いているかを求める。
var h = (H * 60.0 + M) / 720.0;
var m = M / 60.0;
// 差から1周の何パーセント分開いているかを求める。(小さいほうの角度を使う)
var p = Math.Abs(h - m);
p = Math.Min(p, 1 - p);
// 角度にする
var ang = p * 360;
// ラジアンにする
var rad = ang * Math.PI / 180;
// 余弦定理を使う
var ans = A * A + B * B - 2 * A * B * Math.Cos(rad);
ans = Math.Sqrt(ans);
Console.WriteLine(ans);

D – Water Bottle

上の問題で角度を問う問題が解けなかったので、いろいろ復習してたんですが、プログラムに使う角度はラジアンにする必要があるというのは知ってました。余弦定理もギリギリ覚えてたので助かりました。誤差は知りません。

10分ちょっとで解けたのでとりあえず安心してました。

D – .. (Double Dots)

D – .. (Double Dots)

あるところに、洞窟があります。洞窟には N 個の部屋と M 本の通路があり、部屋には 1 から N の、通路には 1 から M の番号がついています。通路 i は部屋 Ai と部屋 Bi を双方向につないでいます。どの 2 部屋間も、通路をいくつか通って行き来できます。部屋 1 は洞窟の入り口がある特別な部屋です。

洞窟の中は薄暗いので、部屋 1 以外の各部屋に 1 つずつ道しるべを設けることにしました。各部屋の道しるべは、その部屋と通路で直接つながっている部屋の 1 つを指すように置きます。

洞窟の中は危険なので、部屋 1 以外のどの部屋についても以下の条件を満たすことが目標です。

  • その部屋から出発し、「いまいる部屋にある道しるべを見て、それが指す部屋に移動する」ことを繰り返すと、部屋 1 に最小の移動回数でたどり着く。

目標を達成できる道しるべの配置が存在するか判定し、存在するならばそのような配置を 1 つ出力してください。

制約

  • 入力はすべて整数
  • 2≤N≤105
  • 1≤M≤2×105
  • 1≤Ai,Bi≤N (1≤i≤M)
  • Ai≠Bi (1≤i≤M)
  • どの 2 部屋間も、通路をいくつか通って行き来できる

これは単一始点の最短経路問題として解けば、あとは経路を適当に復元するだけです。ということでダイクストラのライブラリを引っ張ってきて実装しました。

冷静になると、普通にBFSしてもよい問題でした。

どの2部屋もつながっているという制約があるので、結局のところ道しるべは必ず配置できます。”No”を出力するパターンはないです。

ということで実装です。

var N = sc.ReadInt();
var M = sc.ReadInt();
var dij = new Dijkstra(N);
var G = new List<int>[N];
for (int i = 0; i < N; i++)
{
    G[i] = new List<int>();
}
for (int i = 0; i < M; i++)
{
    var a = sc.ReadInt();
    var b = sc.ReadInt();
    a--; b--;
    dij.Add(a, b);
    dij.Add(b, a);
    G[a].Add(b);
    G[b].Add(a);
}
// 頂点0からの最短経路を求めておく
var dist = dij.Calc(0);
// 頂点1..N-1についての答えを求める
var list = new List<int>();
for (int i = 1; i < N; i++)
{
    var d = dist[i];
    if (d == Dijkstra.INF)
    {
        // どの部屋もつながっているのでここには到達しない
        Console.WriteLine("No");
        return;
    }
    // 頂点iについて、道しるべを決める
    foreach (var next in G[i])
    {
        // nextから頂点0までの距離がいまより1だけ小さいとき
        // 道しるべとしてnextを記録する
        if (dist[next] + 1 == d)
        {
            list.Add(next);
            break;
        }
    }
}

Console.WriteLine("Yes");
foreach (var ans in list)
{
    Console.WriteLine(ans + 1);
}

ダイクストラ本体は以下の記事からどうぞ。微妙に関数名が違いったりしますが機能自体はおおよそ同じです。

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

WAをやらかしたのは、グラフの入力を双方向に取らなかったところと、道しるべを記録したあと break でなく continue したことです。sampleをさぼったのは舐めてました。

BFSで解くと以下のようになります。

var N = sc.ReadInt();
var M = sc.ReadInt();
var G = new List<int>[N];
for (int i = 0; i < N; i++)
{
    G[i] = new List<int>();
}
for (int i = 0; i < M; i++)
{
    var a = sc.ReadInt();
    var b = sc.ReadInt();
    a--; b--;
    G[a].Add(b);
    G[b].Add(a);
}
var q = new Queue<(int, int, int)>();
var visited = new bool[N];
visited[0] = true;
var michishirube = new int[N];
q.Enqueue((0, -1, 0));
while (q.Count > 0)
{
    var t = q.Dequeue();
    var now = t.Item1;
    var prev = t.Item2;
    var d = t.Item3;
    foreach (var next in G[now])
    {
        if (visited[next]) continue;
        visited[next] = true;
        michishirube[next] = now;
        q.Enqueue((next, now, d + 1));
    }
}
Console.WriteLine("Yes");
for (int i = 1; i < N; i++)
{
    Console.WriteLine(michishirube[i] + 1);
}

こっちのほうがミスが少なかった気がします。

E問題はサンプル2が合わせられなくて断念しました。

以上。

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