蟻本読書会決意表明とウォーミングアップ

Contents

1 AtCoderに挑戦中
2 蟻本を読んでみる
3 ウォーミングアップ

AtCoderに挑戦中

現在、AtCoderに挑戦しているのですが、なかなかレーティングが上がりません。プログラミング練習サイトはたくさんありますが、そのなかでもAtCoderは難しいことで知られています。

AtCoderのコンテストに参加すると成績に応じてレーティングが変化します。それとともに「色」が変化します。400ごとに色がついていて、上のランクから赤・橙・黄・青・水・緑・茶・灰・黒というなってます。一度でもコンテストに参加すれば灰色になります。そして2024/04/12段階の鳩のランクは「灰色」です（トホホ）。

AtCoder株式会社代表取締役社長高橋直大さんは AtCoder（競技プログラミング）の色・ランクと実力評価、問題例 – chokudaiのブログにおいて赤・橙・黄・青・水・緑・茶・灰がどのような人か次のように説明しています。

灰色は参加すれば誰でもなれるので意欲以外の保証はなし。
学生で茶色なら優秀だがエンジニアとしてはちょっと物足りない。派遣とかで来たエンジニアが茶色あれば一安心。
緑あれば大抵の企業でアルゴリズム力は十分。AtCoder的には決して上位ではないが、他社評価サイトなら最高評価。
水色だと基礎的なアルゴリズム処理能力については疑いのないレベル。
青以上は一部上場のIT企業でも、一人もいないことが結構あるレベルになる。
黄色からは化け物。競プロの問題を解く機械だと思っておけば良い。
橙はあたまおかしい。
赤はもうなんか世界大会とかに招待されたりする。

上位陣の成績をみてみると名前が赤やオレンジ色で書かれた「化け物」「あたまおかしい」人が上位を占領しています。ABC（AtCoder Beginner Contest）の制限時間は100分なのですが、全問正解するためには1問あたり10分で解かなければなりません。鳩には到底かなわない実力者ばかりです。

ということで、当面は高望みせずに基礎学力を高めるということでアルゴリズムと数学　演習問題集とか競技プログラミングの鉄則などに取り組んでいます。どのようなコードを書けばいいのかを公開するとこのブログのコンテンツにも使えて一石二鳥なのですが、ちょっと困ったことがあります。

ルールによると「コンテスト中にネット上で問題のネタバレはご遠慮ください」。

コンテスト中におけるSNSの利用についても、「面白かった」などの感想は問題ないが、「面白かった。A問題はox法を使って解いた」「ox法でA問題がTLEだった」「A問題はあることに気がつけば簡単だった」というものは問題に言及する内容を含んでいるので不可とのこと。

逆にいえばコンテストが終わってしまえば解法や解説が公開されるため問題ありません。ところがアルゴリズムと数学　演習問題集とか競技プログラミングの鉄則は常設中のコンテストで現在も開催中です。したがってネタバレとなる記事は書けないということになります。

あと競プロ典型 90 問は「常設中のコンテスト」カテゴリにあるけど、「コンテストは終了しました。今後は「過去問」としてお楽しみください」とあるので、これはいいのかな？ただ問題が難しすぎるのと問題が難易度順にもジャンル順にも並んでいません。これはこれで取り組む価値があるのですが、現在の鳩のレベルでは難しいので今後の課題ということで・・・。

蟻本を読んでみる

ではどうするか？この前ポチった蟻本があるじゃないか！ということで当面、蟻本読書会をやってみたいと思います。

目次は以下のとおり

1-1 ～ 1-5 競技プログラミングの説明など（省略）
1-6 気楽にウォーミングアップ

2-1 すべての基本 “全探索”
2-2 猪突猛進！ “貪欲法”
2-3 値を覚えて再利用 “動的計画法”
2-4 データを工夫して記憶する “データ構造”
2-5 あれもこれも実は “グラフ”

3-1 値の検索だけじゃない！ “二分探索”
3-2 厳選！頻出テクニック (1)
3-3 さまざまなデータ構造を操ろう
3-4 動的計画法を極める！
3-5 水を流して問題を解く “ネットワークフロー”
3-6 平面・空間を扱う “計算幾何”

4-1 より複雑な数学的問題
4-2 ゲームの必勝法を編み出せ！
4-3 グラフマスターへの道
4-4 厳選！頻出テクニック (2)
4-5 工夫を凝らして賢く探索
4-6 分けて解いてまとめる！ “分割統治法”
4-7 文字列を華麗に扱う

あとこんな記事もあったので参考にさせていただきます。

AtCoder 版！蟻本 (初級編)

ウォーミングアップ

ウォーミングアップでは「三角形」に関する問題が掲載されています。AtCoderだとこんな問題が掲載されています。

B – Making Triangle

1, …, N の番号がついた N 本の棒があります。棒 i の長さは L_i です。このうち、三角形を作ることのできるような長さの異なる 3 本の棒を選ぶ方法は何通りあるでしょうか。

入力
N
L_1 L_2 L_3 … L_N
（ただし 1 ≦ N ≦ 100, 1 ≦ L_i ≦ 10^9, すべて整数）

注意点として使う棒の長さは異なるものでなけれならないけど、同じ長さであっても別の棒はそれぞれ別にカウントしなければなりません。たとえば「長さ 3, 4, 5 の棒が 2 本ずつ合計 6 本」ある場合は 3, 4, 5 の三角形をつくる選び方の組み合わせは全部で 8 個あります。

配列のなかからどの要素を3つ選ぶかを三重ループにして決めています。同じ棒を選ぶことはないので内側のループは b は 0 ではなく a から、c は b から開始しています。3つの辺から三角形をつくることができる条件は「1辺よりも残りの2辺の和のほうが大きい」です。この比較を1回で終わらせるために配列を値が小さい順にソートしています。これなら vs[a] + vs[b] > vs[c] であるなら三角形をつくることができると判断できます。

using System;
using System.Linq;

class Program
{
    static void Main()
    {
        int N = int.Parse(Console.ReadLine());
        int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

        vs = vs.OrderBy(_ => _).ToArray();

        int ans = 0;
        for (int a = 0; a < N; a++)
        {
            for (int b = a; b < N; b++)
            {
                for (int c = b; c < N; c++)
                {
                    if(vs[a] == vs[b] || vs[a] == vs[c] || vs[b] == vs[c])
                        continue; // 同じ長さのものを選んではいけない

                    if (vs[a] + vs[b] > vs[c])
                        ans++;
                }
            }
        }
        Console.WriteLine(ans);
    }
}

using System;

using System.Linq;

class Program

{

static void Main()

{

int N = int.Parse(Console.ReadLine());

int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

vs = vs.OrderBy(_ => _).ToArray();

int ans = 0;

for (int a = 0; a < N; a++)

{

for (int b = a; b < N; b++)

{

for (int c = b; c < N; c++)

{

if(vs[a] == vs[b] || vs[a] == vs[c] || vs[b] == vs[c])

continue; // 同じ長さのものを選んではいけない

if (vs[a] + vs[b] > vs[c])

ans++;

}

Console.WriteLine(ans);

}

Ants (POJ No.1852)

蟻本の冒頭にある問題です。これが蟻本の名前の由来だという説もあります。

Ants は以下のような問題です。

長さLcmの竿の上をn匹のアリが毎秒1cmのスピードで歩いています。アリが竿の端に到達すると竿の下に落ちていきます。
竿の上は狭くてすれ違えないので、二匹のアリが出会うと、それぞれ反対を向いて戻っていきます。
各アリについて、現在の竿の左端からの距離x_iはわかりますが、どちらの方向を向いているのかはわかりません。
すべてのアリが竿から落ちるまでにかかる最小の時間と最大の時間をそれぞれ求めなさい。

入力
L
n
x_1 x_1 x_1 … x_n
（ただし 1 ≦ L ≦ 10^6, 1 ≦ n ≦ 10^6, 0 ≦ x_i ≦ L）

アリがぶつかると反転して移動することになるので一見すると難しそうな問題です。ところがそれぞれのアリを区別しなければぶつかったアリ同士が反転しないでそのまますれ違ったとしても結果は同じです。

するとアリが竿から落ちるまでにかかる時間を最小にするのであればそれぞれのアリは最初の位置からみて近い方の端に向かって移動すればよいし、最大にしようとするなら遠い方の端に向かって移動すればよいのです。

using System;
using System.Linq;

class Program
{
    static void Main()
    {
        int L = int.Parse(Console.ReadLine());
        int n = int.Parse(Console.ReadLine());
        int[] xs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

        int[] maxs = new int[n];
        int[] mins = new int[n];
        for (int i = 0; i < n; i++)
        {
            int x = xs[i];
            mins[i] = Math.Min(x, L - x); // 近い方の端までの距離
            maxs[i] = Math.Max(x, L - x); // 遠い方の端までの距離
        }
        // それぞれの最大値がすべてのアリが竿から落ちるまでにかかる最小または最大の時間
        Console.WriteLine(mins.Max());
        Console.WriteLine(maxs.Max());
    }
}

using System;

using System.Linq;

class Program

{

static void Main()

{

int L = int.Parse(Console.ReadLine());

int n = int.Parse(Console.ReadLine());

int[] xs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

int[] maxs = new int[n];

int[] mins = new int[n];

for (int i = 0; i < n; i++)

{

int x = xs[i];

mins[i] = Math.Min(x, L - x); // 近い方の端までの距離

maxs[i] = Math.Max(x, L - x); // 遠い方の端までの距離

}

// それぞれの最大値がすべてのアリが竿から落ちるまでにかかる最小または最大の時間

Console.WriteLine(mins.Max());

Console.WriteLine(maxs.Max());

}

蟻本読書会決意表明とウォーミングアップ

AtCoderに挑戦中

蟻本を読んでみる

ウォーミングアップ

鳩でも分かるC#管理人からのお願い

コメントについて

管理人のモチベーションアップのために

コメントをどうぞ