競プロ 言語調査

随時更新

☆ = 0.5★

名前 ジャッジ対応 速度 使用者数
C++ ★★★ ★★★ ★★★
Java ★★★ ★★ ★★
C# ★★ ★☆
D(DMD) ★★
D(LDC) ★★☆
Rust ★☆ ★★★
Go ★★
Python ★★★ ★★

C++

王道、大鉄板、これが使えないジャッジは競プロサイトにあらず

ジャッジ速度使用者数全てで他を寄せ付けない

困ったらコレ

Java

コレが使えないジャッジは(ry

C++より使用者が少ない理由は2つあると思ってて、

  • 遅い。JVMで動いてるからどうしようもないね。でもAtCoder等なら定数倍ヤバはもう出ないので平気っちゃ平気?インドワクワク系は…
  • コードが長くなる、いちばん有名なのはプリミティブ型をラッパしなきゃいけないこと(Integer, Long, Double…)

C

chokudaiさんが使っていることで有名

visual studioの補完が強いらしい?

あとLINQも軽く調べるとかなり便利そう

これも仮想マシンで動いていて、かなり速度に問題があるイメージだけど、 仮想マシンやめるC# Nativeとかいうプロジェクトがあるっぽい?

かなり未来に期待できそう、今現在では微妙感がぬぐえず

D(DMD)

僕は好きです。

何故かプロコン界隈だと、日本でのみ異常な人気がある感じがします。あとGassa

仮想マシンは使ってないけどそもそもコンパイラが微妙なので遅いです

D(LDC)

D言語コンパイラが2種類あるんですが、こっちはLLVMベースなのでとにかく速いです。

対応ジャッジはAtCoder以外見たことないです。

おわりです。

Rust

かなりホットなイメージです

速度もC++並というイメージが有る

実は殆ど書いたこと無いのでイメージで物を言っています

Go

プロコンで使うのきつくない?僕はきついと思います。

Python

C++の次に人気なイメージが有る

当然ながらとても遅いが、まあ速度が問題にならないなら

Kotlin

ICPCにぶち込まれた言語、メインスポンサーって凄いなって思いました。

JVMで動いている以上Javaより速くなることはなさそう?でもKotlin Nativeとかあるらしいし、これもどうなるでしょう

少なくともICPC WFの問題は全部Kotlinで通せることが保証されるんじゃないでしょうか(メインスポンサーは凄いため)

CODE FESTIVAL 2017

当日朝

睡眠失敗。悲しいね

早めに行く

周りがwafrelka, sigma, wo, tozan, hogloidでウンウンこれもまたdiversityだね

本戦

とりあえず1000点まで全部読む

Fが面白そうだね(一番最初に構築ゲーやるの無謀すぎないか?)→しばらくいじったりエスパー発動したりしたら解けました

そろそろA, Bを解くか→Aが難しすぎませんか?

Bは前2文字から次の文字が決まるので最初の2文字を全探索した、かなり無駄ですね

E, Gは読んだら解けてしまった、かなり調子がいいですね、と思いきや…

Dはちゃんと捨てられて、1600に100分時間を残せたところまでは良かった。多分1900が一番解ける希望があったっぽいので、ちゃんと読むべきでしたね…

エキシビション

sugim, sigmaエキシビション失敗してたので出る。 B、息を吐くように平衡二分木が使えれば解けるところまでは行っていたっぽいが、息を吐くように平衡二分木が使えなかった。筋トレ

トーナメント

Round1で200点を取る(は?)(D言語のto!ulongは入力が負のときに例外を投げます。気をつけようね!)

りんごさんの挑戦状

指を痛める

リレー

sevenkplusさんに自分の考えた解法を伝えようとしたら全く伝えられなかった。英語力 Hを書いたらバグらせた、悲しいね

反省

ちゃんとオンサイトブーストは効いてるっぽいので、1600以上を安定して解けるようになりましょう(完)(1600以上が安定して解けるの世界で何人だ?)

スタッフ、writerの皆さんお疲れ様でした

JOI 春合宿 2017 Broken Device 解法(未検証)

概要

略。

解法

この問題は、150 * 60の$\mathbb{F}_2$ matrixであって、「行ベクトルを110個選んだときに、どう選んでもrankが60になる」ような行列を構築すれば解ける。

ところで、

https://arxiv.org/pdf/1404.3250.pdf

を見ると、ランダムに110 * 60選んだ行列がフルランクになる確率は$(1 - 1/{2^{51}})^{60}$以上らしい。

よって、テストケース数を30とすると失敗する確率は

$1/{2^{51}} * 60 * 30 * 1000$で抑えられ、これはEPS

実装

脳内AC

JOI Open 2013 Synchronization 人間的解法

JOI Open 2013 Synchronizationの人間的な解法を紹介します。

問題概要

解法

ある辺を追加すると、左右で互いに情報を交換します。この交換する個数を高速に求めたいです。

左が情報をa個、右がb個持っていて、そのうち共通のものがc個あったとします。 すると辺を追加した後、左右はつながり、合計でa+b-c個の情報を持ちます。

ところで、このcは、"その追加しようとしている辺がその前に繋がっていた時点での、左右の情報の個数"です。

以上より、辺ごとに最後につながっていた時点での左右の情報の個数を持つことにします。すると以下のようなクエリを処理できれば良くなります。

  • 辺の追加
  • 辺の削除
  • 連結成分の頂点全体にset
  • ある頂点の値を取得

これはもう今の時代どうとでもなりますが(ex euler-tour-tree)、それは今回は使いません。

まず、木の形が固定であることを利用し、最初に根付き木にすると、

  • 辺の追加
  • 辺の削除
  • 連結成分のうち、最も根に近いものを取得

の3つができれば良くなります。連結成分のうち最も根に近い頂点の値が、その連結成分の値を表すこととします。

これはもう今の時代どうとでもなりますが、そのなかで実装の軽いeuler-tour 2Dを使用します。 これを利用すると、ノードにsetとかそこらへんを載せたsegtreeで解けることがわかります。

手元で1.9sで、まあ2xだと考えると、TLが4sぐらいならば間に合うと思うのですが、本番だとどのぐらいのTLだったのでしょうか。 まあsetをやめて、例えば先読みしてsegtreeとかにすればもっと速くなると思います。

よく考えると、RMQだけで実装できました。思考停止二分探索でlogが2個、segtree特有の二分探索高速化でlogが1個です。

ICPC World Final 細かい話

practice

今までのworld finalの問題6問セット*2時間だった。

1: 知らない 2: 球形の穴が沢山空いた直方体が与えられるので、k等分 3: 知らない 4: 重実装幾何 どぼじて 5: 平面状に点がたくさん与えられて最大クリーク 6: 420と見せかけて状態が少ないハフマン木構築

本番

持ち込みたいもの(白紙、ライブラリ、筆記用具)は初日の登録セッションで渡しておかないといけない。期間中に練習をしたいなら、持ち込み用と練習用で分けて持っておく必要がある。白紙だけでなく方眼紙も持ち込めた。

むこうから支給されたのは、水500ml * 6本、昼ごはん3食、後ろに消しゴムの付いた鉛筆3本、ボールペン黒3本、ノートと大量の方眼紙が3セット

筆記用具はかなり貧弱なので、持ち込んだほうがいいと思う。 紙は使い切ることはまず無い量だったので、まあ紙質とか気にするなら

3人座れる長机、パソコンの位置は一番左

システムの情報はサイトに書いてある、重要な情報はスタックサイズ無限、C++14が使える、あたり?

キーボードは耐えられないほどではないがそこそこ打ちにくかった、本番だと2分ぐらいしかパソコンに触ってないから記憶が怪しいかも

コンテスト前の虚無タイムは相当長い

印刷のタイムラグは多分チームごとに相当差がある、印刷場に近い席なら相当速い(と思う)(今回だと名前順が遅いほど速い)。個人的にはクエリを送ってから印刷までのタイムラグは少なくて、それを運んでくる時間が律速(ゆっくり歩いて運んでくる)

印刷の方法はコマンドラインからprintfile A.cppみたいに叩く方式だった。不思議。

ジャッジ結果は結果以外何も見れなかった(一番厳しい方式)。得られる情報はジャッジ結果が帰ってくるまでのタイムラグぐらい。本来のkattisだと何番目のケースで落ちたかとか見れるが、今回はそれはないので注意。

思い当たるのはこのぐらいなので、他に知りたいことが合ったら教えてください

AGC 014 F Strange Sorting

AGC 014 Fを解きました。

解いた後に解説動画を見たら全然違いました。ゴリ押しです。

まず、数列を-1倍してよくある各点までのLISを求めるやつをします。 たとえば[3, 5, 1, 2, 4]ならば、[1, 1, 2, 2, 2]です。これは"初めてその値が高い項になるのは何回目か?"を表します。

サンプル3:[2, 10, 5, 7, 3, 6, 4, 9, 8, 1]に対してやると、[1, 1, 2, 2, 3, 3, 4, 2, 3, 5]となります。

ここで、LISといえばRank分けですね、というわけで分けると、[2, 10], [5, 7, 9], [3, 6, 8], [4], [1]となりますね。

ここで、実はこれをこのまま結合した[2, 10, 5, 7, 9, 3, 6, 8, 4, 1]を数列の初期値としても答えが変わらないことが示せます。略します。

で、これを二次元平面にプロットしてみましょう。x座標はLISの値、y座標は数列の値です。

すると下図のようになります。

f:id:yosupo:20170512075557j:plain

すると、"一番左の列の点たちを適切な位置に動かす"を繰り返すような操作になることに気づきます。 具体的には各点について、「自分より上の点について、自分より左の列から移動してきたような点」が存在しない列、のうち最も左側に動きます。

操作をすると下図のようになります。

f:id:yosupo:20170512075548j:plain

ここで、上の点にしか移動が依存しないことを考えると、上から点を追加していく方針を考えたくなります。

要するに、各列について、その列に来た点のうちもっとも左側から来たものとの距離、を持って、その配列を管理しながらいい感じに処理をします。

各点についてどのような処理をするかというと、「配列の値 <= 移動距離」となるなかで最も近いものに移動し続けることになります。

もちろん愚直では間に合いませんが、ここで、配列の値が広義単調減少であることを利用します。

大体配列の値ずつぐらい移動することを考えると、今のいる場所の配列の値で平方分割することを考えたくなります。

具体的には「今いる場所の1マス先の配列の値」がsqrt以上かどうかで場合分けをすると、大きい間は愚直にバイナリサーチ、小さいとまとめて一気に動く、という操作を行えば良くなります。

計算量はO(NsqrtNlogN)と見せかけてO(NsqrtN)です。

「みんなのプロコン」

久しぶりの参加記

コンテスト前

うっかり遅刻した(いつもの)(ごめん)(反省がない)(受付時間で差を付けろ)(鈍足)

なんかsigmaとsugimにArrangement Tickets(JOIオープン)の僕の解法は嘘解法だとかいう言いがかりをつけられる。

コンテスト開始

問題を読んでる間に前の席のantaさんが実装を始めて怖かった

A問題はメモ化再帰やるだけっぽいのでとりあえず全探索書いたら一生答えが返ってこなかった。 でもまあメモ化したらサンプルがあったので提出。WA

よく考えたら遷移にループがありますねぇ!(気づき) 幸先が悪すぎる。 無理やり修正して投げたらAC。既にantaさんが2問解いてるんだけどバグかな?

FA狙うゾってCを読んだらsegtreeで解けると勘違い。書き終わったがサンプルが合わない(それはそう) よく考えると平方分割だったので書き直し。

C問題のWAが取れなすぎるので一回置いといてDEを読む。Dは解法自明実装激重だったが、この時点でペナルティも時間消費も激しすぎたのでDを捨ててABCEの4完を目指すことを決定。

C問題のデバッグと並行してE問題を考えると解けた。

が、Eもめちゃくちゃバグる。

Cを提出→結果待ちでEをデバッグして提出→結果待ちでCをデバッグして提出→…みたいになって冷えていた。

ACを見ることで精神衛生を保とうと放置してたBをパパっと解いたらWAして更に嫌な気持ちになった。

多分ジャッジルームで「こいつ冷えてるな~」とか言われてるんだろうなあと思いながらデバッグ。Bはすぐにバグが取れる。

CE両方ほぼ同時にバグを取りきるが両方TLEする(は?)

両方O(NsqrtNlogN)なのでオーダーが間違えてるのか?とは思ったがどうしようもないので両方定数倍改善することに。

E問題はsetを事前に用意していた超高速setに変更。無事AC。1654/2000ms

C問題はmodをif + 引き算にチマチマ書き換えたら無事AC。5443/6000ms

定数倍改善してる間にEのFAも取られるしもうめちゃくちゃですね。

恐ろしいWAが溜まっているがDを20分で解くのは厳しすぎるなあと思ってこれ以上誰もE通すな~~~って思いながらボーッとする。

さすがに頑張るかという気持ちになってDを実装したが、案の定間に合わず。

まとめ

前半があまりにひどすぎたが、後半は最善の行動だった。

ところで商品なに来るか知らないんですが、何が来るんでしょう