23
13

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

競プロnoobがJulia縛りでAtCoder水色に

Last updated at Posted at 2019-01-20

なったので投稿する

概要

ほぼJuliaのみ(現状制約の問題で解答不可能な過去問を除く、という意味)を用いてAtCoderでレート1200に到達しました。
恐らく先人が存在しないと思うので、マイルストーンとして「Juliaを用いて」「水色を目指す」という読者を想定した記事を書くことにしました。

進捗

rightblue.png
緑帯でレートの推移が文字通り草を生やしていますが、これは後述のC問題速解きを徹底した結果、パフォーマンスが完全にD問題の難易度に依存するようになったためだと思います。
ABCに8回出て全完できたのは1回しかありません。解ける問題の数だけで考えれば、実力はレート1000~1100辺りだと思います。

aclang.png
現状Juliaだと絶対に解けない問題があるので、それを埋めるためにJSを使いました。今後も使うかは未定です。FortranはJuliaでのAtCoder攻略を諦めかけた時に手を出しましたが、今ではなかったことにされています。

感想

今の所一瞬で解ける問題と絶対に解けない問題しかないので、コンテストが実質競技タイピングと化していて非常に不毛です。毎回最後の30分は諦めて下がっていく順位を眺めながら過ごしています。
最初の数分で勝負が決まるのでそこに向けてめちゃくちゃ準備をしています。前日の睡眠を調整して、3時間前には軽食を摂り、2時間前に過去問とタイピングで頭と指のウォームアップをしています。毎回異常なくらい緊張して、謎の震えでキータッチがおぼつかなくなります。

もっと解けるか解けないか血湧き肉躍る戦いを繰り広げたいです。精進あるのみです。頑張ります。

Julia固有のメリット

これまでに発見した、競プロにおいてJuliaだからこそ可能なことを挙げます。

ありません。

Juliaのメリット

Julia固有とはいかないまでも、Juliaを使うことに他のメジャー言語と比べてメリットがないわけではないです。

競プロのルール上Juliaが速さで勝てることはほぼないので、基本的に「便利さ」という面が強みになります。

標準ライブラリが強い

そもそも科学技術計算向けに開発されている(多分)言語なので、算術的なものに関しては標準ライブラリでできることは多いです(使いこなせてるとは言ってない)。

わかりやすい

自然言語と極力同じ表現ができるような文法になっている(はず)ので、コードを見た時に何をやっているかわかりやすいです。文法も基本に忠実というか、初見で何をしているのかわからないということは少ないように感じます。
私はJuliaとJavaScriptしか使えない人間ですが、そんな私から見るとプログラミング初心者におすすめできる言語だと思います。

JITコンパイル

腐ってもスクリプト言語最速の異名を持つ言語です。私自身がE~F問題にほとんど触れられていないからというのもありますが、今のところ想定解法を素直に実装して間に合わなかったことはないです。今はまだね。

マイナー

競プロではマイナー言語なので「言語別AC数のランカーになる」「AC数で他のマイナー言語を越える」というモチベーションを持てます。
kenkooooさん、ありがとうございます。

実例

ドヤ顔で変態解法を披露するコーナーです。

AGC024-A

parseInt(x) = parse(Int,x)
function main()
	a,b,c,k = map(parseInt, split(readline()))
	v = [a,b,c]
	x = [0 1 1;1 0 1;1 1 0]
	v = x^k*v
    println(abs(v[1]-v[2]) >= 1000000000000000000?"Unfair":v[1]-v[2])
end
main()

「AGCは頭を使って解くんやで」ということを教えてくれている問題ですが、脳筋の私でも「変換行列をn回左からかける」という操作によって設問の定義通りの計算結果が出せます。
Juliaは行列のべき乗を標準搭載しているのでこの解法が簡潔に書け、かつ間に合います。

ABC075-C

parseInt(x) = parse(Int, x)
parseMap(x::Array{SubString{String},1}) = map(parseInt, x)

function main()
	# 隣接行列読み込み リンク情報は後々使うため別に保持
	n,m = readline() |> split |> parseMap
	g = zeros(Int,n,n)
	e = Array{Int}(2,m)
	for i in 1:m
		e[:,i] = readline() |> split |> parseMap
		g[e[1,i],e[2,i]] = 1
		g[e[2,i],e[1,i]] = 1
	end

	# ラプラシアンを求める
	l = diagm(g*ones(Int,n))-g

	# 引いて、階数を計算して、戻す
	count = 0
	for i in 1:m
		l[e[1,i],e[2,i]] += 1
		l[e[2,i],e[1,i]] += 1
		l[e[1,i],e[1,i]] -= 1
		l[e[2,i],e[2,i]] -= 1
		if rank(l) < n-1
			count += 1
		end
		l[e[1,i],e[2,i]] -= 1
		l[e[2,i],e[1,i]] -= 1
		l[e[1,i],e[1,i]] += 1
		l[e[2,i],e[2,i]] += 1
	end
	println(count)
end

main()

想定解ではdfsを用いていますが、C問題でdfsを出題するなど言語道断です。私が解けません。
 
 グラフが(強)連結である ⇔ グラフのラプラシアンの階数がn-1である

という性質を利用します。全ての辺に関して、それ一本のみを取り除いたグラフのラプラシアンの階数を求め、それがn-1未満だったものの数を数えることで答えが出ます。
Juliaは行列の階数を求める関数を標準搭載しているのでこの解法が簡潔に書け、かつこの問題の制約下では間に合います。50×50程度なら楽勝でした。

Juliaのデメリット

以前私の書いた記事を参考いただけると幸いです。

遅い

遅いです。

parseが遅い

parseが遅いです。

メモリ使用が異常

f__kyou.png
AtCoderのJulia0.5.0はFワードを出力するだけで145MBを使用します。
明らかにおかしいメモリの使われ方をしているので、これはバグの類ではないかと思っています。
実際にこの問題のせいで、グラフの隣接リストを辞書型で持った際にMLEを起こしたことがありました。
AtCoderさん、待ってます。

配列のインデックスが1からスタートする

Juliaを使っている人なら1から数えることに慣れているかもしれませんが、多くの言語は0からスタートするため、懇切丁寧にも0スタートを想定して作問されている問題が多数あります。つらいです。
ちょっと逆順に配列を見始めた途端、私のような頭の悪い人では今どこを参照しているか分からなくなるので、注意が必要です。

Pythonじゃダメなんですか?

良いと思いますよ。

便利な関数と気をつけるべき点

Juliaを使ってAtCoderの問題を解く上でよく使う、知っておくと便利、調べる時間を短縮できる、躓きがち、などの要素を持つ項目です。思いつき次第追記する可能性があります。

sortcols(sortrows)

行列を列ごと(行ごと)にソートする方法です。
sortcols.png

split, chomp

主に入力時に使うものですが、注意点としてsplitを適用した場合に個々の要素の型がStringでなくSubString{String}になります
substring.png
Stringを指定して操作を行う場合などに注意が必要です。

Julia1.0ではchompした場合にもSubString{String}になるようです(0.5.0ではString)。来たるべきアップデートに備えて留意しておきます。

maximum, minimum

配列の最大値、最小値を返します。max, minと混同しないように気を付けましょう。

Dictとfindmax系統

Int=>IntのDictを使うケースは大いにあり得、その中ではvalueが最大値となるkeyを取得したいこともあると思います。
しかしInt=>IntのDictに対してfindmaxやindmaxを行った場合、valueでなくkeyを参照してしまうため実質使用不可能です1
これは1.0では改善されています。AtCoderさん、待ってます。

Julia1.0以降を使っている人向け

「atcoder julia」とかでtwitterを調べると1.0になったらやってみようかな的発言が散見されます。
個人的には今すぐ始めて良いと思います。

そもそも競プロで求められるような操作はプログラミング言語を名乗る上で当たり前に備えているようなものばかりで、Juliaならば0.5でも1.0でも大概の機能が同一に備わっていると思います。
実際に1.0で書いたコードをそのまま提出しても多くの場合そのまま通りますし、仮にエラーを吐いたとしても修正箇所はごく僅かです。
バージョンの違いであれこれ言える程度に知識を持っている人なら、その程度の適応はすぐに可能だと思います。

必要だと感じる要素

需要があるかどうかわかりませんが、これ以降は言語に依らない一般的な話になります。
特に灰色が水色になる上で、必要と感じる要素を挙げます。

結論

水色になる上で最も重要なことは「C問題の速解き」です。
ABCの順位表を眺めているとわかりますが、多くのコンテストで600点獲得にかかった時間で順位に天と地ほどの差が開きます2
レートは順位を元に算出されますが、時間をかけてD問題をクリアしても600点組上位と順位差は開かず、したがってレートの差もあまりありません。
つまり、このレート帯において「レートを稼ぐ」ことは「可能な限り速く600点を獲得する」こととほぼ同値であり、ボトルネックはC問題ということになります。

以下はその上で必要だと感じたものです。

実装力

ABCはだいたい、

A...競技プログラミングのルール
B...if文とfor文を書く能力(と簡単な文字列の処理)
C...計算量という概念の理解、実装力
D...数学力、考察力、有名問題に関する理解

が問われるケースが多いように感じます。 実装力 ⇔ 思い浮かべた操作をコードにする能力 はC問題を完答する上でとても重要だと思います。

言語(仕様)の理解

JuliaとAtCoder特有の問題を知っていない限り絶対に解けない問題が存在します。
詳しくは過去の記事を参考にしてください。
一か月くらいをこれに費やしたので、皆さんは私の苦労を使ってショートカットしてください。
他の言語でも、知っていないと手も足も出ない的な要素は多かれ少なかれあるので、最低限それを知っておくことは必要だと感じます。

諸々のテクニック

重要なのは
・二分探索
・ソート
・累積和
程度だと思います。
が、ソートはソートという便利な機能の存在を知るだけでよく、累積和は予め足しておくという発想を知るだけでよいので、実質重要、というか理解していないと詰む要素は二分探索のみということになります。

C問題を解く上でこれ以上のものが求められることは(特に最近では)少ないように感じます。求められた場合や極端に難しい問題が出た場合は600点獲得者がごっそり減るので、B問題速解きができればそこそこのパフォーマンスが出、致命傷には至らないと思います(Cf.ABC108)。
どうせコンテスト本番で「C問題が既存の知識で解けない!」と気づく段階なら90分くらいは余っていると思うので、最悪その場で勉強すればよいと思います。

やって効果があったこと

この手の記事は先例が大量にありますが、特に効果があったと感じたものを挙げます。

過去問を解く

ほとんどの人にとって、最短でスコアを上げる方法は過去問を解くことだと思います。

どれをどの程度埋めればいいかという問題ですが、先例で言及されている分量の多くは「水色」という目標に対して若干過剰だと感じます3
水色達成に一番重要なのはC問題なので、水色が目標という人はとにかくC問題を埋めることを意識すればいいと思います。
当然、もっと上を目指している人にとってC問題の重要度は低いと思います。

※解説AC

解けないより解説を見て解いたほうが、多くの人にとって、特にレートの低いうちは間違いなく良いと思います。
C問題に実装力が必要と書きましたが、最初のうちはそれ以前に何を実装すればいいのか、問題を解くために何を知ればよいのかがわからないという状況が多発します。
そんな状況で闇雲に勉強するのは非効率なので、分からない問題に当たったら答えを見て「まず自分が何を知るべきか」を知ればよいと思います。

※先人の解答を参照する

特に詰まった時に、正解から逆算してどうすれば解けるか考えるのは良い方法です。競プロにおいて正解とは先人のACした解答例です。故にマイナー言語では難しい面もありますが…
他にも先人のコードと速度を比較してみると、細かい言語の仕様など様々な発見があったりします。
 
 
 

基本的に水色到達までにやって効果があったのは過去問だけだと感じました。

むすび

AtCoderさん、
Codeforcesさん、
Julia1.0待ってます。

  1. keyの最大値と、そのkeyがDictの何番目に格納されているかが返ってきます。世界一どうでもいい情報ですね。

  2. 極端な例ですが、ABC116での600点最速がパフォーマンス1600(上限)、最遅がパフォーマンス580です。

  3. 多くの場合「もっと上の目標があり、パフォーマンスも水色相当よりずっと高い値を出しながら、通過点として水色になった」事例なので、必然的に行っている内容は水色よりずっと上のレート帯を想定しているものだと思います。

23
13
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
23
13

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?