CODE FESTIVAL 2016 予選A 参加記
コード祭り2016の予選Aに出ました。
ABCDの4完で全体107位、日本人40位でした。registerフェーズで落ちてなければ予選突破してそう。
・開始
配点が 100 - 200 - 400 - 800 - 1200 なのでとりあえずCを解かなきゃ話にならないなぁと思いCから開く
解法はすぐ思いついたが無限にバグらせて4WA
・20分経過
ひいこら言いながらCを通す
順位表みたら300位とかでおいいいいい、っつった
・25分経過
B, Aと通してDを開く
が に依存しないかつ が に依存しないことはすぐ見えたけどわからず
・40-45分経過
下のツイートの解法を思いついて実装する(自分はハマらなかったけどグラフが連結でない可能性があるので注意)
こんなグラフを作って幅優先して、距離が異なるパスが発見されたらNo、ってした pic.twitter.com/pSRcHULB9K
— りあん♨🍶 (@rian_tkb) 2016年9月24日
・60分経過
実装して提出する
Submission #895510 - CODE FESTIVAL 2016 qual A | AtCoder
サンプルが一個落ちていることにより入れる値が負数じゃダメだという条件を見逃していることに気づく
・75分経過
列の最小値を持って幅優先探索中に更新していけば良さそうと気づいて実装を始める
・85分経過
実装したがWAが取れない
Submission #896588 - CODE FESTIVAL 2016 qual A | AtCoder
仕方ないから幅優先探索後にめっちゃループ回してさらに最小値を更新するか〜〜〜って言う
・90分経過
1 ケ ー ス WA
Submission #896888 - CODE FESTIVAL 2016 qual A | AtCoder
・100分経過
最後のループで300回以上更新があった場合もう負数になるんじゃね? ってNoを出力するコード出したらAC
(コンテスト後にsubmit二分探索したら30回ほどで打ち切って大丈夫だったらしい)
不正感しかないけど通ったからいいんだもん...!
Submission #897265 - CODE FESTIVAL 2016 qual A | AtCoder
不正感が強い pic.twitter.com/Wf66V4zpbh
— りあん♨🍶 (@rian_tkb) 2016年9月24日
あとはゆっくり順位表を眺めてました
(コンテストが終わったあと考察したらこれEのほうが簡単じゃない? ってなった)
とりあえずホントにどうなることやらって感じだったのでホントにホッとしています...
今年もパーカー得たい〜〜〜!!!
あと、予選Bまでに東工大内でコード祭り予選突破練習会開きたいです、協力者(というか主催者)募集中です
ハーフパイプ(2) 解説?
今回、testerをさせていただきました。
問題はこちら
No.398 ハーフパイプ(2) - yukicoder
まずはwriterさんの解説をご覧ください
http://yukicoder.me/problems/no/398/editorial
この問題、想定解法は埋め込みです。testerで問題をもらった時 6*100*100*600*100 = 36億 から落ちないよぉふぇぇ... ってなって解説をカンニングして、は〜〜〜、ってなった記憶があります。
ただ、ちゃんと定数倍改善を行えばこのオーダーでも C++ で 250ms, C# で 900ms で通る(かつ埋め込みのための列挙がほぼ同じ時間でできる!)ようになります。まずはその解説から。
まず dp[index][min][max][sum] というDPを考えます。これの更新式は以下のようになります。
for m in {0..100}:
dp[i + 1][min(j, m)][max(k, m)][l + m] += dp[i][j][k][l]
初期化については、一番左に置く数について埋め込み、
dp[0][i][i][i] = 1
としてしまうのが楽だと思います。
このdpの場合、
sum = x * 4とし、
for i in {0..100}:
for j in {i..100}:
ans += dp[5][i][j][sum + i + j]
とした ans が求めるものです。
このままやるともちろんTLEしますが、端的に言うと dp[i][j][k][l] == 0 の場合に m のループに入らないようにすれば良いです。
というのも、dp[i][j][k][l] == 0 となる場合が(定数倍の範囲内ですが)そこそこあり、その時に内側のループに入らないようにしてあげればループ回数がおよそ1億回ほどになり、C++等で通ります。C#でも1300msほどで通りましたが、Python等の言語では厳しいと思います。
(参考 : http://yukicoder.me/submissions/103388,
: http://yukicoder.me/submissions/103389,
: http://yukicoder.me/submissions/103496)
また、dp[i][j][k][l] > 0 となる l の範囲は連続なので、そこだけループを回すようにしてあげればもう少し早くなります。
(参考 : http://yukicoder.me/submissions/103467,
: http://yukicoder.me/submissions/103495)
dp[i][min][max][sum] > 0 なる sum の 範囲は、
最小値が min + max + max + ... + max = min + max * i,
最大値が min + ... + min + min + max = min * i + max となるので、そこだけ回すとC++で250ms, C#で900msほどになります。
まぁ詳しくはソースコードを読んでください。
さて、そして問題のなんか場合分けして速いの(http://yukicoder.me/submissions/103511)についてですが、オーダーとしては 100^3 です。
やってることとしては単純で、
a + b + c + d + sum && a <= b <= c <= d
なる (a,b,c,d) を全探索し、一つ一つに対して min <= a なる min と d <= max なる max を追加した時の並べ方の場合の数を数え上げています。
min と max については、
・min == a && d == max
・min < a && d == max
・min == a && d < max
・min < a && d < max
の 4通りだけ調べればOK。
並べ方の場合の数については、
{a,a,a,a,a,a} : 1
{a,a,a,a,a,b} : 6C1 = 6
{a,a,a,a,b,b} : 6C2 = 15
{a,a,a,b,b,b} : 6C3 = 20
{a,a,a,a,b,c} : 6P2 = 30
{a,a,a,b,b,c} : 6C1 * 5C2 = 60
{a,a,b,b,c,c} : 6C2 * 4C2 = 90
{a,a,a,b,c,d} : 6P3 = 120
{a,a,b,b,c,d} : 6P2 * 4C2 = 180
{a,a,b,c,d,e} : 6P4 = 360
{a,b,c,d,e,f} : 6P5 = 720
となります(実際に解いた時に用いたメモを紛失したので間違ってるかも...、変なとこあったら教えてください><)
あとはこれを落ち着いてコードに起こすと、以下のコードになります。
#include <iostream> using namespace std; int main() { int a, b; scanf("%d.%d", &a, &b); int sum = (a * 100 + b) / 25; long long ans = 0; for (int i = 0; i < 101; ++i) { for (int j = i; j < 101; ++j) { for (int k = j; k < 101; ++k) { int l = sum - i - j - k; if (l < k) break; if (l > 100) continue; int m = 100 - l; if (i < j && j < k && k < l) ans += 180 + (i + m) * 360 + i * m * 720; else if (i == j && j < k && k < l) ans += 60 + i * 180 + m * 120 + i * m * 360; else if (i < j && j == k && k < l) ans += 90 + (i + m) * 180 + i * m * 360; else if (i < j && j < k && k == l) ans += 60 + i * 120 + m * 180 + i * m * 360; else if (i == j && j < k && k == l) ans += 20 + (i + m) * 60 + i * m * 180; else if (i == j && j == k && k < l) ans += 15 + i * 60 + m * 30 + i * m * 120; else if (i < j && j == k && k == l) ans += 15 + i * 30 + m * 60 + i * m * 120; else if (i == j && j == k && k == l) ans += 1 + (i + m) * 6 + i * m * 30; } } } cout << ans << "\n"; return 0; }
もしこれが想定解法として提示されたら窓からMacBookAirを投げ出すレベルの解法ですが...
まぁこんな面倒くさい場合分け、競プロerだとあんまりしないですけど、そこまで競プロになれてない人だと逆にこっちで頑張るのが自然かも、とも思いました。
Segment treeを整備したという日記
(2019/10 追記:自分のライブラリを GitHub で管理するようにし始めたので、最新版が以下から参照できます)
github.com
最近Sumsegtreeを使う問題を解いたら、持ってたSumsegtreeがバグってたので、ついでにもっと色々使えるように手直ししたのでその備忘録みたいなものを書きます。
c#でのsegtreeのコード載せてるページ少ないし、ね。
なお、基本的に秋葉大先生のスライドをとても参考にさせていただいて作っているので俺の記事は読まなくていいのでこちらをお読みください
プログラミングコンテストでのデータ構造
以下コードです。
using System; class Segtree<T> { int n; T[] tree; Func<T, T, T> f; T exnum; public Segtree(int m, Func<T, T, T> f, T ex) { this.f = f; this.exnum = ex; n = 1; while (n < m) n <<= 1; tree = new T[(n << 1) - 1]; for (int i = 0; i < tree.Length; i++) tree[i] = ex; } public Segtree(int m, T ini, Func<T, T, T> f, T ex) : this(m, f, ex) { for (int i = 0; i < m; ++i) tree[i + n - 1] = ini; all_update(); } public void assign_without_update(int j, T x) { tree[j + n - 1] = x; } public void update(int j, T x) { int i = j + n - 1; tree[i] = x; while (i > 0) { i = (i - 1) >> 1; tree[i] = f(tree[(i << 1) + 1], tree[(i << 1) + 2]); } } public void all_update() { for (int i = n - 2; i >= 0; i--) tree[i] = f(tree[(i << 1) + 1], tree[(i << 1) + 2]); } public T look(int i) { return tree[i + n - 1]; } // [s, t) public T run(int s, int t) { return query(s, t, 0, 0, n); } T query(int s, int t, int k, int l, int r) { if (r <= s || t <= l) return exnum; if (s <= l && r <= t) return tree[k]; return f(query(s, t, (k << 1) + 1, l, (l + r) >> 1), query(s, t, (k + 1) << 1, (l + r) >> 1, r)); } }
(2016/04/19 : iniが指定されていない時にexnumで初期化するように設定しました)
(2016/10/03 : 色々細かいところを修正したのと、全体の初期化を でなく で実現するための関数を追加、あと半開区間にしました!)
まず、型を自由に指定できるようにしてあります、これは基本的にはlongにしとけばどうにかなるのであんま意味ない気もしますが、doubleにしたい時とか
D: タコヤキオイシクナール - AtCoder Regular Contest 008 | AtCoder
とかだとまぁ楽かなぁという気がします。
それでは、変数の解説をしていくと、
・Func
Func
また、MaxとかMinだと Math.Max とか Math.Min を渡してあげるだけで動きます、嬉しい。
その他でも、f(x1, f(x2, x3)) = f(f(x1, x2), x3) を満たす関数なら動くのかな...? 理学部じゃないのでわからん。
・T exnum
exnum は、区間が範囲外の時に返す値を入れる変数で、とても弱い値を入れておけばokです。例えば、Sumの時は0, Maxの時は-∞, Minの時は+∞, といったように。
・T ini
ini は、初期化用変数です。別にいらないような気もするかもですが、Tがclassだったりすると馬鹿みたいにランタイムエラーを起こすのであったほうが良いです。
あとは前述したスライドとほぼ同じなので、これで使えます。
一番の肝はコンストラクタで初期化する時で、そこがちゃんと出来てしまえばあとは毎回同じように使えます。めっちゃ嬉しい。
こちらが使用例になります。
Submission #694898 - AtCoder Regular Contest 033 | AtCoder
Submission #694924 - AtCoder Regular Contest 008 | AtCoder
#118362 No.426 往復漸化式 - yukicoder
(2016/10/03 : 使用例を追加しました)
最小費用流とか平衡二分探索木とかも持っとかなきゃなぁという気はしてる(書く気は起きない)。
No.335 門松宝くじ, No.336 門松列列
奇跡的に全完できたけど、普通にクソ苦手なセットだった
門松列の流行早く終わってくれ
No.335 門松宝くじ - yukicoder
No.336 門松列列 - yukicoder
門松宝くじは、当確率である2つの数字が選ばれたとき、3つの数字が門松列かつ3つの数字のmaxが最大になるようにもう1つの数字を選ぶようにして、そのときのmaxの期待値を出す問題(自分でも何を言っているのかわからない…)
普通に全部の選ばれる数字の組(通り)に対して ()通り全探索すると となりダメ(最初、800^3 = 2400万だと勘違いしてこれで出した)
そこで、選ばれた2つの数字について具体的に考えていきます
- 選ばれた2数a, b(a < b)について、元の順列におけるindexが index[a] < index[b] のとき
下図(横軸 : index, 縦軸 : 数値)で適当に赤く塗られたところの数をあと一つの数として選べば、3数は門松列になります
ここから、実は区間のMaxとminさえ持っていれば良いことがわかります
max[i][j]を区間[i, j]におけるMax、min[i][j]を区間[i, j]におけるminとすると、
max[0][index[b] - 1] > b のとき ...... 得点は max[0][index[b] - 1]
max[0][index[a] - 1] > a のとき ...... 得点は b
min[index[b] + 1][n - 1] < b のとき ...... 得点は b
min[index[a] + 1][n - 1] < a のとき ...... 得点は b
上のいずれにも適さないとき ...... 門松列を作れないので得点は 0
max[i][j], min[i][j] を前もって で求めておけば、各組に対して定数時間で求めることができ、結果 となります
index[b] < index[a] のときも同じような感じで求めることができます
門松列列は、順列の並び替えの中でジグザグな列は何通りあるか、という問題
(どっかで見たことある気がするけど、題意は または となる i が存在しないことと同義)
まぁ、DPを考えます。
i - 1番目の数がi番目の数より大きかったかどうかで、i + 1番目にどのような数を置けるかが決まります
(例えば ......, 6, 4 というところまで数列を作っていたら、次の数は5以上でなければならない)
使える数字は決まっていて、一度使った数字は使えないので、次に置ける数字がm個、次に置けない数字がn個だとすると下図のようになります
このとき、次のような漸化式が成り立ちます
dp[m + n][m] = dp[m + n - 1][n] + dp[m + n - 1][n + 1] + ... + dp[m + n - 1][m + n - 1] (dp[0][0] = 1)
(dp[m + n - 1][k] は、次に置ける数の中でk - n + 1番目に小さい数を選んだときの場合の数)
これをこのままループを回すと となりますが、
sum[i][j] = dp[i][k]
を順次求めておけば となり、間に合います
求めるものは、sum[N - 1][N] * 2 です
なんかすごい変なDPをしている自覚はあります......
それぞれ、提出はこんな感じです
#71404 No.335 門松宝くじ - yukicoder
#71459 No.336 門松列列 - yukicoder
(P,Q)-サンタと街の子供たち 解説(?)
なんかめっちゃ面白い問題だなぁ、と思いかつ上手くハマって解けたので、つたないですが解説記事を書かせていただきます。
(お昼に間違ってフライング投稿しちゃってて慌てて非公開にしましたごめんなさい><)
問題はこちら
No.321 (P,Q)-サンタと街の子供たち - yukicoder
ナイトはチェス盤のすべてのマスに到達できるが、それ以外の距離の移動のみではどうなるか? というもの
まずは、例外処理から(以下、 とし、各座標はすでに絶対値を取ってあることとします)
- (p, q) = (0, 0) のとき
自明に動けないので、 となる点がいくつあるか探します( が書いてなかったように思うのですが、できればどちらか明記していただけるとありがたかったかも、書いてあったらごめんなさい>< )。
- p = 0 のとき
ならばいけるので探します。
- gcd(p, q) > 1 のとき
必要条件として、 が挙げられます。かつ、p, q が互いに素となる状態にして後述の条件を満たすか判別すればよいです。
- p, q が互いに素のとき
とりあえず、チェス盤を考えます。
まず、ナイトと同じな (p, q) = (1, 2) のときを考えると、最初は (0, 0) の白マスにいて、移動した先は必ず黒マスになっています。
次に、(p, q) = (1, 3) を考えると、白マスにしか到達することができず、絶対に黒マスに到達することができません。
ここで、次のような仮定をすることができます。
「すべてのマスに到達できる ⇔ gcd(p, q) == 1 かつ (p + q) % 2 == 1」
かつ、
「gcd(p, q) == 1 かつ (p + q) % 2 == 0 ⇔ すべての白マス( (x + y) % 2 == 0 ) に到達できる」
本番では、私はこれを証明せずに投げて通してしまいました。
ここに証明を書いてもいいのですが、writerさんが解説ページで証明っぽいのをなされているのでここでは割愛させていただきます(めんどいし)。
http://yukicoder.me/problems/849/editorial
23分ほどでACし、7番目くらいでした。あんまこじらせないでさっと行けてよかった……。