3チームに分かれて行います。初めに3チーム1マスずつ当てられています。
支配しているマスの隣のマスについて、指定された問題をマスに書かれている言語で書くことでそのマスを支配できます。
既に他のチームに取られてしまっている隣り合っているマスは、そのチームのコードの文字数（マスに書かれている）よりも短いコードを書くことで上塗りして支配が出来ます。
期間は1週間です。

というものでした。お題は、

8桁の2進数で与えられた数が三角数かどうか判定せよ。入力は50個の数からなる。三角数なら1、そうでないなら0を出力せよ。

というものでした。私は赤チームだったのですが、緑チームにかなりのプロ2名がいらっしゃったようで、残念ながら自分の書いたコードは他の方に塗りつぶされてしまった・それによって提出する権利を失ってしまったのですが、Esolangの習得に関してはまあまあ頑張れたかな、と思ったので、自分のやったものについて、書いた順に触れていきます。

2017-08-21

競プロerキャンプ in 関東

プロコン

8/17～18の間に行われた競プロerキャンプ in 関東。達也さん（@tatuyan_edson）、迷路さん（@pazzle1230）を中心に私含め5名の少数人数ながら、楽しい時間を過ごすことが出来ました。

さて、今回はその合宿初日に行われたVirtualContest(https://vjudge.net/contest/178834)の解説を行います。といっても最後の1問が解けていないのですが…

2017-08-13

AOJ2200: Mr. Rito Post Office

数日悩んだ結果問題文誤読と気付いたのでキレそうです。

2017-06-05

AtCoder Regular Contest 075 E - Meaningful Mean

AtCoder

ARCのEは解けるようにならないと不味い。

問題概要

N個数列のN*(N+1)/2個の空でない部分列のうち、算術平均がK以上のものはいくつあるか。

http://arc075.contest.atcoder.jp/tasks/arc075_c

解説

仮平均をすると楽なので、各a[i]からKを引いておくと、「算術平均がK以上」→「総和が非負」に言い換えられます。

累積和を使うと各区間が定数時間で求まるので、O(N²)で解くことが出来ますが、今回はO(NlogN)まで速くしないといけません。自分はここまででした。

b[i]=(a[0]+a[1]+…+a[i-1])-K*(i-1)とすると、b[i](0≦i≦N+1)がバラバラの値として存在していて、b[r]-b[l]≧0となるl,r(l<r)の数を求めるのが問題でした。rを左から順に見ていくとして、b[0],b[1],…,b[r-1]の中にb[r]以下の数がいくつあるかが分かれば問題が解けます。BITを使えばこれがO(logN)で求まるのですが、数が大きすぎるので、座標圧縮の要領でb[i]が何番目に大きいのかを求めたc[i]でBITをすればOKです。c[i]は0～N+1であることが保証されており、後はc[i]以下の数の個数をBITで求めて加え、BITにc[i]を追加する、ということを繰り返します。

BITはyukicoderのこの問題が似ている気がしたので載せておきます。練習用にどうぞ。

http://yukicoder.me/problems/no/59

以下解答プログラムです。結局O(NlogN)まで縮められました。

http://arc075.contest.atcoder.jp/submissions/1330330

感想

この問題の解説には「データ構造を使って計算量を落とす」としか書いていませんでしたし、自分もBIT位しか思いつかなかったのですが、O(N)まで落とせた人はいらっしゃるのですかね…

正直600点問題が解けなかったのは痛いです。実力も最近かなり酷いので、競プロに専念出来る環境が欲しい…