2019-12-14

AtCoder黄色になりました

モジャンボ@Jumbo_kpr
JWC(じゅっぴーワールドカンパニー)で宴( 'ω')۶ｯｯｯｨｨｨｨｲｲｲｲﾖｯｼｬｱｱｱｱｱｱｱｧ!!!! https://t.co/4g33jCqIpP
2019/12/09 00:24:27

じゅっぴー@juppyjappy
これは黄色になったのが嬉し過ぎて、人の家でぬいぐるみ遊びするモジャンボ(@Jumbo_kpr ) https://t.co/UvGes6Jrmh
2019/12/09 01:14:38

ぴーよ@競プロ@ywmt_kpr
もにゃ黄色おめでとう通話の様子 https://t.co/sbuspAOpqR
2019/12/09 03:27:43

AtCoder Beginner Contest 147で黄色コーダーになりました！競プロを始めたときは自分が黄色になれるとは思いもしませんでしたし、長い道のりでしたが続けてよかったです。
ということで、ずっと書きたかった色変記事を書きたいと思います。「○○色になるまでにやったこと」系の記事は自分が水～青の時にたくさん読んで参考にさせてもらったので恩返しの意味も込めつつ、同じように青～黄色を目指す人の参考になれば嬉しいです。

解いた問題数など

AtCoder ProblemsのユーザーページとAtCoder Scoresの精進グラフです。
AtCoderのほかにCodeforcesで292問、AOJで11問、yukicoderで26問、TopCoder SRMを50問ほど解いたので合わせて1250問くらいになります。

振り返り記事を書くのはこれが初めてなので、競プロを始めたところから時系列に沿って振り返ります。

競プロを始めるまで(~2018年2月)
プログラミングに初めて触れたのは、学部1年の秋学期に受講した「アルゴリズム入門」という講義がきっかけでした。言語はRubyで、プログラミング未経験者向けに0から優しく教えてもらいました。講義の後半でDP(nCrをパスカルの三角形で求めるやつ)にも触れていましたが、ふーんって感じでまだ面白さはよく分かりませんでした。その後、巷で話題のAtCoderをやってみたいと思い、友人に聞くとRubyよりC++が良いと言われたのでC++に乗り換えて競プロを始めることにしました。はじめの環境構築で死ぬほどつまずいたのを覚えています。(パスを通すって何？みたいなレベルでした)

緑色になるまで(~2018年6月)
ABCの過去問を解いてC++の文法を勉強しつつ予定が合えばコンテストに出る、みたいな感じで緑までは割とスムーズにいけました。またこの頃に蟻本を買いましたが、STLについての説明が端折られていたのでググりながら読むのが少し辛かったです。今だったら「AtCoder Programming Guide for beginners (APG4b)」をやるといいと思います。

水色になるまで(~2018年10月)
蟻本の初級編を一通り読んで中級編以降はつまみ食いしつつコンテストに参加していました。精進グラフの傾きを見ればわかるように、水になるまではあまり熱心に取り組んではいませんでした。けんちょんさんのAtCoder版蟻本が神なのでとりあえずこれの初級編をやるのがおすすめです。

青色になるまで(~2019年6月)
グラフを見ての通り水色前半で半年くらい停滞してしまいましたが、この期間にもちゃんと実力はついていたような気がします。やったこととしては、

・AtCoder300点埋め
とてもいい練習になりました。典型的なアルゴリズムの実装が早くなったと思います。

・AtCoder400点埋め
このレベルになると分からない問題が多く、自分はすぐに解説を見てACしていました。
(解説ACの是非については人によって意見が分かれるところですが、個人的には解けそうにない問題を考え続けるのが苦痛なのとできるだけ多くの問題に触れたいので、今でも少し考えてさっぱりわからなければすぐに解説を見ています。)

・AtCoder500~600点で解けそうな問題を選んで解いた
点数の割に難しい問題(いわゆる地雷？)にぶつかると心が折れがちだったのでAtCoder Scoresの「対戦者」にフレンドを何人か入れて、多く通されている問題を選んで解きました。

・Codeforcesを始めた
コンテストの頻度が多くレートの変動も大きいのでスリリングな楽しさが味わえます。
AtCoderと比べると日本人が少ない海外サイトでシステムも独特なので敷居が高く感じるかもしれません。ぴーよさんとNoiminさんのブログで詳しく紹介されているのでこれらを読むと雰囲気がつかめると思います。

あと、今年の春にsimとjuppyとチームを組んでICPCに出場することになったのですが、これがモチベーションを上げてくれました。チーム結成当時は確か全員水色だったのが国内予選の時には全員青になっていたので相当効果があったんじゃないかと思います。

黄色になるまで(~2019年12月)
青になってからやったこととしては、
・TopCoder SRM Div1 Easy Hunting
TopCoderというコンテストサイトの問題を50問くらい解きました。難易度はAtCoderで300~700くらいの印象でちょうどいい練習になりました。

・Codeforcesのバーチャルコンテスト
これが一番力がついたと思います。
vjudgeという、いろいろなコンテストサイトから問題を集めてバーチャルコンテストを開けるサイトを使って定期的にCodeforcesのバチャ(バーチャルコンテストの略)をやりました。他の人と競うので一人で問題を解くよりも集中できてよかったです。もし興味があればグループに招待するので気軽にお声がけください。

また、自分のレートと同じくらいの難易度(Difficulty 2000前後)の問題を4問集めて2時間で解くバチャ(Mojumbo Practice)もやっていました。これは大体ABCのE~Fくらいの難易度なのですが、AtCoderだけだとどうしても数が足りなかったので練習量を増やすのにちょうどよかったです。(このくらいの難易度の問題をたくさん解いてABC-Eを早解きできるようになれば黄色が見えてくると思います。)

さいごに
今後の目標としては年内にCodeforces薄橙*1(やばそう)、来年中にAtCoder橙(ratedコンテストがたくさんほしい)を目指して頑張りたいと思います。
あと、来年のICPCはチーム全員暖色で行こうみたいな話をした覚えがあるので、チームメイトに圧力をかけていこうと思います。

最後まで読んでいただいてありがとうございました。

*1 2019/12/14追記: 達成しました！！！

モジャンボ@Jumbo_kpr
Wow! CoderMojumbocompeted in Codeforces Round #606 (Div. 1, based on Technocup 2020 Elimination Round 4) and gain… https://t.co/Y7mbF9gQYc
2019/12/14 23:18:40

2019-10-20

AtCoder Beginner Contest 143-F 「Distinct Numbers」

競技プログラミング

こんにちは、本日21歳になりました。モジャンボです。
今回のABCで初めて橙パフォをとることができたのでウキウキでF問題の解説を書きたいと思います。

問題文

考えたこと
K=1の時は答えはN回で、Kを大きくすると操作回数は単調に減っていく
Kを1ずらしたとき、あるいは操作回数を1ずらしたときに何かいい性質ないかな～(うまく差分更新的なことができたらうれしい)
操作回数をcとしたとき、重複がc枚以下のカードは脳死で使える(それぞれの操作で一回ずつ使えばいいので)
重複がc以上のカードは、そのうちのc枚を使える(上と同じ理由)
このような、使えるカードの枚数の合計がK*c以上ならc回操作を行える！！！
初め(K=1のとき)は操作回数cはN回でN枚全部使える。そこからKを大きくすると操作回数を減らさなきゃいけなくなる。
cを1小さくするときに、重複がc枚以上のカードはそれまでc回使えていたのがc-1回しか使えなくなるので、その分使えるカードの枚数を減らせばいい(これは累積和を使えばO(1)でできる)

解法
上で書いたようなことをそのまま実装します。
Kを1からNまで回して、各Kに対して、使えるカードの枚数の合計がK*c以下になるまでcを減らし続ける
cがNから0まで単調に減り続ける(cの更新はN回だけ行われる)のでO(N)で解ける

提出コード

#include<iostream>
#include<vector>
using namespace std;
int num[300030];//num[x]=x枚以上重複しているカードの種類数
int cnt[300030];//cnt[x]=数xのカードの枚数
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
int N; cin >> N;
for (int i = 0; i < N; i++) {
int x; cin >> x;
x--;//0-indexedにする(なんとなく)
cnt[x]++;
}
for (int i = 0; i < N; i++) {
num[cnt[i]]++;
}
for (int i = N; i >= 0; i--) {
num[i] += num[i + 1];//後ろからの累積和
}
int sum = N;//使えるカードの枚数
int c = N;//操作回数
for (int k = 1; k <= N; k++) {
//sumがk*c以上になるまでcを減らしていく
while (sum<k*c) {
sum -= num[c];//cを1減らすときに、使えるカードの枚数が(重複がc枚以上のカードの種類数)だけ減る
c--;
}
cout << c << endl;
}
}

2019-09-23

AGC038-C ｢LCMs｣

競技プログラミング

一昨日のAGCのC問題を完全理解したので解説します。
(※スマホだと数式がうまく表示されないようなのでPC版表示に切り替えてください)

求めたいものは次式で表される値ですが、
\[\sum_{i<j}LCM(A_{i},A_{j})\]
これはgcdを使うと次のように書き換えられます。
\[\sum_{i<j}\frac{A_{i}A_{j}}{GCD(A_{i},A_{j})} \]
そこで、gcdが同じになる\(A_{i},A_{j}\)の積の総和(これを\(f(d)\)とします)を効率よく求めることができれば、答えは次のようして求められます。
\[ans=\sum_{d}\frac{f(d)}{d}\quad where \quad f(d):=\sum_{GCD(A_{i},A_{j})=d}A_{i}A_{j}\]
この\(f(d)\)をどうやって計算するかですが、これは\(d\)を約数として持つ\(A_{i},A_{j}\)の積の和(これを\(g(d)\)とします)を求め、そこから余分なもの(\(d\)の倍数(\(d\)を除く)をgcdとして持つ\(A_{i},A_{j}\)の積の和)を引けばよいです。すなわち、
\[g(d):=\sum_{d|A_{i},A{j}}A_{i}A_{j}\]
として、
\[f(d)=g(d)-\sum_{k \geq 2}f(kd)\]
となります。
\(g(d)\)は次式を利用して前計算できるので、
\[2g(d)=(\sum_{d|A_{i}}A_{i})^2-\sum_{d|A_{i}}{A_{i}}^2\]
\(f(d)\)も後ろから順次求めていくことができます。

実装にあたって気を付けるべきことは、逆元を前計算しておくこと(\(x^{MOD-2}\)はやや遅いです)と、約数列挙を\(O(M\log{M})\)でやることです(\(O(M\sqrt{M})\)は厳しい)。この辺りはACコードを見ていただければと思います。

普段数式を書くことがあまりないので、記号の使い方など間違っていたら指摘していただけると幸いです。

ACコード

#include<iostream>
#include<vector>
using namespace std;
#define REP(i, n) for(int i = 0;i < n;i++)
#define ll long long
#define pb(a) push_back(a)
const int MOD = 998244353;
const ll MAX_VAL = 1000000;
ll add(ll x, ll y) {
x += y;
if (x >= MOD) return x - MOD;
return x;
}
ll sub(ll x, ll y) {
x -= y;
if (x < 0) return x + MOD;
return x;
}
ll mult(ll x, ll y) {
return (x * y) % MOD;
}
ll bin_pow(ll x, ll p) {
if (p == 0) return 1;
if (p & 1) return mult(x, bin_pow(x, p - 1));
return bin_pow(mult(x, x), p / 2);
}
ll inv[1000010];//逆元
vector<ll>divisors[1000010];//約数の集合
ll sum1[1000010];//sum1[d]=dの倍数の和
ll sum2[1000010];//sum2[d]=dの倍数の2乗の和
ll A[200020];
ll f[1000010];
ll g[1000010];
//逆元の前計算
void inverse_init() {
inv[1] = 1;
for (int i = 2; i <= MAX_VAL; i++) {
inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
}
}
//約数列挙
void divisors_init() {
for (int d = 1; d <= MAX_VAL; d++) {
for (int x = d; x <= MAX_VAL; x += d) {
divisors[x].pb(d);
//divs[x].insert(d);
}
}
}
//g(d)の計算
void calc_g() {
for (int d = 1; d <= MAX_VAL; d++) {
ll tmp = 0;
tmp = add(tmp, mult(sum1[d], sum1[d]));
tmp = sub(tmp, sum2[d]);
tmp = mult(tmp, inv[2]);
g[d] = tmp;
}
}
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
divisors_init();//約数列挙
inverse_init();//逆元の前計算
int N; cin >> N;
REP(i, N) {
cin >> A[i];
for (auto x : divisors[A[i]]) {
sum1[x] = add(sum1[x], A[i]);
sum2[x] = add(sum2[x], mult(A[i], A[i]));
}
}
calc_g();//g(d)の計算
ll ans = 0;
for (int d = MAX_VAL; d >= 1; d--) {
ll tmp = g[d];
for (int k = 2; k*d <= MAX_VAL; k++) {
tmp = sub(tmp, f[k*d]);
}
f[d] = tmp;
ans = add(ans, mult(f[d],inv[d]));
}
cout << ans << endl;
}

画像がなくて寂しかったのでこの前取ったKilling Rhythmのリザルトを貼ります。

2019-09-12

フィックスターズのサマーインターンに参加しました

こんにちは。モジャンボです。
株式会社フィックスターズにて3週間のサマーインターンに参加してきました。
その時の記録を残しておきます。これからインターンに参加する人の参考になれば幸いです。

・応募するまで
僕は現在工学部の3年生で、おそらく修士に進むので就活はまだまだ先なのですが、卒業後にやりたいことが全く決まっていないのもなぁと思い、AtCoderJobsや魔法のスプレッドシートを見ながらインターンにいくつか応募してみることにしました。あとその頃ちょうどNEW GAME!を読んでいて就業体験モチベが高まっていたという事情もあります。結果的にフィックスターズでのインターンは思ったよりNEW GAME!していて大満足でした。

フィックスターズに応募した理由は、
・業務内容が面白そう
応募時にたくさんあるテーマの中からやりたいものを選べるのですが、僕は「画像処理アルゴリズムの開発・高速化」を選びました(めちゃめちゃ楽しそう)

・応募要件のハードルが低い

(AtCoderJobsから申し込む場合)AtCoder水以上で、C/C++を使えてやる気があれば歓迎！みたいな感じでええや～んとなりました。他社のインターンではしばしば†実務での開発経験†が要求されていたのでそれがないのはとても魅力的に感じました。

・有給
時給2000円ｽｺﾞｯ(๑°ㅁ°๑)‼✧(◎_◎;)やばやば(神ω神)\\ｳｵｵｵ(っ `-´ c)ｵｵｵｵｵ//

・面接
ここはどの程度書いていいのか分からないので適当に流します。
大崎本社のオフィスでコーディング試験を受けてそのまま面接に進みました。
自分にはアピールできる実績も能力も特になかったので、終わったときは正直落ちたかなと思いました。

・採用
(´⊙౪⊙)۶ｯｯｯｨｨｨｨｲｲｲｲﾖｯｼｬｱｱｱｱｱｱｱｧ!!!!

・入社
同じテーマで参加したインターン生がもう一人いたのですがそれがたまたま知人で、インターン中の席も隣だったので完全にNEW GAME!が開始しました。

ここからやったことを書きます。今回自分は業務上の秘密にかかわっておらず、メンターの方の許可もいただけたので特にぼかしたりせずに書きます。
・1週間目
初日は環境構築をして、Gitの使い方を学びました。それまでGitを使ったことがなかったのでこのタイミングで使い方を学べたのはありがたかったです。
その後はCUDAによるGPUプログラミングを勉強しつつ、畳み込み演算の高速化に取り組みました。CUDAと畳み込みについての説明はそれぞれ以下の記事が分かりやすいと思います。

・2週間目
ここからが本題です。
「Ego-Motion Estimationの高速化」に取り組みました。連続する2フレーム間でのカメラの動きを推定するプログラム(メンターの方が開発している)の高速化です。
自分はそもそも画像処理の基本から無知だったので、その辺りを説明していただいて、関連する論文を読んで、ソースコードを読んで、プロファイラなどを使い改善できそうな部分を探して書きなおす　みたいな流れで行いました。
二週間目はまだGPUを使わずにいろいろ試していました。が、何をやっても大体遅くなって笑いました。

・3週間目
プロファイリングの結果、ボトルネックになっている部分は誤差を逐次的に累積する部分だということが分かっていて、これはGPUで並列計算させることができそうだったので、この部分をCUDAで書き直すことにしました。並列プログラミングはデバッグが難しく、コーディングの10倍くらいの時間をデバッグに費やしていた気がします。

何とか最終日の二日前に完成し、5倍くらい速くなってホッとしました。その後は三週間で行った内容をまとめたスライドを作成し、最終日に成果報告会という形で発表を行い、インターンが終了しました。

・業務以外のこと
・オフィス
広々としていてかなり良い環境だったと思います。インターン生やアルバイトにも1人1台十分なスペックのPCとモニター2枚が割り当てられていて感動しました。また、フリースペースもあり、お昼寝スペースや筋トレ用の器具、マッサージチェアなどが置いてあったりして居心地がよさそうでした。
・昼食
社員の方と一緒させていただき、三週間毎日違うお店でご飯を食べました。大体何を食べてもおいしかったですし、多くの方とお話しする機会になってよかったです。
・おやつタイム
毎週木曜の16~17時に「おやつタイム」なるものが設けられていて、社内のフリースペースに集まっておやつを食べました。
・競プロ
社内では競プロが盛んらしく、一度競プロ練習会(バチャコン)に参加させていただきました。
・自販機
社内の自販機は一杯10円で利用できて(神ω神)でした。毎日コーヒーを飲みまくってました。

・感想
大満足でした。反省すべき点も多々ありますが、業務内容が面白くメンターの方にも良く面倒を見ていただいて、素晴らしい体験ができました。また、これまで競プロ以外でのプログラミング経験がないことを少し負い目に感じていたので実務っぽい開発経験が得られてよかったです。
このような素晴らしい機会を与えてくださったAtCoderJobs様とフィックスターズ様に感謝します。

2019-06-24

AGC005-C 「Tree Restoring」

競技プログラミング

友人(simkaren, juppy)とICPCに出ることになってから競プロモチベが高くていい感じです。
今日解いた問題「Tree Restoring」がとてもいい問題だと思ったので考察過程などを書いてみます。

・問題
頂点数がNで、すべてのi=1,2,..,Nについて頂点iと最も遠い頂点の距離がa_iとなる木を作れるか？

・考察の前に
グラフを構築する問題は、まず「極端なグラフ」を考えて、それを元にあれこれ手を加えるとうまくいくことが多い(らしい)です。先日のABC131-Eもこの方針で解けました。
「極端なグラフ」には以下のようなものがあります。全部N頂点とします。

・ウニグラフ

1つの頂点と、それにつながるN-1個の葉をもつ木です。
スターグラフとも言うらしいです。

・完全グラフ

すべての頂点同士が辺で結ばれているグラフです

・パスグラフ

直径(あとで説明します)がN-1となる木です。一直線な形をしています。

・キャタピラ木

パスグラフにいくつか葉をつけ足した木です。

・木の直径
木の直径とは、「最も遠い二頂点間の距離」のことです。
例えば下図の木で言うと、青色で示したパスの長さ5が直径になります。

・考察
まずは上にあげた極端な木をいろいろ描いてみます。
青い数字で示したのはその頂点から最も遠い頂点の距離です。

なんだかパスグラフとそれに葉を加えたキャタピラ木がとても良い性質を持っているように見えますね。

与えられたa_iのうちの最大値をmaxとします。
まず直径maxのパスグラフを書いてみると、
maxが偶数→a_iの最小値はmin=max/2となり、a_i=minの点が1つ、a_i=min+1~maxの点が2つづつ
maxが奇数→a_iの最小値はmin=(max+1)/2となり、a_i=min~maxの点が2つづつ
になります。

ここに（直径を変えないように）葉を加えていくとa_i=min+1~max(a_iがminとなる点は増やせないことに注意)の点を好きなだけ増やしていくことができます。

逆にこのようにして構成できなければ"Impossible"を出力します。

・ソースコード
https://atcoder.jp/contests/agc005/submissions/6100835

#include<algorithm>
using namespace std;

int num[101];//各a_iの個数をカウントする
int main() {
	int N;
	cin >> N;
	int mx = 0, mn = 1000;//a_iの最大値と最小値
	for(int i=0; i<N; i++){
		int a; cin >> a;
		mx = max(mx, a);
		mn = min(mn, a);
		num[a]++;
	}
	bool ok = true;
	//maxが偶数の時
	if (mx % 2 == 0) {
		//minはmaxの半分でなければダメ
		if (mn != mx / 2)ok = false;

		//a_iがminとなるiは1つだけで、それ以上増やせない
		if (num[mn] != 1)ok = false;

		//a_iがmn+1~mxとなるiは少なくとも2つなのでそれを下回っていればImpossible
		for (int i = mn+1; i <= mx; i++){
			if (num[i] < 2) {
				ok = false;
			}
		}
	}
	//maxが奇数の時
	else {
		//minは(max+1)の半分でなければダメ
		if (mn != (mx + 1) / 2)ok = false;

		//a_iがmaxとなるiは2つだけで、それ以上増やせない
		if (num[mn] != 2)ok = false;

		//a_iがmn+1~mxとなるiは少なくとも2つなのでそれを下回っていればImpossible
		for (int i = mn + 1; i <= mx; i++) {
			if (num[i] < 2) {
				ok = false;
				if (ok)cout << "ok" << endl;
			}
		}
	}
	if (ok) {
		cout << "Possible" << endl;
	}
	else {
		cout << "Impossible" << endl;
	}
}