naoya_t@hatenablog

いわゆるチラシノウラであります

CodeChef September Long Challenge 2017

f:id:n4_t:20170912134258j:plain
https://www.codechef.com/SEPT17
9/1 15:00IST 〜9/11 15:00IST

今回は全問からちょこちょこ(=部分点多数)得点できた。
最終104位。
(新レーティングまだ出てない)
→総合2195(+108), Long Challenge2043(+173)
f:id:n4_t:20170914055127p:plain:w288 f:id:n4_t:20170914055146p:plain:w288
(最初の数問だけ解いて放置した前回の失点が痛い)

CodeChefのLong Challengeはハードな時間制限がないし再提出についても緩い(ペナルティもないし、TopCoderのMMみたいな2時間待ちもない)から、問題だけ読んでおいてふと思いついたときに解いて時間のあるときに提出できるのが良い。趣味でやってる社会人競プロ勢に優しい。
cf.
上司に言われたこと「社会人になったら趣味を持て!」その理由に納得の声 - エキサイトニュース(1/3)




Editorial: Questions Tagged With sept17 - CodeChef Discuss

Little Chef and Sums (CHEFSUM; 9567, 29.45%)

https://www.codechef.com/SEPT17/problems/CHEFSUM

あるインデックス i より前の総和(a_iを含む)と、i から後の総和(a_iを含む)の合計は当然全体の総和+a_iの値なわけで。a_i が一番小さい値になる i(で一番最初に来るやつ)を返すだけ。
→AC (100pts)
https://www.codechef.com/viewsolution/15216355

Minimum Good Permutation (MINPERM; 8963, 63.67%)

https://www.codechef.com/SEPT17/problems/MINPERM

全てのiについて a_i ≠ i になる辞書順最若permutationを求めるやつ。
左から2つずつひっくり返したやつ。最後が3つになるときだけそこはrotateしたやつ。
→AC (100pts)
https://www.codechef.com/viewsolution/15216514

Chef and Pick Digit (CHEFPDIG; 7370, 35.31%)

https://www.codechef.com/SEPT17/problems/CHEFPDIG

0〜9の各数字の出現回数を数えておいて(O(N))、65〜90が表現できるか調べる。66,77,88はそれぞれ2回以上出ている必要があるとかその程度。
→AC (100pts)
https://www.codechef.com/viewsolution/15216703

Fill The Matrix (FILLMTR; 1469, 7.92%)

https://www.codechef.com/SEPT17/problems/FILLMTR

相互の差が0か1か。
a[i] は x か x+1 (xは任意の数)になるんだよね
ていうか、等しいか等しくないか、の真偽値でよくね?
とすると
これ2-SATで解けるじゃん
どっちがどっちに相当するか一瞬悩んだけど
→AC (40pts) 1つWA...
https://www.codechef.com/viewsolution/15258606

1e5 x 1e5 だとvisitedの判定キーがオーバーフローするじゃん
そこlong longにして
→2投目AC (100pts)
https://www.codechef.com/viewsolution/15258614

Sereja and Commands (SEACO; 1886, 6.8%)

https://www.codechef.com/SEPT17/problems/SEACO

2 i j で出てくる区間は時間軸(m)
1 i j で出てくる区間は空間軸(配列のインデックス; n)
で、いもす法で行けるのかな

k 番目の命令まで処理した後の状態を a_k とすると、
漸化式
a_k = a_(k-1) + 命令内容
2 i j の場合、a_k = a_(k-1) + (a_j - a_(i-1))
1 i j の場合、a_k = a_(k-1) + b_k
ここで b_i は、長さNの、[i..j] が1でそれ以外は0の配列に相当するんだけど、最後にいもす回すから実際は a[i]+=1, a[j+1]-=1 だけの処理
求めたい値は a_mで、
a_mをa_1 .. a_(m-1) で表現(高々3要素に置換される)したりb_kに足しこんでいったりするだけ。計算量は O(M+N) とかじゃないかな。
→1投目WA
https://www.codechef.com/viewsolution/15265499
largeケースの一部だけACで、small, mediumがWA。一部SEGV。

ああ
mって書くべきところをnで回してるわ。naoya_tあるある。
(m=n=1e5、みたいなケースだと通るわけだ)
そこだけ直して
→AC (100pts)
https://www.codechef.com/viewsolution/15265666

Weasel does Xor on Tree (WEASELTX; 258, 2.67%)

https://www.codechef.com/SEPT17/problems/WEASELTX
これ同じパターンの繰り返しだ

oooooooo
o-o-o-o-
oo--oo--
o---o---
oooo----
o-o-----
oo------
o-------

2x2のパターンは右下だけ空(NANDっぽい)
4x4のパターンは2x2のパターンを並べたもの(右下だけ空)
8x8のパターンは…
って感じ
フラクタルっぽい
5000ぐらいまでなら余裕
→ AC (50pts)
https://www.codechef.com/viewsolution/15280557

2e5 x 2e5だと…クエリ前に準備しておけない…O(N^2) な解法は無理
これを、半分だけ準備して残り半分はクエリ時に計算するとかできないかな
512(≒√N)ぐらいのブロックだけ用意して、どのブロックに該当するかはクエリ時に求める、みたいな
O((N+Q)√N) 解法が出来た
→AC (100pts)
https://www.codechef.com/viewsolution/15289873

Sereja and Functions [チャレンジ問題] (SEAFUNC; 203, 50.82%)

https://www.codechef.com/SEPT17/problems/SEAFUNC
とりあえず、1点ずつを定数出力するQ=N^2的解法で問題をちゃんと理解できてるか試す
→WA
0-baseと1-base間違えてる?
→直したけどWA

問題を読み返す。

とりあえず何このサンプルケース
スリードする気満々じゃないか
水平方向にx軸, 垂直方向にy軸が伸びてて y=f(x) みたいになってると思うじゃん
違うんだ
垂直方向にr軸、水平方向にc軸があって c=f(r) なんだよね
サンプル出力最下行の

0 1 0 1 0 1 5 1 5

は、入力最下行の 11111 にはまってないんだよね
このサンプル出力は

00001
00101
01001
10001
00001

みたいなことになる。100箇所まで間違ってていいという条件があるからこれでもACなんだよね。

というわけで、x/y軸を入れ替えたら
→AC (3.2pts)
https://www.codechef.com/viewsolution/15302150
これだけでも3点か。

で、とりあえず、1次式を投入。適当な傾きで繋がってる点同士を直線で繋いでいくやつ。
パラメータ全パターン試すには時間がなさすぎる(Time Limit = 1 secs)
→AC (26pts)
https://www.codechef.com/viewsolution/15366549

ところで、100箇所まで間違ってていいってことは

00000
00000
00000
00000
00000

だろうが

11111
11111
11111
11111
11111

だろうが構わないってことで。

未処理の点が100箇所になったらそこで打ち切って提出してしまっていいってことだ。
(サンプルケースみたいに1が100箇所以内なら出力は Q=0 でいい!実際にはそういうテストケースは来ないだろうけど)
→ AC (29.4pts)
https://www.codechef.com/viewsolution/15366605

一箇所修正したけど点数変わらず
https://www.codechef.com/viewsolution/15368374

とりあえずここまで;

Sum of Cubes (SUMCUBE; 76, 4.85%) 部分点

https://www.codechef.com/SEPT17/problems/SUMCUBE

Subtask #1 (8pts): n≦15なら全部列挙しても間に合う。

Subtask #2 (7pts): k=1;それぞれの辺が、頂点n個のsubgraphで何回使われるかは求められるからそれを足し合わせるというか掛け合わせるだけ。

→AC (8+7=15pts)
https://www.codechef.com/viewsolution/15305988

Subtask #3 (9pts) k=2のケース。いろいろこねくり回したけど式が立てられずここまで;

Weasel finds Staircase (WEASELSC; 52, 1.52%) 部分点

https://www.codechef.com/SEPT17/problems/WEASELSC

どこを段差にするか、貪欲に切り出してみたり。
→WA
サンプルケースは出来てるっぽいんだけどな…

とりあえず、K=0だけでも通すか
これってhistogram[] の最小値を返せばいいんじゃない?
→WA

なんか読み違えてる?

0 1 1 0 のとき、0の箇所は「使わない」というか「使えない」のか。
1以上の所だけで最大面積の長方形を切り出さないといけないのか;

ってどうやる?
とりあえず左から眺めて、高さがいくつの柱がどこにあったかをpriority queueに放り込んでみたいな解法を書いて
→ AC (K=0のみ。10pts)
https://www.codechef.com/viewsolution/15368323
ここまで

Querying on a Grid (QGRID; 25, 1.56%) 部分点

https://www.codechef.com/SEPT17/problems/QGRID

Subtask #1: ある点からある点への経路は全て事前に求めておけるし、クエリの度に経路を移動しながらインクリメントしていくシミュレーションで間に合う →AC (6pts)

https://www.codechef.com/viewsolution/15363036

Subtask #2: クエリの度にインクリメントをやってたら O(QN) で間に合わないよね;でもM=1ってことはすべてが一直線上にある。経路は1本道。先にtype1を全部処理して、いもすして、type2を処理する →WA

ああ、クエリが来る前のtype 1しか考慮に入れてはいけないんだ(当然か)
というわけで
segment tree上でいもすっぽい事をして
→AC (6+11=17pts)
https://www.codechef.com/viewsolution/15363210