nobu-qの日記

■[PKU][AC] 3009 15:01

反復深化で47ms。その後実験でBFSしてみたらTLEｗｗｗ 最悪 (50+座標) * 4^10 byte 必要なのでメモリ的にも危ないとは思ったけど。

■[PKU][AC] 1009 16:07

http://www.acm.inf.ethz.ch/ProblemSetArchive.html

アーカイブを発見。sample inputとoutputをゲットしてデバッグ完了！

1000000000*3は負になっちゃいますよね／(^o^)＼

それだけでした／(^o^)＼

■[PKU][AC] 3007 18:46

ちょっと訳ありで速くしてみた。

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

struct Data {
    const char* s1;
    int l1;

    const char* s2;

    Data(const char* s1, int l1, const char* s2)
        : s1(s1), l1(l1), s2(s2) {}

    char operator [](int n) const {
        if (n < l1) return s1[n];
        else return s2[n - l1];
    }
};

int Length;

bool operator <(const Data& lhs, const Data& rhs)
{
    for (int i = 0; i < Length; i++) {
        if (lhs[i] != rhs[i]) return lhs[i] < rhs[i];
    }
    return false;
}

bool operator ==(const Data& lhs, const Data& rhs)
{
    for (int i = 0; i < Length; i++) {
        if (lhs[i] != rhs[i]) return false;
    }
    return true;
}

int main()
{
    string str, rstr;
    
    vector<Data> s;
    int t;

    cin >> t;
    while (t--) {
        char tmp[128];
        scanf("%s", tmp);
        s.clear();

        str = tmp;
        rstr = str;
        reverse(rstr.begin(), rstr.end());
        Length = str.size();

        const char* s1 = str.c_str();
        const char* r1 = rstr.c_str();

        s.push_back(Data(s1, Length, NULL));
        s.push_back(Data(r1, Length, NULL));

        for (int i = 1; i < Length; i++) {
            // back + front(same order)
            s.push_back(Data(s1 + i, Length - i, s1));
            s.push_back(Data(r1 + i, Length - i, r1));

            // front + r_back, r_back + front
            s.push_back(Data(s1, i, r1));
            s.push_back(Data(r1, i, s1));

            // r_front + back, back + r_front
            s.push_back(Data(r1 + i, Length - i, s1 + Length - i));
            s.push_back(Data(s1 + Length - i, i, r1 + i));
        }

        sort(s.begin(), s.end());
        s.erase(unique(s.begin(), s.end()), s.end());

        cout << s.size() << endl;
    }
}

適当でサーセンｗ cinとscanf混ぜて使って良いのは小学生までだよねー。Lengthはグローバル変数だから、最適化されずに毎回読み込まれたりしてねーよなーとかの心配事や、そぎ落とせそうな贅肉はまだあるけどとりあえず94ms。1位は76ms。とりあえず使ってるアルゴリズムは違わなそうなので安心。あまりに時間がかかるから、何か変な方法使ってんのかな？とか思ってしまった。ところでメモリ使用量はどうやると減るんでしょうかうううう。

つかPKU最近タイマー変わった？ちょっと古いタイムと約16のアライメントが違う気がする。

■[ICPC][PKU][AC] 2684: Polygonal Line Search 00:03

2684 -- Polygonal Line Search

久々にやった。今年は頑張って東大勢とさいたま+その他大勢の猛者に勝つ！今年はほぼ確実にawakiaと出れる最後のICPCなので気合い入ってます。もう一人の新チームメイトもポテンシャルがやばいので気合いマシマシ。俺自身も留学することになったら来年は出られないので、その点でも必死(仮に東大に入れたら誰か俺を受け入れてくださいｗ)。

で、解いてみた。同じ形をした図形を探す問題。制約が多く、

• 図形は線で構成される
• 線はX,Yのどちらかの軸に平行である
• 回転、平行移動した図形のみ同じ形と見なす(拡大縮小は含まれない)
• 線は左右どちらかに90度曲がる事しかできない

という感じ。これを使うとうまく解ける。まずは線分を

移動距離, 曲がった方向, 移動距離, 曲がった方向, ..., 移動距離

と言うデータに変換する。こうすることで平行移動と回転を無視して図形を比較することができる。一つ注意すべき事として、図形には端点が2つあるので、2通りのデータができあがると言うこと。もう片方の端点から辿ったデータは、元のデータをreverseしてから、曲がった方向を反転させてやれば良い。あとは残りの図形のデータを入力し、その二つと比較して終了。

久しぶりだったので頭がなまってた。来週から本格的にリハビリ開始。

■[PKU][AC][prog][memo] 1458(LCS) 17:30

昨日の反省をふまえてLCSを色々作ってみた。昨日のfox(笑)のid:awakia-n案も実装してみた。結構綺麗に出来たと思う。O(NM)。合ってるか分からんけど。

考え方。LCSの性質上、文字列x, yの順序を逆転した物をx', y'としたとき、lcs(x, y)とlcs(x', y')の内容は変わっても長さは変わらない。なので、[xi, 末尾]、[yi, 末尾]の区間のLCSの長さはx'とy'に置き換えて考えると[0, xi']、[0, yi']の区間のLCSと同じになる。よって、予め通常の文字列とreverseした文字列でLCSのテーブルを作って置く事でプログラムが綺麗になるかもという感じ。