ICPC 国内予選 参加記

ICPC の国内予選に参加しました.

チーム名は Nara Institute of BBQ,メンバーは Python をプライマリ言語としている私と @giraffe0890@UZI7215 でした.

実力的に 4 完以上は厳しそうなので,我々のチームは深層学習で AC するコードを生成することに…….

という冗談はさておき,3 完を確実にするために,作戦は,

  1. @y_sira が A を早解き,その間に @giraffe0890@UZI7215 が B,C の解法を考える
  2. @y_sira が A を解き終えたら,B,C のフォローに入って 3 完させる
  3. D 以降を 3 人で一緒に考える

こんな感じで立てていました.

本番

本番直前にプリンタにトラブルがあり,テンパる.

とりあえず,私が A を AC .

#   _______________    __  ___   ____  ____  ____
#  /_  __/ ____/   |  /  |/  /  / __ )/ __ )/ __ \
#   / / / __/ / /| | / /|_/ /  / __  / __  / / / /
#  / / / /___/ ___ |/ /  / /  / /_/ / /_/ / /_/ /
# /_/ /_____/_/  |_/_/  /_/  /_____/_____/\___\_\
#
import itertools

while True:
    n, m = map(int, input().split())

    if n == m == 0:
        break

    a = list(map(int, input().split()))

    s = []
    for pair in itertools.combinations(a, 2):
        if sum(pair) <= m:
            s.append(sum(pair))

    if len(s) == 0:
        print('NONE')
    else:
        print(max(s))

他のメンバーの様子を見に行く. @giraffe0890 が「B 解けそう」と言っていたのでおまかせすることに. @UZI7215 は「C 無理そう」とのことだったので,私が C の考察をしてみることに. @UZI7215 には D の考察をお願いした.

C は画像処理みたいに微分を使ってエッジ検出するのかなぁと考察するも,実装まで届かず. この時点で開始から 1 時間半程度経過していたと思う.

@giraffe0890 が B に手こずっていたので,問題文を解説してもらって,「これは構文解析で実装できそう」と思ったので私が実装することに.

ちなみに @giraffe0890 のコードは以下.

#   _______________    __  ___   ____  ____  ____
#  /_  __/ ____/   |  /  |/  /  / __ )/ __ )/ __ \
#   / / / __/ / /| | / /|_/ /  / __  / __  / / / /
#  / / / /___/ ___ |/ /  / /  / /_/ / /_/ / /_/ /
# /_/ /_____/_/  |_/_/  /_/  /_____/_____/\___\_\
#
while True:
    s1 = str(input())
    if s1 == ".":
        quit()
    s2 = str(input())
    if s1 == s2:
        print('IDENTICAL')
        break
    if s1[0] == s2[0] == '"':
        a = 0
    else:
        a = 1
    t1 = s1.split('"')
    t2 = s2.split('"')
    if len(t1) != len(t2):
        print('DIFFERENT')
        break
    count = 0
    for i in range(len(t1)):
        if t1[i] != t2[i]:
            if i % 2 == a:
                count += 1
            else:
                print('DIFFERENT')
                break
    if count == 1:
        print('CLOSE')
        break
    elif count > 1:
        print('DIFFERENT')
        break
    print(t1)
    print(t2)
    print(count)

構文解析を実装し終わるが,バグに悩まされること小一時間. なんとかバグを直して B を AC.

#   _______________    __  ___   ____  ____  ____
#  /_  __/ ____/   |  /  |/  /  / __ )/ __ )/ __ \
#   / / / __/ / /| | / /|_/ /  / __  / __  / / / /
#  / / / /___/ ___ |/ /  / /  / /_/ / /_/ / /_/ /
# /_/ /_____/_/  |_/_/  /_/  /_____/_____/\___\_\
#
import sys


def parse(s):
    p = []
    i = 0
    while True:
        if i >= len(s):
            break

        if s[i] == '"':
            lt = '"'
            j = 0
            while True:
                if s[i + j + 1] == '"':
                    i = i + j + 1
                    lt += '"'
                    break
                lt += s[i + j + 1]
                j += 1
            p.append(lt)
        else:
            lt = ''
            j = 0
            while True:
                if i + j >= len(s):
                    i = i + j - 1
                    break
                if s[i + j] == '"':
                    i = i + j - 1
                    break
                lt += s[i + j]
                j += 1
            p.append(lt)

        i += 1

    return p

def main():
    while True:
        s1 = input()

        if s1 == '.':
            break

        s2 = input()

        p1 = parse(s1)
        p2 = parse(s2)

        if len(p1) == len(p2):
            miss = 0
            critical = False
            for term1, term2 in zip(p1, p2):
                if term1[0] == '"' and term2[0] == '"':
                    if term1[1: -1] != term2[1:-1]:
                        miss += 1
                        if miss >= 2:
                            break
                elif term1[0] == '"' and term2[0] != '"':
                    critical = True
                    break
                elif term1[0] != '"' and term2[0] == '"':
                    critical = True
                    break
                elif term1[0] != '"' and term2[0] != '"':
                    if term1 != term2:
                        critical = True
                        break

            if critical:
                print('DIFFERENT')
            else:
                if miss == 0:
                    print('IDENTICAL')
                elif miss == 1:
                    print('CLOSE')
                else:
                    print('DIFFERENT')
        else:
            print('DIFFERENT')

    return 0

if __name__ == '__main__':
    sys.exit(main())

この時点で残り 30 分.

@giraffe0890@UZI7215 が G を考えてくれていて,@giraffe0890 が「G の机上コーディング出来た」とのことだったので,おまかせ. @UZI7215 は D で苦戦していた. 残り 10 分程度のところで写経を終え,テストケースを流してみるものの,配列の範囲外アクセスで exception を吐く. 壁の方向へ移動してしまっていたようだ.

#   _______________    __  ___   ____  ____  ____
#  /_  __/ ____/   |  /  |/  /  / __ )/ __ )/ __ \
#   / / / __/ / /| | / /|_/ /  / __  / __  / / / /
#  / / / /___/ ___ |/ /  / /  / /_/ / /_/ / /_/ /
# /_/ /_____/_/  |_/_/  /_/  /_____/_____/\___\_\
#
while True:
    n, m = map(int, input().split())
    if n == m == 0:
        break
    p = []
    flag = 0
    for i in range(n):
        p.append(list(map(str, input().split())))



    def flag_check(x, y, flag):
        if x == (1-1) and y == (n-1):
            flag += 1
        elif x == (m-1) and y == (n-1):
            flag += 1
        elif x == (m-1) and y == (1-1):
            flag += 1

    def go (x, y, flag):
        if flag == 3 and x == (1-1) and y == (1-1):
            return 'YES'
        flag_check(x, y, flag)
        if flag == 0:
            if p[x-1][y] == '.':
                p[x-1][y] = '#'
                go(x-1, y, flag)
            elif p[x][y-1] == '.':
                p[x][y-1] = '#'
                go(x, y-1, flag)
            elif p[x+1][y] == '.':
                p[x+1][y] = '#'
                go(x+1, y, flag)
            elif p[x][y+1] == '.':
                p[x][y+1] = '#'
                go(x, y+1, flag)
        elif flag == 1:
            if p[x][y-1] == '.':
                p[x][y-1] = '#'
                go(x, y-1, flag)
            elif p[x+1][y] == '.':
                p[x+1][y] = '#'
                go(x+1, y, flag)
            elif p[x][y+1] == '.':
                p[x][y+1] = '#'
                go(x, y+1, flag)
            elif p[x-1][y] == '.':
                p[x-1][y] = '#'
                go(x-1, y, flag)
        elif flag == 2:
            if p[x+1][y] == '.':
                p[x+1][y] = '#'
                go(x+1, y, flag)
            elif p[x][y+1] == '.':
                p[x][y+1] = '#'
                go(x, y+1, flag)
            elif p[x-1][y] == '.':
                p[x-1][y] = '#'
                go(x-1, y, flag)
            elif p[x][y-1] == '.':
                p[x][y-1] = '#'
                go(x, y-1, flag)
        elif flag == 3:
            if p[x][y+1] == '.':
                p[x][y+1] = '#'
                go(x, y+1, flag)
            elif p[x-1][y] == '.':
                p[x-1][y] = '#'
                go(x-1, y, flag)
            elif p[x][y-1] == '.':
                p[x][y-1] = '#'
                go(x, y-1, flag)
            elif p[x+1][y] == '.':
                p[x+1][y] = '#'
                go(x+1, y, flag)
        else:
            return 'NO'

    go(0, 0, flag)

ここでコンテスト終了.

反省

  • チームメンバーを有効に活用できず,時間の無駄が多かった
  • 机上コーディングの詰めが甘いメンバーが多かった
  • チームメンバーの考察をもっとじっくり聞けばよかった

あとから他のチームに聞いたことだが,B は構文解析なんて書かずとも,split('"') でうまいこと実装できるらしい. 確かに.

C は微分せずとも,制約が緩いので,全探索で解けるらしい.

ちゃんちゃん.

表で太い罫線を引く

論文でよく見かける,横に太い罫線が引かれた表.

\Hline などの独自コマンドを定義して実現する方法もありますが,パッケージ booktabs を読み込むことで太い罫線を引くコマンドを追加できます.

プリアンブルで \usepackage{booktabs} とし,例えば本文で以下のような表を作成します.

\begin{tabular}{lrr} \toprule[4pt]
  品名   & 単価 (円) & 個数   \\ \midrule
  りんご & 100       & 5     \\
  みかん & 50        & 10    \\ \bottomrule[4pt]
\end{tabular}

よく見かけるスタイルの表ができました.めでたしてめでたし.

ちなみに,\Hline を独自に定義する方法は次の記事が参考になる.

LaTeXの表に,太い横線 \Hline を追加 - shingoushori's dialy

引用すると,プリアンブルに

\makeatletter
\def\Hline{
  \noalign{\ifnum0=`}\fi\hrule \@height 4.\arrayrulewidth \futurelet
  \reserved@a\@xhline}
\makeatother

と記述することで \Hline が定義できるようだ.

AOJ0024

Physical Experiments | Aizu Online Judge

 v = 9.8t,  y = 4.9t^2 より, \displaystyle y = \frac{v^2}{19.6} N 階での高さは  y = 5N - 5 だから, \displaystyle 5N - 5 = \frac{v^2}{19.6}. これを解いて, \displaystyle N = \frac{v^2}{98} + 1

ガラス球が割れるような速度  v_b に達するためには, \displaystyle N = \left\lceil \frac{v_b^2}{98} \right\rceil + 1 階から落下させればよい.

from math import ceil

while True:
    try:
        print(ceil(float(input()) ** 2 / 98) + 1)
    except EOFError:
        break

AOJ0023

Circles Intersection | Aizu Online Judge

from math import hypot

n = int(input())
for i in range(n):
    x1, y1, r1, x2, y2, r2 = map(float, input().split())
    d = hypot(x1 - x2, y1 - y2)
    if d > r1 + r2:
        print(0)
    elif abs(r1 - r2) <= d:
        print(1)
    else:
        if r1 > r2:
            print(2)
        else:
            print(-2)

AOJ0022

Maximum Sum Sequence | Aizu Online Judge

while True:
    n = int(input())
    if n == 0:
        break
    s = [int(input())]
    for i in range(1, n):
        a = int(input())
        s.append(max(a, a + s[i - 1]))
    print(max(s))

AOJ0021

Parallelism | Aizu Online Judge

n = int(input())
for i in range(n):
    x1, y1, x2, y2, x3, y3, x4, y4 = map(float, input().split())
    c1 = (y1 - y2) * (x3 - x4)
    c2 = (y3 - y4) * (x1 - x2)
    if abs(c1 - c2) < 1e-10:
        print('YES')
    else:
        print('NO')