A - たこ焼き買えるかな?

愚直にloopを回した。7つ以上なら10個まとめて買う。

あの親切なサンプルがなかったら油断して勢いで書いて提出してWA生やしてたかもしれない。

>,>,[>+>+<<-]>>[<<+>>-]<>++++++++++[<->-]<>-<[>+<[-]]>[<->+]<>+<[[-]>-<<[-]<>+++
+++++++++++++++++++++++++++++++++++++++++++++[<->-]<>]>[-<<[>+<-]<[>+<-]>>[<<+>>
-]<>++++++++++++++++++++++++++++++++++++++++++++++++[<->-]<>++++++++++<[>[>+>+<<
-]>>[<<+>>-]<<<-]>[-]>[<<+>>-]<<>+++++++++++++++++++++++++++++++++++++++++++++++
+[<->-]<[<+>-]<>>]<<>[>+<-]<[>+<-]>>[<<+>>-]<[>+>+<<-]>>[<<+>>-]<>+++++++[>+<-]<
[>+<-]>>[<<+>>-]<[<[>>+>+<<<-]>>>[<<<+>>>-]<>+<[[-]>-<<[>+<-]<[>+<-]>>[<<+>>-]<-
[>+<-]<[>+<-]>>[<<+>>-]<>]>[-<<>>]<<-][-]<[>-<[-]]>[<->+]<>-<[>+<[-]]>[<->+]<[[-
]<[>+>+<<-]>>[<<+>>-]<>++++++++++[>+<-]<[>+<-]>>[<<+>>-]<[<[>>+>+<<<-]>>>[<<<+>>
>-]<>+<[[-]>-<<[>+<-]<[>+<-]>>[<<+>>-]<-[>+<-]<[>+<-]>>[<<+>>-]<>]>[-<<>>]<<-][-
]<[>-<[-]]>[<->+]<>-<[>+<[-]]>[<->+]<>+<[[-]>-<<>++++++++++[<->-]<>]>[-<<[-]<>>>
]<<[>+<-]<[>+<-]>>[<<+>>-]<>+[<+>-]<[>+<-]<[>+<-]>>[<<+>>-]<[>+>+<<-]>>[<<+>>-]<
>+++++++[>+<-]<[>+<-]>>[<<+>>-]<[<[>>+>+<<<-]>>>[<<<+>>>-]<>+<[[-]>-<<[>+<-]<[>+
<-]>>[<<+>>-]<-[>+<-]<[>+<-]>>[<<+>>-]<>]>[-<<>>]<<-][-]<[>-<[-]]>[<->+]<>-<[>+<
[-]]>[<->+]<][-]<>+++++++++++++++<[>[>+>+<<-]>>[<<+>>-]<<<-]>[-]>[<<+>>-]<<[>+<-
]<[>+<-]>>[<<+>>-]<[>+>+<<-]>>[<<+>>-]<>+<[[-]>-<<>+++++++++++++++++++++++++++++
+++++++++++++++++++[<+>-]<.[-]<[>+>+<<-]>>[<<+>>-]<>+++++++++[<[>>+>+<<<-]>>>[<<
<+>>>-]<>+<[[-]>-<<[>+<-]<[>+<-]>>[<<+>>-]<-[>+<-]<[>+<-]>>[<<+>>-]<>]>[-<<>>]<<
-][-]<[>-<[-]]>[<->+]<>-<[>+<[-]]>[<->+]<>+<[[-]>-<<>+++++++++++++++++++++++++++
+++++++++++++++++++++.[-]<>]>[-<<>>]<<>]>[-<<[-]<>>]<<>++++++++++<[>>+>+<<<-]>>>
[<<<+>>>-]<>+<[[-]>-<<[>>+<<-]>+>>>>>+[<<<<[->+>+<<]>[-<+>]>[-<<<<<-[>]>>>>>>>-<
<<<<<[<]>>>>]>+>]<<<<<<<[>]>[>[-<<<+>>>]>>>-<<<<<]>->[-]>>>>>[-]<<[<<<<<+>>>>>-]
<<<<<>]>[-<<[-]>>]<<[>+>+<<-]>>[<<+>>-]<>+<[[-]>-<<>++++++++++++++++++++++++++++
++++++++++++++++++++[<+>-]<.[-]<>]>[-<<[-]<>>]<<>+++++++++++++++++++++++++++++++
+++++++++++++++++[<+>-]<.[-]<>++++++++++.[-]<

別のサイトの問題のためにbrainfuck書いたら、鯖側の処理系で動かなくて自前の処理系に包んで提出する羽目になりました。brainfuck対応してるの見つけて手書きで頑張ったのに悲しかかったです。その勢いでこっちでもやりました。手書きは疲れたので自前の変換器で生成しました。人の手のぬくもりのないコードですが許してほしい。

B - 謎のたこ焼きおじさん

各文字種ごとに考えればよい。

NR == 2 {
    split($0, s, "")
    for (i in s) a[s[i]] += 1
}
NR == 3 {
    split($0, s, "")
    for (i in s) b[s[i]] += 1
}
END {
    result = 0
    split("ABCDEFGHIJKLMNOPQRSTUVWXYZ", alpha, "")
    for (i in alpha) {
        c = alpha[i]
        # print c, a[c], b[c]
        if (a[c] > 0 && b[c] == 0) {
            result = 1000000006
        } else if (b[c] > 0) {
            t = int((a[c] + b[c] - 1) / b[c])
            if (result < t) result = t
        }
    }
    if (result == 1000000006) result = -1
    print result
}

brainfuckでも書ける問題だと思ったけど、私の変換器だと力不足なので手書きが必要で、疲れるので逃げました。

今日のawk:

  • for (i in ary) { ... } 文がある。javascriptと同じ(propertyを捜査してるという点まで含めて)
  • 文字はない。for (char c = 'a'; c <= 'z'; ++ c) { ... }みたいな操作はできない
  • min,maxはない

C - THE☆たこ焼き祭り2012

まず、1秒に1つしかたこ焼きを投げられない、という制約に関して考える。 これは最初にたこ焼きを投げる人(あなた)に以外の参加者に関して無視できる。 理由としては、あなたに関しても適用されることと、最適な順序でたこ焼きの分配が行われる場合、同じ人へは同じ道を通って渡されるため、たこ焼きが衝突することはないこと。 よって、各人に対してその人にたこ焼きを渡すのに必要な最短の時間をdijkstra法で求め、伝達に時間を要する人から順に配っていけばよい。

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
template <class T>
using reversed_priority_queue = std::priority_queue<T, std::vector<T>, std::greater<T> >;
#define repeat_from(i,m,n) for (int i = (m); (i) < (n); ++(i))
#define repeat(i,n) repeat_from(i,0,n)
using namespace std;
template <typename T> T sq(T x) { return x * x; }
int main() {
    int n; cin >> n;
    vector<int> x(n), y(n), t(n), r(n);
    repeat (i,n) cin >> x[i] >> y[i] >> t[i] >> r[i];
    vector<double> z(n, -1);
    reversed_priority_queue<pair<double,int> > q;
    q.emplace(0, 0);
    while (not q.empty()) {
        auto p = q.top(); q.pop();
        int i = p.second;
        if (z[i] != -1) continue;
        z[i] = p.first;
        repeat (j,n) if (z[j] == -1) {
            q.emplace(z[i] + sqrt(sq(x[j] - x[i]) + sq(y[j] - y[i])) /(double) min(t[i], r[j]), j);
        }
    }
    sort(z.rbegin(), z.rend());
    double result = 0;
    repeat (i,n-1) {
        result = max(result, z[i] + i);
    }
    printf("%.9f\n", result);
    return 0;
}

しかし2012って3年前なのかあ