TopCoder Single Round Match 775

　Easyを見て、ちゃんと時間をかければできそうだけど詰めるのは辛そう、とMedへ行くも、Medが分からずの0完でした。Easyをやるべきだったかな、とも思いますが、結局ACするのは難しかった気がします。

Div1 Easy IterateOverACube

　kmjpさんのブログの記事やかっつさんのブログの記事を参考にしましたが、少し違う方法です。

　合計がxになるタプルが何個あるか？　を調べれば良い。場合分けが必要で混乱するけど、

・三次元の問題は断面を考える

　とすれば良いと思う。
　たとえば、N=3で、z軸が0, 1, 2 の場合に分けて考えると、合計が0～6のときの点の位置は、

　 [1, 0, 0]　(0, 0, 0)の一つ
→ [2, 1, 0]　(1, 0, 0), (0, 1, 0)の二つがz=0に、(0, 0, 1)がz=1にある。
→ [3, 2, 1]
→ [2, 3, 2]
→ [1, 2, 3]
→ [0, 1, 2]
→ [0, 0, 1]

　のように変化する。
　なので、L = [1, 2, 3, 2, 1] という配列の長さ3の区間の和となっているので、尺取り法で求めることができる。

　合計が求まった後も、xを固定して同じように考えられる。こちらは、二次元平面上で考えられるので上よりは分かりやすい。

　しかし、この方法だと、色々工夫してもPython2じゃMLEやTLEになってACできなかった。
　えー辛い。私の書き方が悪いだけで、この計算量ならPythonでいけると思うんだけど……。

　Pythonで通せなかったので、C++で実装しました。以下、システムテスト通ったコードです。コメント付けてないし、C++は全く書き慣れていないので読みにくいと思いますが、ACできた証拠に。

#include <bits/stdc++.h>
using namespace std;

class IterateOverACube {
 public:
      vector <int> findCell(int N, long long index){
          index+=1;
          vector <int> L;

          for (int i=1;i=0;i-=1){
                    L.push_back(i);
          }
          for (int i=0;i<=N;i+=1){
                    L.push_back(0);
          }

          int LEN=L.size();
          int i=0;
          int j=0;
          vector<long long> S;
          S.push_back(1);
          long long SUM=1;

          while (i=index){
                       SUM=i;
                       rest=index-(NOW-S[i]);
                       break;
                    }
          }

          NOW=0;
          int x=0;

          for (int i=0;i=rest){
                        rest=rest-(NOW-L[SUM-i]);
                        x=i;
                        break;
                     }
          }

          int SYZ=SUM+1-x;
          int z=min(SYZ,N)-rest;
          int y=SUM-x-z;

          return {x,y,z};

      }
};