2019-01-01

2018年の振り返りと2019年の抱負

まず去年の抱負の振り返り。

一日7時間睡眠

達成率70%くらい。9月くらいからはメシにも気を付けていい感じ。

年収+10%

達成率140%！！天才だと思われる。

プロコン再開

まあLeetCode毎週でてるし、Long Challengeも参加多いので、再開したといってよい。

2019年の抱負はこちら。なお生活系がキャリア系に優先するものとする。

生活系

一日7時間睡眠＋ちゃんとメシ

体を壊すと家族が困る。死守。

5時帰宅+土日は家族と

過去4年ずっと維持してるけど、だいじなので明言しておく。

筋トレ続ける

いまの生活を続ければよいけど、これも明言する。体だいじ。

キャリア系

年収+10%

プロジェクトがアレしてアレすれば+20%も夢ではないはず。

LeetCodeのWeeklyで3完安定

ほぼ出来てるが挙げておく。業務・ホワイトボードコーディングではこれで十分でしょ。

Kaggleに浸かる

やっと沼に堕ちることを決意しました。具体的なランク的な目標は3月くらいまでに決めます。

英語

就活で足を（あんまり）引っ張らないくらいに英語を伸ばす。具体的には vocabulary.com を日常的にやる。

「Kaggleに浸かる」以外は「日常生活を続ける」に等しいが気にしない。

2018-12-24

C#で競技プロするときの部品集

Competitive Programming (2) Advent Calendar 2018の12/25分の記事です。

C#は良い言語なのですが、競技プログラミングには少し（というか色々）足りないものがあります。ここでは、その不足分を埋める個人ライブラリを紹介します。

この記事にあるコードはすべて自由にご利用くださってかまいません。ただ、不具合等があったら報告をいただけると幸いです。

なお、ほとんどが蟻本を参考にして実装されています。

優先キュー

public class PriorityQueue<T> where T : IComparable
{
    private IComparer<T> _comparer = null;
    private int _type = 0;

    private T[] _heap;
    private int _sz = 0;

    private int _count = 0;

    /// <summary>
    /// Priority Queue with custom comparer
    /// </summary>
    public PriorityQueue(IComparer<T> comparer)
    {
        _heap = new T[128];
        _comparer = comparer;
    }

    /// <summary>
    /// Priority queue
    /// </summary>
    /// <param name="type">0: asc, 1:desc</param>
    public PriorityQueue(int type = 0)
    {
        _heap = new T[128];
        _type = type;
    }

    private int Compare(T x, T y)
    {
        if (_comparer != null) return _comparer.Compare(x, y);
        return _type == 0 ? x.CompareTo(y) : y.CompareTo(x);
    }

    public void Push(T x)
    {
        _count++;
        if (_count > _heap.Length)
        {
            var newheap = new T[_heap.Length * 2];
            for (int n = 0; n < _heap.Length; n++) newheap[n] = _heap[n];
            _heap = newheap;
        }

        //node number
        var i = _sz++;

        while (i > 0)
        {
            //parent node number
            var p = (i - 1) / 2;

            if (Compare(_heap[p], x) <= 0) break;

            _heap[i] = _heap[p];
            i = p;
        }

        _heap[i] = x;
    }

    public T Pop()
    {
        _count--;

        T ret = _heap[0];
        T x = _heap[--_sz];

        int i = 0;
        while (i * 2 + 1 < _sz)
        {
            //children
            int a = i * 2 + 1;
            int b = i * 2 + 2;

            if (b < _sz && Compare(_heap[b], _heap[a]) < 0) a = b;

            if (Compare(_heap[a], x) >= 0) break;

            _heap[i] = _heap[a];
            i = a;
        }

        _heap[i] = x;

        return ret;
    }

    public int Count()
    {
        return _count;
    }

    public T Peek()
    {
        return _heap[0];
    }

    public bool Contains(T x)
    {
        for (int i = 0; i < _sz; i++) if (x.Equals(_heap[i])) return true;
        return false;
    }

    public void Clear()
    {
        while (this.Count() > 0) this.Pop();
    }

    public IEnumerator<T> GetEnumerator()
    {
        var ret = new List<T>();

        while (this.Count() > 0)
        {
            ret.Add(this.Pop());
        }

        foreach (var r in ret)
        {
            this.Push(r);
            yield return r;
        }
    }

    public T[] ToArray()
    {
        T[] array = new T[_sz];
        int i = 0;

        foreach (var r in this)
        {
            array[i++] = r;
        }

        return array;
    }
}

まずは定番の優先キュー（ヒープ）です。C#を競プロで使うときの最大の不満がこれといっても過言ではありません。コンストラクタにIComparerを渡したり、最小/最大のどちらで動かすか設定できたりします。Push()、Pop()のほかに、Peek()、Count()、Contains()、Clear()、ToArray()といった便利メソッドも足してあります。

UnionFind

public class UnionFind
{
    private class Node
    {
        public Node Parent { get; set; }
        public int Rank { get; set; }
    }

    private Dictionary<object, Node> _dict = new Dictionary<object, Node>();

    private Node Root(object data)
    {
        if (!_dict.ContainsKey(data))
        {
            var node = new Node();
            _dict.Add(data, node);
            return node;
        }
        else
        {
            var node = _dict[data];
            return Find(node);
        }
    }

    private Node Find(Node node)
    {
        if (node.Parent == null) return node;
        return node.Parent = Find(node.Parent);
    }

    public void Unite(IComparable x, IComparable y)
    {
        var xRoot = Root(x);
        var yRoot = Root(y);
        if (xRoot == yRoot) return;

        if (xRoot.Rank < yRoot.Rank)
        {
            xRoot.Parent = yRoot;
        }
        else
        {
            yRoot.Parent = xRoot;
            if (xRoot.Rank == yRoot.Rank) yRoot.Rank++;
        }
    }

    public bool IsSameGroup(IComparable x, IComparable y)
    {
        return Root(x) == Root(y);
    }
}

つぎはこれも定番のUnionFind。多少速度は犠牲にしていますが、なるべく汎用的に使えるようにIComparableなら何でも受け付けるようにしてます。Unite()のほかに、IsSameGroup()も用意してます。

比較できるタプル（ペア）

public class ComparablePair<T, U> : IComparable where T : IComparable<T>
{
    public readonly T Item1;
    public readonly U Item2;

    public int CompareTo(object obj)
    {
        ComparablePair<T, U> castedObj = (ComparablePair<T, U>)obj;
        return this.Item1.CompareTo(castedObj.Item1);
    }

    public ComparablePair(T t, U u)
    {
        Item1 = t;
        Item2 = u;
    }
}

C#のTupleは比較できないので。まあたまに便利です。

平衡二分探索木

// <summary>
// Self-Balancing Binary Search Tree
// (using Randamized BST)
// </summary>
public class SB_BinarySearchTree<T> where T : IComparable
{
    public class Node
    {
        public T Value;
        public Node LChild;
        public Node RChild;
        public int Count;     //size of the sub tree
                                //            public int Sum;       //sum of the value of the sub tree

        public Node(T v)
        {
            Value = v;
            Count = 1;
            //                Sum = v;
        }
    }

    static Random _rnd = new Random();

    public static int Count(Node t)
    {
        return t == null ? 0 : t.Count;
    }

    //public static int Sum(Node t)
    //{
    //    return t == null ? 0 : t.Sum;
    //}

    static Node Update(Node t)
    {
        t.Count = Count(t.LChild) + Count(t.RChild) + 1;
        //            t.Sum = Sum(t.LChild) + Sum(t.RChild) + t.Value;
        return t;
    }

    public static Node Merge(Node l, Node r)
    {
        if (l == null || r == null) return l == null ? r : l;

        if ((double)Count(l) / (double)(Count(l) + Count(r)) > _rnd.NextDouble())
        //            if ((double)Count(l) / (double)(Count(l) + Count(r)) > 0.5)   //debug
        {
            l.RChild = Merge(l.RChild, r);
            return Update(l);
        }
        else
        {
            r.LChild = Merge(l, r.LChild);
            return Update(r);
        }
    }

    /// <summary>
    /// split as [0, k), [k, n)
    /// </summary>
    public static Tuple<Node, Node> Split(Node t, int k)
    {
        if (t == null) return new Tuple<Node, Node>(null, null);
        if (k <= Count(t.LChild))
        {
            var s = Split(t.LChild, k);
            t.LChild = s.Item2;
            return new Tuple<Node, Node>(s.Item1, Update(t));
        }
        else
        {
            var s = Split(t.RChild, k - Count(t.LChild) - 1);
            t.RChild = s.Item1;
            return new Tuple<Node, Node>(Update(t), s.Item2);
        }
    }

    public static Node Remove(Node t, T v)
    {
        if (Find(t, v) == null) return t;
        return RemoveAt(t, LowerBound(t, v));
    }

    public static Node RemoveAt(Node t, int k)
    {
        var s = Split(t, k);
        var s2 = Split(s.Item2, 1);
        return Merge(s.Item1, s2.Item2);
    }

    public static bool Contains(Node t, T v)
    {
        return Find(t, v) != null;
    }

    public static Node Find(Node t, T v)
    {
        while (t != null)
        {
            var cmp = t.Value.CompareTo(v);
            if (cmp > 0) t = t.LChild;
            else if (cmp < 0) t = t.RChild;
            else break;
        }
        return t;
    }

    public static Node FindByIndex(Node t, int idx)
    {
        if (t == null) return null;

        var currentIdx = Count(t) - Count(t.RChild) - 1;
        while (t != null)
        {
            if (currentIdx == idx) return t;
            if (currentIdx > idx)
            {
                t = t.LChild;
                currentIdx -= (Count(t == null ? null : t.RChild) + 1);
            }
            else
            {
                t = t.RChild;
                currentIdx += (Count(t == null ? null : t.LChild) + 1);
            }
        }

        return null;
    }

    public static int UpperBound(Node t, T v)
    {
        var torg = t;
        if (t == null) return -1;

        var ret = Int32.MaxValue;
        var idx = Count(t) - Count(t.RChild) - 1;
        while (t != null)
        {
            var cmp = t.Value.CompareTo(v);

            if (cmp > 0)
            {
                ret = Math.Min(ret, idx);
                t = t.LChild;
                idx -= (Count(t == null ? null : t.RChild) + 1);
            }
            else if (cmp <= 0)
            {
                t = t.RChild;
                idx += (Count(t == null ? null : t.LChild) + 1);
            }
        }
        return ret == Int32.MaxValue ? Count(torg) : ret;
    }

    public static int LowerBound(Node t, T v)
    {
        var torg = t;
        if (t == null) return -1;

        var idx = Count(t) - Count(t.RChild) - 1;
        var ret = Int32.MaxValue;
        while (t != null)
        {
            var cmp = t.Value.CompareTo(v);
            if (cmp >= 0)
            {
                if (cmp == 0) ret = Math.Min(ret, idx);
                t = t.LChild;
                if (t == null) ret = Math.Min(ret, idx);
                idx -= t == null ? 0 : (Count(t.RChild) + 1);
            }
            else if (cmp < 0)
            {
                t = t.RChild;
                idx += (Count(t == null ? null : t.LChild) + 1);
                if (t == null) return idx;
            }
        }
        return ret == Int32.MaxValue ? Count(torg) : ret;
    }

    public static Node Insert(Node t, T v)
    {
        var ub = LowerBound(t, v);
        return InsertByIdx(t, ub, v);
    }

    static Node InsertByIdx(Node t, int k, T v)
    {
        var s = Split(t, k);
        return Merge(Merge(s.Item1, new Node(v)), s.Item2);
    }

    public static IEnumerable<T> Enumerate(Node t)
    {
        var ret = new List<T>();
        Enumerate(t, ret);
        return ret;
    }

    static void Enumerate(Node t, List<T> ret)
    {
        if (t == null) return;
        Enumerate(t.LChild, ret);
        ret.Add(t.Value);
        Enumerate(t.RChild, ret);
    }

    // debug
    public static int GetDepth(Node t)
    {
        return t == null ? 0 : Math.Max(GetDepth(t.LChild), GetDepth(t.RChild)) + 1;
    }
}

Randomized BSTを使って自動バランスするようにがんばりました。平衡二分探索木です。Insert()のほかに、Remove()、RemoveAt()、Contains()、Find()、UpperBound()、LowerBound()などがあります。
これ単体だとあんまり便利ではないかもしれませんが、次のSetとMultiSetの実装に必要です。

C言語ぽいSetとMultiSet

public class Set<T> where T : IComparable
{
    protected SB_BinarySearchTree<T>.Node _root;

    public T this[int idx] { get { return ElementAt(idx); } }

    public int Count()
    {
        return SB_BinarySearchTree<T>.Count(_root);
    }

    public virtual void Insert(T v)
    {
        if (_root == null) _root = new SB_BinarySearchTree<T>.Node(v);
        else
        {
            if (SB_BinarySearchTree<T>.Find(_root, v) != null) return;
            _root = SB_BinarySearchTree<T>.Insert(_root, v);
        }
    }

    public void Clear()
    {
        _root = null;
    }

    public void Remove(T v)
    {
        _root = SB_BinarySearchTree<T>.Remove(_root, v);
    }

    public bool Contains(T v)
    {
        return SB_BinarySearchTree<T>.Contains(_root, v);
    }

    public T ElementAt(int k)
    {
        var node = SB_BinarySearchTree<T>.FindByIndex(_root, k);
        if (node == null) throw new IndexOutOfRangeException();
        return node.Value;
    }

    public int Count(T v)
    {
        return SB_BinarySearchTree<T>.UpperBound(_root, v) - SB_BinarySearchTree<T>.LowerBound(_root, v);
    }

    public int LowerBound(T v)
    {
        return SB_BinarySearchTree<T>.LowerBound(_root, v);
    }

    public int UpperBound(T v)
    {
        return SB_BinarySearchTree<T>.UpperBound(_root, v);
    }

    public Tuple<int, int> EqualRange(T v)
    {
        if (!Contains(v)) return new Tuple<int, int>(-1, -1);
        return new Tuple<int, int>(SB_BinarySearchTree<T>.LowerBound(_root, v), SB_BinarySearchTree<T>.UpperBound(_root, v) - 1);
    }

    public List<T> ToList()
    {
        return new List<T>(SB_BinarySearchTree<T>.Enumerate(_root));
    }
}

public class MultiSet<T> : Set<T> where T : IComparable
{
    public override void Insert(T v)
    {
        if (_root == null) _root = new SB_BinarySearchTree<T>.Node(v);
        else _root = SB_BinarySearchTree<T>.Insert(_root, v);
    }
}

平衡二分探索木を使ったSetとMultiSetです。LowerBound()とUpperBound()があるのが強み（というかそのために作った）。

Deque

public class Deque<T>
{
    T[] buf;
    int offset, count, capacity;
    public int Count { get { return count; } }
    public Deque(int cap) { buf = new T[capacity = cap]; }
    public Deque() { buf = new T[capacity = 16]; }

    // for debug
    public T[] Items
    {
        get
        {
            var a = new T[count];
            for (int i = 0; i < count; i++)
            {
                a[i] = this[i];
            }
            return a;
        }
    }

    public void Init()
    {
        count = 0;
    }

    public T this[int index]
    {
        get { return buf[getIndex(index)]; }
        set { buf[getIndex(index)] = value; }
    }
    private int getIndex(int index)
    {
        if (index >= capacity)
            throw new IndexOutOfRangeException("out of range");
        var ret = index + offset;
        if (ret >= capacity)
            ret -= capacity;
        return ret;
    }
    public void PushFront(T item)
    {
        if (count == capacity) Extend();
        if (--offset < 0) offset += buf.Length;
        buf[offset] = item;
        ++count;
    }
    public T PopFront()
    {
        if (count == 0)
            throw new InvalidOperationException("collection is empty");
        --count;
        var ret = buf[offset++];
        if (offset >= capacity) offset -= capacity;
        return ret;
    }
    public void PushBack(T item)
    {
        if (count == capacity) Extend();
        var id = count++ + offset;
        if (id >= capacity) id -= capacity;
        buf[id] = item;
    }
    public T PopBack()
    {
        if (count == 0)
            throw new InvalidOperationException("collection is empty");
        return buf[getIndex(--count)];
    }
    public void Insert(int index, T item)
    {
        if (index > count) throw new IndexOutOfRangeException();
        this.PushFront(item);
        for (int i = 0; i < index; i++)
            this[i] = this[i + 1];
        this[index] = item;
    }
    public T RemoveAt(int index)
    {
        if (index < 0 || index >= count) throw new IndexOutOfRangeException();
        var ret = this[index];
        for (int i = index; i > 0; i--)
            this[i] = this[i - 1];
        this.PopFront();
        return ret;
    }
    private void Extend()
    {
        T[] newBuffer = new T[capacity << 1];
        if (offset > capacity - count)
        {
            var len = buf.Length - offset;
            Array.Copy(buf, offset, newBuffer, 0, len);
            Array.Copy(buf, 0, newBuffer, len, count - len);
        }
        else Array.Copy(buf, offset, newBuffer, 0, count);
        buf = newBuffer;
        offset = 0;
        capacity <<= 1;
    }
}

ないと稀によく困るデックです。PushFront()、PushBack()、PopFront()、PosBack()、Insert()、RemoveAt()を用意してます。

GCD、ExtGCD

public static Int64 Gcd(Int64 a, Int64 b)
{
    if (a < b)
    {
        var tmp = a;
        a = b;
        b = tmp;
    }
    if (b == 0) return a;
    var p = a > b ? a : b;
    return Gcd(b, p % b);
}

public static Int64 ExtGcd(Int64 a, Int64 b, ref Int64 x, ref Int64 y)
{
    Int64 d = a;
    if (b != 0)
    {
        d = ExtGcd(b, a % b, ref y, ref x);
        y -= (a / b) * x;
    }
    else
    {
        x = 1;
        y = 0;
    }
    return d;
}

これは定番ですね。C#ではなくとも、みんな自前ライブラリで持ってると思われます。

組み合わせ系

// m種類から重複なくn個を選ぶ組み合わせ
public static Int64 GetMcn(int m, int n)
{
    Int64 val;
    if (m < n) return 0;
    n = Math.Min(n, m - n);
    if (n == 0) val = 1;
    else val = GetMcn(m - 1, n - 1) * m / n;
    return val;
}

// m種類から重複なくn個を選んで並べる組み合わせ
public static Int64 GetMpn(int m, int n)
{
    if (n > m) return 0L;
    Int64 ret = m;
    for (int i = 0; i < n - 1; i++)
    {
        ret *= (m - i - 1);
    }
    return ret;
}

// m種類から重複を許してn個を選ぶ組み合わせ（順番は無視）
public static Int64 GetMhn(int m, int n)
{
    return GetMcn(m + n - 1, n);
}

static Int64[] fact = new Int64[500005];
static Int64[] inv = new Int64[500005];

/// <summary>
/// FOR TEST - mCn % p (p should be prime number)
/// </summary>
public static Int64 GetMcn_p_Simple(Int64 m, Int64 n, Int64 p)
{
    // m! / ( n! ( m - n )! )
    return fact[m] * inv[m - n] % p * inv[n] % p;
}

/// <summary>
///  mCn % p (p should be prime number)
///  use Lucas's theorem
///   - need pre-calculation using the mod
/// </summary>
public static Int64 GetMcn_p(Int64 m, Int64 n, Int64 p)
{
    if (!(0 <= n && n <= m)) return 0;
    Int64 ret = 1;
    for (; n > 0; m /= p, n /= p)
    {
        Int64 n0 = m % p, k0 = n % p;
        if (n0 < k0) return 0;
        ret = ret * GetMcn_p_Simple(n0, k0, p);
        ret %= p;
    }
    return ret;
}

/// <summary>
///  mCn % p (p should be prime number)
///  use Lucas's theorem (No pre-calculation needed)
/// </summary>
public static Int64 GetMcn_p_NoPrecalc(int m, int n, int p)
{
    if (p < 2) return GetMcn(m, n);

    var dm1 = m / p;
    var dm2 = m % p;
    var dn1 = n / p;
    var dn2 = n % p;

    if ((dm2 < dn2) || (dm1 < dn1)) return 0;

    return GetMcn(dm1, dn1) * GetMcn(dm2, dn2) % p;
}

public static Int64 ModInv(Int64 a, Int64 m)
{
    Int64 x = 0, y = 0;
    ExtGcd(a, m, ref x, ref y);
    if (x < 0) x += m; //modInv will never be negative
    return x;
}

public static void Precal_FactAndInv(Int64 mod)
{
    fact[0] = 1;
    inv[0] = ModInv(1, mod);

    for (Int64 i = 1; i < 500005; i++)
    {
        fact[i] = (fact[i - 1] * i) % mod;
        inv[i] = ModInv(fact[i], mod);
    }
}

組み合わせ系のライブラリ。これらも、C#でなくともみんな自前で用意してます。いくつかの関数は、Precal_FactAndInv()を呼んでから使ってください。

2018-12-21

CodeChef December Challenge 2018 参加日記

ひさびさのロングチャレンジは2完で460位/786人(Div1)。Div1は問題が難しすぎて楽しくない…。

Max and Electrical Panel

ある電子パネルは、xボルト以上の電源につなぐと壊れてしまう。1000コイン与えられるので、次の2オペレーションを使ってxを特定せよ。
・yボルトの電源につなぐ（1コイン）
・壊れたパネルを治す（cコイン）
1 <= x <= 150,000
1 <= c <= 150

二分探索をするだけだが、素直に[l,r)の中央を取っていくと、cが大きい場合に修理費が嵩みコインが足りなくなる。中央ではなく、l+(r-l)/4などの下限に近い値を使えば問題ない。
https://www.codechef.com/viewsolution/21784719

Chef and Interactive XOR

隠れた整数列[a1, a2, ... an]がある。XOR(ai, aj, ak)を何度か問い合わせることで、要素すべての値を確定させよ。ただし、各Indexに対して、3回までしか問い合わせは実行できない。
8 <= n <= 5 x 10^4

要素1からイテレートしていく。
残り要素数が4または8以上のとき、
one = a[i] ^ a[i+1] ^ a[i+2]
two = a[i+1] ^ a[i+2] ^ a[i+3]
three = a[i] ^ a[i+1] ^ a[i+2]
four = a[i] ^ a[i+2] ^ a[i+3]
を取得し、
a[i] = one ^ three ^ four
a[i+1] = one ^ two ^ three
a[i + 2] = one ^ two ^ four
a[i + 3] = two ^ three ^ four
を得ることができる。
残り要素数が5,6,7の場合も同様にパターンを見つけ出す。特に残り7の場合は手作業では難く、別にスクリプトを書いて導出した。
https://www.codechef.com/viewsolution/21865422

Directing Edges

無向グラフを、すべての頂点の入次数が偶数になるように有向グラフ化せよ。
・1 <= N(頂点数), M(辺数) <= 10^5
・グラフは連結している
・重複辺や自己ループは存在しない

まず自明なこととして、条件を満たす有向グラフを作るのは、辺が奇数のときは不可能、辺が偶数のときは必ず可能である。また、もし木であれば、葉からどんどん消していけばよいので簡単である（葉Aからその親B、Bの親からBに方向づける）。
よって、次のようにグラフを木に変換してしまえばよい。
・適当な全域木をつくる
・この木で使われなかった辺を、ダミーノード（葉）を作って繋げてしまう
（実装は省略）
言われてしまえば簡単な問題で、これが解けなかったのは悔しい。

2018-10-25

書類選考に通るレジュメの書き方（ソフトウェアエンジニア）

タイトルは誇大広告。

募集をかけるとレジュメが本当に大量に届きます。うちだとソフト屋（ぼく）が一次選考を頑張ってやっているのですが、届いたレジュメの30%が10秒、50%が30秒でゴミ箱行きです。この（ぼくの）10秒・30秒を突破する法則が出来てきたので、参考までここでシェアします。

ちなにアメリカにあるベンチャー（中小企業）のソフトウェアエンジニア職の話です。
※まともな人には自明のことばかりです

10秒のカベ

長い！
3ページ以上だと読む気が失せます。特に経験3年とかのくせズラズラ水増しするの最悪。コードもそう書くんでしょうか。

Word形式だったりする
お客さんへのレポートをWordで出すのか？という話です。PDFが無難だと思われ。

見てくれ
文字サイズやフォントの不一致、インデントのズレ、表記ゆれが多いと不安になります。コードもそう書くんでしょうか。

大事な情報がない
たまに名前のないレジュメがあるんですよ・・・。

大事な情報がない（２）
Skillの欄が空白とか。たぶん応募前に、募集要綱にあわせて埋めるつもりだったんでしょうね。

大事な情報がない（３）
メアドと電話番号を忘れずに。連絡できません。

スペルミス、文法ミスが多すぎ
あなたはコンパイルできないコードをコミットするのか。

超ミスマッチ
アドミンとかの方が、「今からコード書きたいです！」的にダメ元で応募しても無駄です。

30秒のカベ

ミスマッチ
C#er募集なのに「Pythonのスペシャリストです！C++/C#も可」みたいなやつ。じゃあPythonの会社行けよってなる。

コード書いてる雰囲気がしない
「チームをマネージしました」「仕様折衝しました」「テストしました」「ドキュメント作りました」・・・・「プログラミングしました」。最後にあるってことは、ほとんどコード書いてないね？

コード書いてるのか分からない
「何とかシステムを開発」「何とかシステムはこんなにスゴイ」「チームのコアメンバー」「チームリードがんばった」みたいな。

ぜんぶ書いちゃう
経験2年で「Python/Ruby/R/C#/Java/C/C++/Asssembler/Elixer/Lisp/JavaScript/HTML/CSS/Haskell」とか嘘松乙。気持ちは分かるが。

英語
ネイティブチェックしましょう。特に南米の方・・・！（インド英語の許容度は人によって異なる模様）

その他

致命傷じゃないけどボディーブローのように効いてきます。

いい人アピール
熱心だとか頑張り屋とかチームオリエンテッドだとか求めてないです。

ぜんぶ書いちゃう（２）
「OS:Windows2000/98/NT/95」とかノスタルジックなやつまで。

ぜんぶ書いちゃう（３）
去年までソフト屋でした。今はA社でセールスマンしてます！

ぜんぶ書いちゃう（４）
大学時代にバスケやっててセンターだったとか・・・。

LinkedInとの不整合
レジュメだと「Software Engineer」なのにLinkedInだと「Powertrain Technician」みたいな。

住んでるところ
居住地はあったほうが無難。外国ならなおさら（面接時の旅費とか、ビザとかあるしね）。

レターサイズじゃない
アメリカの企業に提出するなら、サイズはA4でなくレターにしましょう。プリントできなくてイラっとします。

個人ページへのリンク
学生時代に作ったような写真だけの一枚ページとか、無いほうがマシ。クリックしてがっかりしちゃう。

人事が一次チェックするような会社だと、また話が違うのかもしれませんが。

2018-06-12

Codechef June Challenge 2018 参加日記

155位/438人(Div1)だった。もう1問くらい解けそうだったが、期間中にゲームを買ってしまったのが原因でフェードアウト敗退した。

Vision

三次元の座標上に、２つの点PとQ、および球が与えられる。Pは動かないが、Qは一定の速度で動いてゆく。時間tの点Qの位置は次の式で表される(dはベクトル、Q(0)はQの初期位置)。
Q(t) = Q(0) + d*t
はじめ、点QはPから見えないことが保証されている。このとき、点QからPが見えるようになる最小の時間を求めよ。なお、PやQが球に重なることはない。

初期状態は点Qが見えなくて、ある時間tから点Pが見えるようになるのだから、二分探索を使えば求められる。「点Qから点Pが見えるかどうか」は、Q->Pベクトルが球に交差する、と言い換えればよい。あとは初等幾何の問題。
https://www.codechef.com/viewsolution/18726175

Two Flowers

n行m列のグリッドが与えれ、各セルにはタイプa[i,j]の花が咲いている。最大2種類の花を選び、その花のみ咲いている連続するセルを選択するとき、その最大面積を求めよ。上下左右のいずれかでセルが接するとき、その2セルは連続しているとする。
1 <= n, m <= 2000
1 <= a[i, j] <= 4x10^6

本番はむりやり通したが嘘解法。Editorialの貪欲解は、
１）あるセルと、そのセルの右または下のセルを選ぶ
２）その2つのセルにある色のみを選んでBFSしていく
を、すべてのセルに対して行っている。ただし、同じ集合が重複しないように、「現在のセルからある方向に遷移したことがあるか」をもって、もしあるならば無視するようにしている。これは自分の解とほぼ同じなのだが、重複を無視する部分が位置+色組み合わせでHashSetに入れて判断していたため、TLEになってしまっていた。方向だけなら配列で持てるので間に合う。
https://s3.amazonaws.com/codechef_shared/download/Solutions/JUNE18/editorialist/TWOFL.cpp
(Editorial解)

2018-05-23

Codechef May Challenge 2018 参加日記

久しぶりのプロコンは今回からDiv1/2に分かれたCodechef。Div1で344位/633人の結果だった。ていうかDiv2でいいのに・・・。

Dibs on Fibs

サイズMの配列A、Bと整数Nが与えられる。次の最終resultを、10^9+7でModして答えよ。
result := 0
for i := 1 to M
for j := 1 to M
array fib[1..max(2, N)]
fib[1] := A[i]
fib[2] := B[j]
for k := 3 to N
fib[k] := fib[k-1] + fib[k-2]
result := result + fib[N]
1 <= M <= 10^5
1 <= N <= 10^5

いくつか列挙するとパターンが見える。たとえば
A = [ a, b, c ]
B = [ d, e, f ]
だとすると、iが1のときは
a, d, (a+d), (a+2d), (2a+3d), (3a+5d), (5a+8d), ...
a, e, (a+e), (a+2e), (2a+3e), (3a+5e), (5a+ 8e), ...
a, f, (a+e), (a+2e), (2a+3e), (3a+5e), (5a+ 8e), ...
のようになる。つまりAの各要素xについて
x * fib(n-3) * m
が最終回答になり、同様にBの各要素yについては
y * fib(n-2) * m
が回答になる。これを足し合わせればよい。（N<=2のときは別途計算）
https://www.codechef.com/viewsolution/18432901

Fake Binary Search

要素がDistinctな整数列Aが与えられる。Aの要素Xがについて、次のサーチアルゴリズムで正しいXの位置が求められるようにするためには、最小で何回、要素を交換することが必要か。なお数列Aは１つのみだが、クエリはQ回問われる。
integer binary_search(array a, integer n, integer x):
integer low, high, mid
low := 1
high := n
while low ≤ high:
mid := (low + high) / 2
if a[mid] == x:
break
else if a[mid] is less than x:
low := mid+1
else:
high := mid-1
return mid

正しい二分探索経路上で、Xの左と右それぞれについて、
左：Xより大きいもの
右：Xより小さいもの
が交換しなけらばならない要素とわかる。まずこの左右から交換するべきなので、最終回答に左と右の差を加える。
その次に余ったもの（左もしくは右にあるもの）を、有効な要素と交換していけばよい。
有効な候補の有無は、あらかじめAをソートしておけばLowerBound/UpperBoundで効率よく探すことができる。
https://www.codechef.com/viewsolution/18435496

Change the Signs

整数列Aの任意の要素に-1を掛けることができるとき、連続する長さ2以上の部分列が、必ず合計1以上になるようにしたい。最終的な数列の要素の合計を最小化せよ。

本番ではDFS+枝刈りで部分点だった。
よく考えると、ある要素iに注目しているとき、条件が成立するのは
・i-2が正、i-1が正
・i-2が負、i-1が正
・i-2が正、i-1が負
のパターンしかない。上からそれぞれdp_a, dp_b, dp_cとすると
dp_a[i] = min (dp_a[i-1], dp_b[i-1]) + A[i]
dp_b[i] = dp_c[i - 1] + A[i] (A[i] > A[i-1]のとき)
dp_c[i] = min (dp_a[i-1], dp_b[i-1]) - A[i] (A[i-1] > A[i] + A[i-2]のとき）
dp_c[i] = dp_a[i-1] - A[i] (a[i] + a[i-2] >= A[i-1] > A[i] のとき)
と式を立てることができる。
※参考実装
https://www.codechef.com/viewsolution/18500660

2018-04-22

2018年の抱負（改２）

3月に妻が急病になり、ER搬送からの一週間入院という出来事があった（現在はもう問題なし）。それがきっかけで、自身の健康・キャリアついて色々考え直したので、今年の抱負も合わせて更新しておく。

2018年の抱負

一日7時間睡眠
必須科目。どんなに忙しくても6.5時間は寝る。健康は本当に大事

年収~~+15%~~ → +10%
無理しない額に下方修正。睡眠を削ってまで達成しようとしないこと。
糸井重里さんの『ちゃんとメシ食って、風呂入って、寝てる人にはかなわない』を座右の銘とする。
dot.asahi.com

プロコン再開
もともと今年は控えるつもりだったが、熟考の末、日常的な趣味に戻すことにした。理由は
・プロコンをしないと、仕事のプログラミングを家でやってしまうことがわかった。。。
・アルゴリズムが自分の強みらしいとわかった。自分程度でも田舎の普通のプログラマの中だと突出する
・プロコンがないと、トップレベルのコーダーと絡む機会がゼロになることに気づいた
・ABC/ARCへの定期参加にメドがついた
などなど。