Mujin Programming Challenge 2017

MUJIN Programming Contest Atcoder

参加しました、Bの完全点のみでした
見学権が手に入る200位以内を目標にしていましたが、それは惜しくも届かずでした

Mujin Programming Challenge 2017 - Mujin Programming Challenge 2017 | AtCoder

B - Row to Column

B: Row to Column - Mujin Programming Challenge 2017 | AtCoder

まずBは300点の部分点があるのでこっちから取り掛かることにしました。
部分点はN <= 3だったので、ひたすら列挙して解を求めてやろうと紙に書きまくってました。
でも、N = 2は全列挙できても、N = 3は全列挙とか2 ^ 9 = 514通りなので不可能ではないけど、事実上無理ですね。
今考えるとなんで全列挙しようとしたのか謎です。
多分幅優先探索とかでやるのが良かったんだと思います。

しかし、列挙していると段々法則が見えてきて、とりあえず１行埋めたら後はその行を使って埋まってない列を塗りつぶしていけばいいんじゃないかなと考えます。
全部塗りつぶすには少なくとも１行は真っ黒じゃないとダメですからね。
だから行ごとにその行を真っ黒にするための最短回数を求めて、全ての行の中で一番小さいものを真っ黒にして、後は黒く塗りつぶされてない列を塗りつぶしていけば最短回数になりそうだと思いました（厳密な証明はしてない）
そしてある行を塗りつぶすための操作回数は、まずその行の白の数分は最低必要です。一回の操作で１列しか塗れないので。
それだけで十分かというとそうではなくて、その行を塗るための黒がどっかに無いといけません。
その条件とは、塗りたい行をi番目とすると、列iに少なくとも１つ黒があることです。
もしない場合は、その列にまず１回黒を作るための操作（これはどこかに黒が１個あればできる）をしてから、行iを塗りつぶす作業をするので＋１回余分にかかります。
こうやってある行を塗りつぶすための最短回数が求められます。

結局これはO(N^2)で出来るのでいきなり満点解法が取れます。

……だったはずだったんですけど、変な勘違いをしており「i番目の行を塗り潰すためには(i, i)成分が黒じゃないといけない、そうでない場合は＋１」としており、部分点だけになってしまいました（間違ってるのになぜか部分点は取れた）

結局満点を提出したのはAに取りかかって、上手く行かず戻ってこの問題の解法を見直したときでした
一発で通せていればなあ、とか思いますが仕方ないですね

けれど配点の高い問題を解けたことは素直に喜ばしい事です
ただ1300点は配点高すぎな気がしますけどどうなんでしょうか
アルゴリズムも割と素朴だし、データ構造も２次元配列くらいしか使わないですし
Atcoderの配点の決め方がどうなってるか分からないですので何とも言えないですが

def solve():
    N = int(input())
    A = [[0 if j == '.' else 1 for j in input()] for i in range(N)]
    ans = 0
    min_r = float('inf')
    num_f = 0
 
    check = 0
    for i in range(N):
        check += sum(A[i])
    if check == 0:
        print(-1)
        return None
 
    for j in range(N):
        for i in range(N):
            if not A[i][j]:
                break
        else:
            num_f += 1
 
    if num_f == N:
        print(0)
        return None
 
    exits = [False] * N
    for j in range(N):
        for i in range(N):
            if A[i][j]:
                exits[j] = True
                break
 
    # min_r search
    for i in range(N):
        tmp = 0
        tmp += (not exits[i])
 
        for j in range(N):
            if A[i][j] == 0:
                tmp += 1
 
        min_r = min(tmp, min_r)
 
    ans = (N - num_f) + min_r
    print(ans)
 
if __name__ == '__main__':
    solve()

A - Robot Racing

Bを提出した後に部分点だけでも、と思ってやってましたが解けませんでした。
とりあえず、こんなにスッキリ解けるとは思いませんでした。
こっちも複雑なデータ構造とかアルゴリズムは使ってませんね
それでも確かに難しい問題なのでこういうのを良い問題って言うんだろうなあって思います

from math import factorial
 
def solve():
    N = int(input())
    X = [int(i) for i in input().split()]
    MOD = 10**9 + 7
    ans = 1
    stack = 0
 
    for x in X:
        stack += 1
        if x < 2*(stack - 1) + 1:
            ans *= stack
            ans %= MOD
            stack -= 1
 
    ans *= (factorial(stack) % MOD)
    ans %= MOD
 
    print(ans)
 
if __name__ == '__main__':
    solve()

前からi番目にいる蛙がゴールできるための必要十分条件が、全てのk < iに対してx[k] >= 2*k + 1が成り立っていること
というのがこの問題の肝ですね。
この条件を満たしていれば、それらの蛙を1, 3, 5, ... と配置して、後はその間をピョンピョン飛び越していけばいいわけですね。
逆にi番目の蛙がゴールできたと仮定すると、この蛙が前にいる蛙を飛び越した位置をy[k]とすると、y[1] >= 1, y[2] >= 2 + 1 = 3, y[3] >= 2*2 + 1 = 5, ... , y[k] >= 2*k + 1でなければいけないので逆も確かに成り立つので、必要十分ですね。

言われてみれば確かに、という感じですがコンテスト中に思いつけるかと言われると難しいですよね。

という感じでした。