New Year Contest 2020 の write-up

あけましておめでとうございます。1 月 2 日から 1 月 3 日にかけて開催された New Year Contest 2020 に参加しました。最終的に 1509.34 点を獲得し、9 位でした。

A: 2020

1989 <= Y <= 2021 で 1 <= M <= 12 とのことで昭和と平成も含まれそうですが、無視して常に令和と答えれば OK でした。

B: すぬけ探し

スプレッドシートのスクリーンショットが与えられ、ほとんどのセルが「すめけ」となっている中「すぬけ」のセルを見つけて座標を答えればよいようです。

JPEG ではなく PNG が与えられていることに優しさを感じます。まず「すぬけ」になっているセルをひとつ見つけて切り出し、これとマッチしているセルを探せば OK でした。

import string
from PIL import Image

table = list(string.ascii_uppercase) + ['A' + c for c in string.ascii_uppercase]

im = Image.open('chall.png').convert('RGB')
snuke = tuple(Image.open('snuke.png').getdata())

cw, ch = 38, 17
w, h = im.size

for y in range(h // ch):
  for x in range(w // cw):
    c = im.crop((x * cw, y * ch, (x + 1) * cw, (y + 1) * ch))
    if tuple(c.getdata()) == snuke:
      print('{}{}'.format(table[x], y + 1))

$ python3 solve.py
11
A1
AC2
O13
J14
AA19
B20
AG24
AB26
Y34
G41
AD44

F: AtCoDeerくんとお正月

月と日が与えられるので、お正月まであと何日かを答えればよいようです。

まず以下のような 1 月 1 日だけを「お正月」とするものを提出しましたが通りませんでした。

from datetime import datetime
t = int(input())
for _ in range(t):
    m, d = map(int, input().split(' '))
    if m == 1 and d == 1:
        print('0')
    else:
        delta = datetime(2021, 1, 1) - datetime(2020, m, d)
        print(delta.days)

続いて三が日、1 月 15 日までと試しましたが通らず。ここで諦めました。

I: Orst Aannoozz Aesy

問題文が 1 行ごとにソートされてしまっているようです。適当なオンラインジャッジの問題文を参考に組み立て直すと、以下のようになりました。

# Sort Nazonazo Easy
N要素からなる整数列と、整数Kが与えられる。

整数列からK番目(0-indexed)の要素を取り除き、残ったものの平均値を計算する。

この操作をK番目の要素が存在する間繰り返したとき、平均値の最大は何かしてとのも現れる。

ただし、空の列の平均値は便宜上0とする。

## Input Format
複数ケースが与えられる。1行目にテストケース数Tが書かれている。

各テストケースは形式で以下の通り。その各テストケースの入力が後に続くある。

1行目にNとKが空白区切りで与えられる。

2行目にはN要素の整数列が空白区切りで与えられる。

## Constraints
- 0 <= T <= 31
- 0 <= K <= N <= 2020

## Output Format
答えを1行で出力せよ。ジャッジの解と絶対誤差または相対誤差が1e-6以内であれば正解とする。

t = int(input())
for _ in range(t):
    n, k = map(int, input().split(' '))
    xs = list(map(int, input().split(' ')))
    avgs = []

    while k < len(xs):
        xs = xs[:k] + xs[k+1:]
        if len(xs) == 0:
            avgs.append(0)
            break
        avgs.append(sum(xs) / len(xs))

    print(max(avgs))

K: EvimAngya

35.7100627 139.8107004

34.66549051626846 133.9191406321396

写真に写っている「0番線羽越本線」という文字列をそのままググると出てきました。酒田駅のようです。

38.9222309 139.8458948

Bing で少しトリミングして画像検索すると和歌山城と教えてくれました。

「和柄イルミネーション」でググるとアミュプラザ鹿児島とわかりました。

35.5396292,134.2383599

Bing で画像検索するとほとんど同じ構図で撮影された写真が出てきます。高松シンボルタワーのようでした。

34.3525108,134.0465112

「モノレールアーチ状」でググると、与えられた写真と似たような景色の画像とともにゆいレール浦添延長開業うんぬんの記事が出てきました。ゆいレールの駅を片っ端から調べていくとてだこ浦西駅とわかりました。

Google で画像検索するとアミューズメントパークウェアハウス川崎店とわかりました。

L: Last Striker

コンテスト終了 2 時間の時点で最後から 6 ~ 14 番目に提出すると点数がもらえるようです。私は開始早々提出してしまい 1 点しかもらえませんでした。

M: Mannaka

各プレイヤーは 0 以上 2147483648 以下の整数を提出し、全員の提出した整数の中央値を提出した人に点数がもらえるようです。私は外しました。

O: TozAngya

K: EvimAngya と同様に写真から撮影地の経度と緯度を答える問題でした。

看板に座標や地名が書かれていますが、鵜呑みにしてはいけません。後ろの建物に書かれている「Tundra Grill」でググると出てきました。

Bing で画像検索すると銀座三越前ライオン像がまず出てきますが、騙されてはいけません。よく見ると後ろに写っている壁が違います。「三越ライオン像」でググると札幌三越とわかりました。

この犬はどう見ても秋田犬です。作問者の方の Twitter アカウントで「秋田」を含むツイートを検索すると、それっぽいツイートがヒットします。これを手がかりに大館市の (たぶん) 秋田犬の里とわかりました。

「”stop sign” “wa’la”」でググるとそれっぽいツイートがヒットしアラートベイとわかりました。

「タワーマンションスケート」でググると沼影公園アイススケート場とわかりました。

後ろに写っている看板からこの駅はおそらく 4 文字であること、ラインカラーが黄色っぽい路線であるとわかります。それっぽい駅が出ることを期待して「無人駅赤い瓦」でググると因美線や津山線といった中国地方の路線にあるよく似た駅がヒットしました。これらの路線を管轄する JR 西日本で黄色っぽいラインカラーの路線を探すと、これらの他にも木次線があることがわかります。木次線の駅のうち 4 文字のものを片っ端から調べていくと出雲八代駅とわかりました。

後ろに写っている「KANTO KANKO」と書かれているバスから関東周辺で撮影されたものと推測しましたが、特定できませんでした。

S: A + B Problem 2020

プログラムに与えられる整数の総和を出力すればよいようですが、どうやら標準入力から与えられるわけではないようです。

雑に 10 を常に出力するものを提出するとテストケース 19, 28, 37, 46, 55, 64, 73, 82, 91 だけが正しいと判定され、15 の場合にはテストケース 69, 78, 87, 96 だけが正しいと判定されました。どうやら各桁の数字を足せばよいようですが、どうやって今何番目のテストケースであるか特定すればよいのでしょうか。私は諦めました。

T: TOLO7

V: Pointer, Pointer, Pointer

与えられる文字列について、C99 に準拠した宣言であるかどうか判定すればよいようです。パースは GCC に任せる形で以下のようなコードを提出しましたが、ダメでした。

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

int main() {
    int i, n;
    char s[65536], t[65536], ok[65536] = "";
    FILE *fp;
    
    scanf("%d\n", &n);
    for (i = 0; i < n; i++) {
        fgets(s, 65536, stdin);
        sprintf(t, "main() { %s %s }", ok, s);
        
        fp = fopen("aaaaa.c", "w");
        fputs(t, fp);
        fclose(fp);
        
        if (system("gcc -std=c99 -fsyntax-only aaaaa.c 2>/dev/null")) {
            puts("INVALID");
        } else {
            strcat(ok, s);
            puts("VALID");
        }
    }
    
    return 0;
}

W: Guess the Language

ある言語で書かれた Wikipedia のある記事の一部をソートしたものが与えられるので、何語か特定するという問題でした。この問題を解くにあたって、キリル文字圏の言語を特定する - 話は尽きないという記事を参考にしました。

常に tg を出力するプログラムを提出したところ 3 番目のテストケースで正しいと判定され、これがタジク語であるとわかりました。

ә һ ө җ ү という特徴的な文字からカルムイク語とわかります。

Һ ү という特徴的な文字からブリャート語とわかります。

常に bg を出力するプログラムを提出したところ 10 番目のテストケースで正しいと判定され、これがブルガリア語であるとわかりました。

Xmas: Signboard 1 RETURNS

36 枚の画像が与えられるので、これをいい感じに配置するという問題でした。

よく見ると各画像に EXIF がついており、配置すべき緯度と経度が与えられていることがわかります。以下のスクリプトを実行するといい感じに配置することができました。

from PIL import Image
from PIL.ExifTags import TAGS, GPSTAGS
from neko import get_exif_data, get_lat_lon # https://gist.github.com/valgur/2fbed04680864fab1bfc

layout = [[None for _ in range(6)] for _ in range(6)]

for i in range(1, 37):
  piece = Image.open('logo_data/{}.jpg'.format(i))
  exif = get_exif_data(piece)
  lat, lon = map(int, get_lat_lon(exif))
  lat, lon = lat - 34, lon - 135 # y, x
  layout[lat][lon] = i

layout = layout[::-1]

im = Image.new('RGB', (1000, 1000))
for y in range(6):
  for x in range(6):
    im.paste(Image.open('logo_data/{}.jpg'.format(layout[y][x])), (85 * x, 85 * y))
im.save('result.png')

print('\n'.join(' '.join(str(x) for x in a) for a in layout))

$ python3 solve.py
13 20 16 4 5 6
26 10 32 3 11 12
34 14 2 22 17 18
1 25 21 19 23 24
28 8 9 31 29 30
27 15 33 7 35 36

Z: Shiritori 2020

絵しりとりの様子が与えられるので、それぞれ何を意味しているか答えればよいようです。ところどころ噛み合っていませんが、回答者が何と勘違いしていたかを当てることができればボーナスポイントがもらえました。

ねずみ
ミーアキャット
栗
リチウムイオン電池
調号 (誤り: フラット)
トルネード
鈍角 (誤り: 度)
? (誤り: ハミルトン閉路)
陸 (誤り: 陸地)
着陸
クラッカー
金

st98 の日記帳

2020-01-03[gtf] New Year Contest 2020 の write-up