ラベル プログラミング_競プロ の投稿を表示しています。すべての投稿を表示

2020年4月22日水曜日

【C#】競プロ用にSegmentTreeのライブラリを作ったよ！

SegmentTreeってセグメント木とかセグ木とか色々に呼ばれているので検索するの苦労しません？
あなたはどのワードでここに辿り着きましたか？

先にコードを載せます。超普通のセグ木になります。

using System;
using System.Collections.Generic;
using System.Linq;
 
namespace Library
{
    public class SegmentTree<T> where T: struct
    {
        private readonly T[] data;
        private int size = 1;
        private T defaultValue;
        private Func<T, T, T> function;
 
        public SegmentTree(int size, T defaultValue, Func<T, T, T> function)
        {
            while(this.size < size) this.size *= 2;
            this.defaultValue = defaultValue;
            this.function = function;
            data = Enumerable.Repeat(defaultValue, this.size * 2 - 1).ToArray();
        }
 
        // [a, b)
        public T RangedValue(int a, int b) { return RangedValue(a, b, 0, 0, size); }
 
        private T RangedValue(int a, int b, int now, int l, int r)
        {
            if (r <= a || b <= l) return defaultValue;
            if (a <= l && r <= b) return data[now];
 
            return function(RangedValue(a, b, now * 2 + 1, l, (l + r) / 2), RangedValue(a, b, now * 2 + 2, (l + r) / 2, r));
        }
 
        public T this[int index]
        {
            get
            {
                return data[size + index - 1];
            }
            set
            {
                index += size - 1;
                data[index] = value;
                while (index > 0)
                {
                    index = (index - 1) / 2;
                    data[index] = function(data[index * 2 + 1], data[index * 2 + 2]);
                }
            }
        }
    }
}

以下工夫した点

Genericsの型であるTに値型の制約を与えた
indexによるアクセスでより直感的に
ぐう短い

2020年3月31日火曜日

「Atcoderで水色になるまでにやったこと」を書きます

グラフが歪すぎる。

自己紹介

名前：アスラト
言語：C#
コンテスト出場回数：22回
入水時点のACCount：330

画像の通り競プロはやったり辞めたりしていました。
個人ではほとんどありませんがゲーム製作でプログラムを書いています。
ちなみに製作でのC#は二年ほどのブランクがあります。実質競プロ専用言語。

やったこと

大きく三段階に分かれています。

時系列順に並べましたが、「この順番でやるべき」という意味ではありません。

AtCoderProbremsで古い時期のC問題と簡単なD問題を毎日解いた
125番目以前でD問題のDifficultyが水〜青色なABCを時間制限をつけて解いた
「レッドコーダーが教える、競プロ・AtCoder上達のガイドライン」を半分くらい解いた

上の三点とC#の話について書きたいと思います。

AtCoderProbremsで古い時期のC問題と簡単なD問題を毎日解いた

具体的にはABC64以前のC, D問題を1日1問以上を目安に解きました。
Streak数は驚異の41！すごい！ほめて！

誰も褒めないので私が褒めます！えらい！
大学で帰る前に図書館に行って問題を解いてから帰るという生活を送っていたおかげですね。
このように競プロを強制的に触れる環境を作り習慣化させました。
最初のアプローチとしては正しかったと思います。

一方でアルゴリズムに関しては大学の授業程度の知識しかありませんでした。(蟻本未購入勢)
過去問中に知らない解き方が出てきたらグーグルで検索する......といったことを繰り返し行ってきました。
これは非常に無駄が多くお勧めできません。
先に体系立ったアルゴリズムの学習または速解きの練習から始めることをお勧めします。

125番目以前でD問題のDifficultyが水〜青色なABCを時間制限をつけて解いた

古い時期でそこそこ簡単なC, D問題が枯渇し始めてからこちらに移行しました。
AtCoderのバーチャルコンテスト機能を利用してA〜D問題まで解きました。
こちらの目的は専ら速解きです。

特に茶〜緑色で
「D(orE)問題は無理！しかもC(orD)問題で大量に時間を消費した！」
という時はぴえん😭な結果になることを身を持って体験してきたはずです。
ある程度解けるようになったらどこかで速解きの練習はした方がいいと思います。
あとバーチャルコンテストで私と対戦しましょう！

「レッドコーダーが教える、競プロ・AtCoder上達のガイドライン」を半分くらい解いた

レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】

みなさんこれをやりましょう。学習に向いている問題ばかりです。
ちなみに「半分」である理由は、解いている最中に水色に昇格しただけで深い理由はありません。
これのおかげかは分かりませんが、解き始めた3/5辺りからレートが急上昇したのでみなさんやりましょう。

振り返って

振り返ると「体系的学習→演習」の流れを完全に崩してしまった気がします。
蟻本等で勉強した上で上述のリンクをクリアし、その後速解きの練習をすると要領良く水色に昇格できると思います。
ただ1, 2番目の演習を先であっても私の血肉になりえたことはここに明言させていただきます。

C#はぶっちゃけどうなの？

C#の良い点はそこそこ速くて綺麗に書けることです。
LINQの暴力だけでなく、入力部分を工夫するだけでもC++より簡潔に記述できます。（関連：【C#】手抜き競プロライブラリ〜入力編〜）
其を侮る勿れ、短く書け得ることはそれだけ伸び代を残していることを意味します。
C++よりも一歩先のレートに足を伸ばせるかもしれませんね。実際私も水色になれたわけで。

とはいえ、速さ及びライブラリの充実度においてC++には到底叶いません。
速さは言わずもがな、C#には優先度付きキューも平衡二分木も順列列挙も存在しません。
加えてどマイナーな問題を解くとC#で提出している人が極端に減ります。

ではなぜC#を使うのか。理由は「使えた」ことと「関数型」です。
そもそも「関数型を使って綺麗に速くかけるようになりたい」という願望から私の競プロ生活が始まりました。
そして新たに言語を学ぶ気になれなかった私は、当時使えたC, C#, Java, JavaScriptの中からLINQがあるC#を選択したという歴史的な背景が存在します。

最後にC#もとい競プロの言語についてめちゃくちゃ良いこと言うので聞いてください。

競プロをする目的が競プロならC++にしろ。そうでないならなんでも良い。

これが私の結論です。
何をするにも言えますが、目的や目標の明確化を心がけると良いと思います。

今後

私の当初の目標は水色になることでしたが、まだ上昇の余地が残されているのでもう少しだけ続けてみようと思います。
青に昇進できてもできなくてもまた記事を書きたいですね。

P.S.
水色に昇進することを入水って表現するのすこ

2019年12月27日金曜日

【C#】手抜き競プロライブラリ〜入力編〜

最近競プロを再開しました。
競プロやってたって言えたらかっこいいじゃないですか。
目標は水色。

今日は基本中の基本かつ速度の大幅な向上を期待できる入力のライブラリをご紹介します。

といってもStreamを使ってどうたらこうたら......とかはしないです。

あくまで自分の理解を越えない範囲で、コスパの良い書き方を目指しました。

class Input {
    static IEnumerator<string> enumerator = new string[] { }.AsEnumerable().GetEnumerator();
 
    public static string Line => Console.ReadLine();
 
    public static string[] StrArr => Line.Split(' ');
 
    public static int NextInt => int.Parse(NextWord());
 
    public static long NextLong => long.Parse(NextWord());
 
    public static List<int> IntList => StrArr.Select(int.Parse).ToList();
 
    public static List<long> LongList => StrArr.Select(long.Parse).ToList();
 
    public static string NextWord() {
        while (!enumerator.MoveNext()) {
            enumerator = StrArr.AsEnumerable().GetEnumerator();
        }
        return enumerator.Current;
    }
}

うーん、NextWordだけ"()"が必要なあたりすごく手を抜いてる感が出てますね。

NextInt等はJavaのScannerに挙動が近いです。(Scannerの宣言ないけど)

var a = NextInt;
Console.WriteLine(a);

こんな感じ。

賢い点はenumeratorの初期値に空のstringを入れていること。
これによってwhile文の条件式が簡潔に済ませられます。

コードはご自由にどうぞ。間違いがあったらごめんね。

2018年5月13日日曜日

AtCoder Beginner Contest 097 に初心者ながら参加しました

アスラトです。

「もっとコードを綺麗に書きたいなー」と漠然と考えるようになってきた今日この頃。
アルゴリズムを勉強しようと思い立ちそれ関係の本を探していました。
が、その中でAtcoderというアルゴリズム学習に適したサイトを見つけたので
ワイ「ま、後で考えましょ」ﾎﾟｰｲ
......ということでそれ関係の本は後回しにしてとりあえず参加してみました。

今日はその結果と感想です。ちなみにC言語で書きました

A問題

A問題はそんなに難しくはなかったです。(なおかかった時間)

絶対値の関数ってなんだっけ?
大きい方を出力する関数って何をincludeしなきゃいけないんだっけ？
ファ!?Xcodeがなんかおかしい

ということを調べていたらA問題に13分ぐらいかかってしまいました。悲しい

B問題

「正整数 X 以下の最大のべき乗数を求めてください。」という問題です。

リンク先に書いてありますが、べき乗数の底と指数は任意です。

これを私は平方数だと勘違いしていました。

だって入出力例がうまく通っちゃったんですもの...

aという変数に入力されたデータを代入したら、
printf("%d", (int)sqrt(a)*(int)sqrt(a));
こうやれば終わりじゃね？はっやーいと思って提出したら弾かれました。

問題文はしっかり見ような(戒め)

C問題

A,B共に問題を見たらすぐに道筋が思いつきましたがCはそうはいきませんでした。

途中でC言語きつくね？C＃かjavaでlistを使ったらいけそう...？とか考えましたがやめました。
夕食食べてなかったんですよ。残り時間が半分になったところで夕食にしました。

...で戻ってきたのはコンテスト終了直前。当然できるはずもなく。
悲しいというかそれはそうという感想。

まとめ

コンテストに関しての感想は

問題文はしっかり読もう
C問題からはもう少し典型問題勉強してから挑みたい
C言語の基礎がよくわかっていないと思った
先に夕食を食べよう

やってみて分かったこともあります。
が、何よりアルゴリズムの勉強をしようというやる気が生まれたのは大きかったです。
皆様も是非。

登録: 投稿 (Atom)