POH

2015-09-14

Tech

OI, Paiza, 日常

Paiza 的第6期入门挑战和第6期+的题解
对 POH 的吐槽
对刷 Paiza 题库的惨痛记忆/OI etc

Paiza 的新一期入门挑战（EN），现在是第6期了。代入情景的漫画一样充满槽点满满。（←请吐槽）OOPArt、COBOOL（日文版我没看出是什么，直到看了英文版），还有乱入的类型推导……

我记得我做过第4期。印象中第4期的还是很简单的。（今天看了一下，确实。）

本期的三个问题还是很简单。大胃王（六村リオ）的题就是照着指令运算；大和抚子（緑川つばめ）的题也是……而且5行（3行）就可以了：

void main() {
    char buffer[5];
    gets(buffer);
    printf("%d", 11 * (buffer[0] - '0') + 2 * (buffer[1] - '0'));
}

至于天才（霧島京子）的题，差点就过不去了。粗看题目还以为是求到达终点的最快走法，如果走不到输出“不可能”这样的东西。当时就在想：逆推？回溯搜索？循环判定？循环节引起超限怎么办？

再看题，原来还是一个简单的题目，往下走就可以了……于是在 Notepad++ 中手写，提交，AC。

选用的还是 C#。感觉由于委托（delegate）被作为基础类型看待，CLR 上的语言都有函数式语言的潜质（或者已经是了，如 F#），这点我非常喜欢。就这一点就足以让我在能选 C# 的时候就不选 Java。（当然还有其他原因。）

public class Hello {
    public static void Main() {
        bool[] history;
        int[] cells;
        int n;

        // Let's challenge in my favorite language!!
        string line;
        line = System.Console.ReadLine();
        n = int.Parse(line);
        cells = new int[n];
        line = System.Console.ReadLine();
        var s = line.Split(' ');
        for (var i = 0; i < n; i++) {
            cells[i] = int.Parse(s[i]);
        }

        var canGo = new System.Func<int, bool>(num => {
            if (num == n - 1) return true;
            if (num > n - 1) return false;

            var current = num;

            history = new bool[100];
            history[0] = true;

            while (current != n - 1) {
                history[current] = true;
                current = current + cells[current];
                if (history[current] || current < 0 || current > n - 1) {
                    return false;
                }
            }

            return true;
        });

        line = System.Console.ReadLine();
        var qcount = int.Parse(line);
        var results = new bool[qcount];
        int k;
        for (var i = 0; i < qcount; i++) {
            line = System.Console.ReadLine();
            k = int.Parse(line);
            results[i] = canGo(k);
        }

        for (var i = 0; i < qcount; i++) {
            System.Console.WriteLine(results[i] ? "Yes" : "No");
        }
    }
}

第5期一样简单。但是背后隐藏着的第5期+则开始玩 OI 了。五月份的时候lan发了链接，当时看到第一题想不出一个最快的解法（虽然题目没有要求最快；这种拼图在现实中也很令我头疼）就没做下去了，到现在都没做。后来lan说她刷完了，“挺简单的”。这印证了我的结论，不要和lan讨论题目，否则你会被虐的体无完肤。

当然，Paiza 本身是一个面向程序员的猎头公司，OI 是其附带的功能。这里可以选择题目做（需要登录）。我和lan曾经在发现这个网站后去刷S级的题目……结果我的解题速度被lan碾压，评价也被碾压（lan基本上是一次AC）。求我的心理阴影面积。

这里是第6期+。

今天看博客园文章的时候发现新东西“主席树”。百度了之后找到了一个 OIer 的博客。这位仁兄也是相当厉害，看他的回忆文章就能看得出。

第6期+也做了，只有一道题……

标题也是十分恶搞。回文就回文吧，赶上了第7届松江 Ruby 大会，还专门构造了一个例子，就拿“松江”（まつえ）开涮：

え、妻(つま)が松(まつ)江(え)？

诶，爱人是松江？

然后就出题了：找出给定输入能构造出的回文字符串中最长且字符序最小的。

其他的吐槽：看下面的“豪华礼物”（如果选用 Ruby 回答，速度最快的几段代码会在会议上展示，并且可以抽奖）部分。第一个就是限额三名的揖保の糸。（就是第6期漫画里出现的。安得一手好利啊。）

这道题也挺简单的……暴力法居然也AC……

using System;
using System.Collections.Generic;
using System.Linq;

static class Program {

    static bool stringIsPalin(string s, int n) {
        for (var i = 0; i < n / 2; i++) {
            if (s[i] != s[n - 1 - i]) {
                return false;
            }
        }
        return true;
    }

    static void Main(string[] args) {
        var line = Console.ReadLine();
        var n = int.Parse(line);
        // 存放所有的非回文字符串
        List<string> rolls = new List<string>(n);
        // 存放所有的回文字符串
        List<string> palins = new List<string>(n);
        // 构造字符串时，对应索引的非回文字符串是否已经被使用过
        bool[] used;
        string s;
        int stringLen = 0;
        for (var i = 0; i < n; i++) {
            s = Console.ReadLine();
            if (i == 0) {
                stringLen = s.Length;
            }
            if (stringIsPalin(s, stringLen)) {
                palins.Add(s);
            } else {
                rolls.Add(s);
            }
        }
        used = new bool[rolls.Count];
        if (palins.Count > 0) {
            palins.Sort();
        }
        var result = "";
        string r2 = null;
        int j;
        rolls.Sort();
        var count = rolls.Count;
        if (count > 0) {
            for (var i = 0; i < count; i++) {
                if (!used[i] && i < count - 1) {
                    j = rolls.IndexOf(new string(rolls[i].Reverse().ToArray()), i + 1);
                    if (j >= 0) {
                        // used[i] = true;
                        used[j] = true;
                        result += rolls[i];
                    }
                }
            }
        }
        if (result.Length > 0) {
            r2 = new string(result.Reverse().ToArray());
        }
        if (result.Length > 0) {
            if (palins.Count > 0) {
                result += palins[0] + r2;
            } else {
                result += r2;
            }
        } else {
            if (palins.Count > 0) {
                result = palins[0];
            }
        }
        Console.WriteLine(result);
    }

}

就是这样。居然暴力法都能过……原本还想着不行的话就加个索引的……如果字符串不等长的话就建二重索引……结果都是小题大做。看来第5期+耐心玩的话也可以用暴力法过……（题目提示移动一个方块到指定位置只要随机走很可能在一万步内完成。）