CODE THANKS FESTIVAL 2017で解けなかった問題群
この記事はTSG Advent Calendar 2017の15日目の記事として書かれました。空いていたので放っておきます。
最近、多忙で競技プログラミングの進捗が埋めていないのですが、取り敢えず2問。それぞれ出てきた2解法ずつ取り上げます。
続きを読むTSG第3回コードゴルフ大会
8/19からの1週間に渡って行われたコードゴルフ大会ですが、ここで初めてのコードゴルフに挑戦してみました。この大会は今までEsolang大会だったものにコードゴルフ要素が加わったことで今回からコードゴルフ大会に名称が変わったそうです。
ルール説明
3チームに分かれて行います。初めに3チーム1マスずつ当てられています。
支配しているマスの隣のマスについて、指定された問題をマスに書かれている言語で書くことでそのマスを支配できます。
既に他のチームに取られてしまっている隣り合っているマスは、そのチームのコードの文字数（マスに書かれている）よりも短いコードを書くことで上塗りして支配が出来ます。
期間は1週間です。
というものでした。お題は、
8桁の2進数で与えられた数が三角数かどうか判定せよ。入力は50個の数からなる。三角数なら1、そうでないなら0を出力せよ。
というものでした。私は赤チームだったのですが、緑チームにかなりのプロ2名がいらっしゃったようで、残念ながら自分の書いたコードは他の方に塗りつぶされてしまった・それによって提出する権利を失ってしまったのですが、Esolangの習得に関してはまあまあ頑張れたかな、と思ったので、自分のやったものについて、書いた順に触れていきます。
続きを読む競プロerキャンプ in 関東
8/17～18の間に行われた競プロerキャンプ in 関東。達也さん（@tatuyan_edson）、迷路さん（@pazzle1230）を中心に私含め5名の少数人数ながら、楽しい時間を過ごすことが出来ました。
さて、今回はその合宿初日に行われたVirtualContest(https://vjudge.net/contest/178834)の解説を行います。といっても最後の1問が解けていないのですが…
続きを読むAOJ2200: Mr. Rito Post Office
数日悩んだ結果問題文誤読と気付いたのでキレそうです。
続きを読むAtCoder Regular Contest 075 E - Meaningful Mean
ARCのEは解けるようにならないと不味い。
問題概要
N個数列のN*(N+1)/2個の空でない部分列のうち、算術平均がK以上のものはいくつあるか。
http://arc075.contest.atcoder.jp/tasks/arc075_c
解説
仮平均をすると楽なので、各a[i]からKを引いておくと、「算術平均がK以上」→「総和が非負」に言い換えられます。
累積和を使うと各区間が定数時間で求まるので、O(N2)で解くことが出来ますが、今回は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点問題が解けなかったのは痛いです。実力も最近かなり酷いので、競プロに専念出来る環境が欲しい…
Codeforces Round #416 (Div. 2)
実力不足が出てきているので、ちゃんとブログ活用して精進しなくては…
続きを読むAtCoder Regular Contest 073 E - Ball Coloring
長らく解けなかったので掲載。
問題概要
N組の2個のボールの組が与えられる。各組の片方を赤、もう片方を青に着色していったとき、赤のボールの範囲*青のボールの範囲の最小値を求めよ。
E: Ball Coloring - AtCoder Regular Contest 073 | AtCoder
解説
AtCoder Beginner Contest 060 / AtCoder Regular Contest 073 解説 - はまやんはまやんはまやんを参考にしています。AtCoderの解説準拠です。
ボールを2色に分けるのですが、全体の最小値と最大値は必ずRmax、Rmin、Bmax、Bminのいずれかに属します。よって最大値と最小値がどちらに属するかで場合分けします。
最大値と最小値が異なる色のとき 最大値を赤、最小値を青とします。ここで、赤は小さいほう、青は大きい方を求める必要があります。赤の最小値を大きく、青の最大値を小さくすればいいのですが、これは色を塗るときに組の大きいほうを赤、小さいほうを青に塗ればよいです。
ということで、各組の大きいほう、小さいほうからのみなる配列を作って、その最大値-最小値をかければOKです。同じ色のとき 赤が最大値、最小値両方占めたとしましょう。すると、残りのN-2組から任意に片方だけ抜いていった時の最大値-最小値が小さくなればよさそうです。取り敢えず全部の組で小さいほうを選んだとして、その後値の小さい組から入れ替えていって、入れ替え後に最小値が大きくなる間更新し続けます。(逆に大きいほうだけを抜き出し、最大値を減らしても求める）。参考にしたurlでは一気にセグメント木で殴っていたので、自分もそうさせていただきました。
Submission #1259798 - AtCoder Regular Contest 073 | AtCoder
感想
最初、x,yが出ていて、「(x,y)か(y,x)に点を置いていくときに、点すべてを中に含む長方形の面積の最小値を求めよ」という風に解釈して苦労したのですが、こっちの考え方で解いた強者いらっしゃいますかね…
