2019-06-14

Paiza プログラミング練習問題 A - じゃんけんの手の出し方 (Python)

irisruneです。普段はAtCoderの問題を解いていますが、弊社がPaizaで求人を出していることもあって今回はPaiza プログラミング練習問題を解く記事を出してみました。

問題

（タイトルからわかりにくいと思いますが、問題ページへのリンクです。）

Aランク相当ではありますが正解率が低めで、下手なSランク問題より苦戦する人もいるかと思います。制約が $N\leq10^3$ と緩いのがポイントです。

import sys
import numpy as np


def main():
    n, m = [int(x) for x in input().split()]
    s = input()
    hand = [0, 0, 0]
    for h in s:
        if h == 'G':
            hand[0] += 1
        elif h == 'C':
            hand[1] += 1
        elif h == 'P':
            hand[2] += 1
    ans = 0
    for gi in range(n + 1):
        for ci in range((n + 1) - gi):
            pi = n - gi - ci
            if (gi * 0) + (ci * 2) + (pi * 5) == m:
                ans = max(ans, min(gi, hand[1]) + min(ci, hand[2]) + min(pi, hand[0]))
    print(ans)


main()

解き方としては、グー、チョキ、パーを出す回数の組み合わせを全探索して、指の本数が $M$ と一致する組み合わせについて最も多く勝った回数を出力すればよいです。グー、チョキの出す回数が決まればパーの出す回数は一意に決まるので組み合わせの数は $O(N^2)$ ですね。

グー、チョキ、パーを出す回数からじゃんけんに勝った回数を求める部分については、相手の出すグー、チョキ、パーの回数を数えておいて対応する手を出した回数を計算すればよいです。

じゃんけんに負けた回数も考える必要がある場合は少々難易度が上がると思いますが、今回の条件であれば全探索に気付くことができれば容易に求めることができると思います。

宣伝

弊社のPaiza求人紹介です。

少人数ながら多種多様なスキルとバックグラウンドを持ったエンジニアが集まっていることが弊社のエンジニア集団の面白いところ、いうことで、4つのポジションで募集を出しております。

それぞれ応募要件や条件等が異なりますが、惹かれる記事がありましたら、是非「気になる」に登録してみてください。（ちなみに、筆者は開発ラボの所属です）

雑記

当初は全勝した場合の指の本数を計算して、そこから指の本数が $M$ になるよう調整するという方針で考えていましたが色々と複雑になったのでなかったことになりました。
S問題、A問題をざっと見た感じ、十億連勝以外は解く方針が見えている（or既に解いた）ので不定期に取り扱うと思います。
PaizaはPythonなどの制限時間が15秒と長めなのもあり、言語による有利不利が少なめな気がします（ないこともないです）。
弊社採用担当がノベルティを頂いているので画像を貼っておきます。

2019-06-14

AtCoder ABC 129 E - Sum Equals Xor(Python)

競プロ AtCoder ABC129 E問題 500点 Python

irisruneです。最近AtCoder ProblemsのRecommendationsがスパルタに感じてきました。

問題

atcoder.jp

桁DPというヒントを見てしまいましたがほぼ自力です、多分。6/10の記事で実装が重いかと予想していましたが全然重くありませんでした。

import sys
import numpy as np
MOD = 1000000007


def main():
    bits = input()
    ans = 1
    pow3 = 1
    for i, b in enumerate(reversed(bits)):
        if b == '1':
            ans = ((ans * 2 % MOD) + pow3) % MOD
        pow3 = (pow3 * 3) % MOD
    print(ans)


main()

アルゴリズムの説明の前に今回使うXORの性質について、 $A+B=A xor B$ となるのはAとB両方が1である（ビット）桁が1つもない場合となります。例えば、 $A=1,B=2$ の場合は $A+B=A xor B=3$ と一致しますが $A=1,B=3$ の場合は $A+B=4,A xor B=2$ と一致しません。

逆に言えば今回使うXORの性質はこれ以外ないので、これさえ気付いてしまえばアルゴリズムを考えるのはそう難しくありません。具体的には、

0桁の $L'$ については答えを1通り（ $A=B=0$ ）とおく。
$L'$ に対し与えられた $L$ を一番右の桁から順番に追加する。
追加する桁の数字が0ならば、答えは変わらない。
追加する桁の数字が1ならば、答えを2倍し、 $3^\text{(追加する前の桁数)}$ を足す。

という方針で、ほとんど帰納法と言うべきアルゴリズムとなっています。

4.について補足をすると、 $1xxxxx_{(2)}\gt011111_{(2)}$ であることから $L'=xxxxx_{(2)},11111_{(2)}$ それぞれについて $A',B'$ が取り得る組み合わせ数を用いて $L=1xxxxx_{(2)}$ について $A,B$ が取り得る値の組み合わせ数を計算できます。

ここで、 $A,B$ の一番左の桁がどちらか一方のみ1の場合は2通りあるので、 $L'=xxxxx_{(2)}$ について $A',B'$ が取り得る組み合わせ数を2倍した数の組み合わせがあります。

一方、 $A,B$ の一番左の桁が両方0の場合は $11111_{(2)}$ について $A',B'$ が取り得る組み合わせ数を計算することになりますが、各桁について考えると $A'$ だけ1の場合、 $B'$ だけ1の場合、両方0の場合の3通りあるので3の累乗で求めることができます。

実装の軽さの割には細かくアルゴリズムを説明するのが大変難しいですね。~~解くだけならD問題より簡単だとは思いました。~~

雑記

実はTLEを一度起こしていて、3の累乗を求めるのにpow関数を用いたのが原因でした。そもそも余りを求める必要がある問題でpow関数を用いたのもミスですが、計算量もかかるものなんですね。

2019-06-12

AtCoder ABC 129 D - Lamp Pythonで解けなかったのでJuliaで(Python, Julia)

競プロ AtCoder ABC129 D問題 400点 Python Julia

irisruneです。C問題ではテストケースでトラブルがありましたが、D問題ではPythonの実行時間で少し騒ぎになっていたようですね。

問題

atcoder.jp

公式解説と少しアルゴリズムが違いますが大体同じ解き方です。具体的には、連続する障害物のないマスの数を走査する際に左右の2方向、上下の2方向の結果を統合しているような感じです。

import copy
import sys
import numpy as np


def main():
    h, w = [int(x) for x in input().split()]
    board = [input() for _ in range(h)]
    boardint = [[1 if c == '.' else 0 for c in board[i]] for i in range(h)]
    ansrow = copy.deepcopy(boardint)
    for i in range(h):
        for j in range(1, w):
            ansrow[i][j] = ansrow[i][j - 1] + 1 if boardint[i][j] == 1 else 0
        for j in range(w - 2, -1, -1):
            ansrow[i][j] = ansrow[i][j + 1] if boardint[i][j:j+2] == [1, 1] else ansrow[i][j]
    anscol = copy.deepcopy(boardint)
    for j in range(w):
        for i in range(1, h):
            anscol[i][j] = anscol[i - 1][j] + 1 if boardint[i][j] == 1 else 0
        for i in range(h - 2, -1, -1):
            anscol[i][j] = anscol[i + 1][j] if boardint[i][j] == 1 and boardint[i + 1][j] == 1 else anscol[i][j]
    print(np.max(np.array(ansrow) + np.array(anscol)) - 1)


main()

（最後のnumpyを使う部分を修正した上で）PyPyで提出してもTLEでした。通ったコードと比較した感じ、入力したグリッドを1-0変換する部分やリストのコピーを行う部分が余計だったのかもしれません。

問題を解いている時には他人のコードを見ていなかったので、Pythonで通す方法がなかなか思いつきませんでした。そういうわけで文法の似ているJuliaで全く同じように書き直してみました。

parseInt(x)=parse(Int,x)
parseMap(x::Array{SubString{String},1})=map(parseInt,x)

function main()
    h, w = parseMap(split(readline()))
    board = zeros(Int, (h, w))
    for i in 1:h
            s = readline()
        for j in 1:w
            board[i, j] = s[j] == '.' ? 1 : 0
        end
    end
    ansrow = deepcopy(board)
    for i in 1:h
        for j in 2:w
            ansrow[i, j] = board[i, j] == 1 ? ansrow[i, j - 1] + 1 : 0
        end
        for j in w-1:-1:1
            ansrow[i, j] = board[i, j] == 1 && board[i, j + 1] == 1 ? ansrow[i, j + 1] : ansrow[i, j]
        end
    end
    anscol = deepcopy(board)
    for j in 1:w
        for i in 2:h
            anscol[i, j] = board[i, j] == 1 ? anscol[i - 1, j] + 1 : 0
        end
        for i in h-1:-1:1
            anscol[i, j] = board[i, j] == 1 && board[i + 1, j] == 1 ? anscol[i + 1, j] : anscol[i, j]
        end
    end
    print(maximum(ansrow + anscol) - 1)
end

main()

手元の環境（Julia1.1.0）とAtCoder上の環境（Julia0.5.0）との違いによりREを2回出していますが、とりあえず通りました。特に困ったのはrange()関数の仕様の違いでしたがコロンによる記法を使うことで解決しました。

PythonとJuliaのコードを見比べると一番目立つのはインデックスが0始まりか1始まりかという違いでしょうか。個人的には競プロの問題を解く上では1始まりの方がやりやすい気はしますね。Juliaでコードブロックを閉じるのに逐一endが必要なのは少々煩雑ですが仕方ないのかもしれません。

コードレビューとして、3項演算子を使うと（特に条件式が複合している場合に）1行が長くなりがちですね。JuliaはともかくPythonはどこに改行を挟んでよいかの判断が難しいです、リスト内法表記以外で3項演算子を使わない方がよいのかもしれませんが。

雑記

今PythonでAtCoderの問題を解いているのには一応理由があるのですが、今回のようなケースがあると色々考え直す必要があるかもしれないですね。
Pythonで435msを叩き出している人がいるようで、わかる人が工夫すると割とどうにでもなるんだなと思いました。

2019-06-10

AtCoder ABC 129 C - Typical Stairs (Python)

競プロ AtCoder ABC129 C問題 300点 Python

irisruneです。今回不参加でしたがトラブルがあって大変だったみたいですね。

問題

atcoder.jp

当のトラブルがあった問題です。問題自体は最近珍しい気もする典型問題です。

import sys
import numpy as np

MOD = 1000000007

def main():
    n, m = [int(x) for x in input().split()]
    pattern = [1]
    broken = -1
    brokencnt = 0
    if brokencnt < m:
        broken = int(input())
        brokencnt += 1
    for i in range(1, n + 1):
        if i == broken:
            pattern.append(0)
            if brokencnt < m:
                broken = int(input())
                brokencnt += 1
            continue
        if i == 1:
            pattern.append(pattern[i - 1])
        if i > 1:
            pattern.append((pattern[i - 1] + pattern[i - 2]) % MOD)
    print(pattern[n])


main()

アルゴリズム的には典型的なDPで、追加条件として壊れた段については移動できない（=移動方法が0通り）という扱いにするだけです。見た感じ正解者数が少なく見えるのはトラブルの影響…なんですかね。

色々考えるのが面倒になったので処理を行いながら入力を読み込むという手法を取っています。Pythonの配列アクセスにかかる時間を考えると多少速くなるのかもしれないですが、公式解説のコードに比べて（ $M=0$ の場合分けが必要など）記述が少し複雑になっている気がします。

雑記

D問題、E問題はアルゴリズム的には難しくなさそうですが実装に少し時間かかりそうなのと少し忙しいのでまた後ほど。
先週Paiza練習問題を扱うと言っていたのは忘れていました。とりあえず今週に何か書く予定です。

2019-06-07

AtCoder ABC 123 D - Cake 123 をNumpyを用いてスマートに解きたかった話 (Python)

競プロ AtCoder ABC123 D問題 400点 Python

irisruneです。Numpyを有効に使って計算時間を短くしたかったのですが、なかなか難しいですね。

問題

atcoder.jp

公式解説でも解法が複数説明されていますが、どう解くとしても手法に工夫が必要でかなり難しいです。~~AtCoder ProblemsのDifficulty684しかないって本当ですか。~~

また、解説ACのためアルゴリズム面の解説はあまり行いません。

提出1（公式解説：解法2）

import sys
import numpy as np


def main():
    x, y, z, k = [int(n) for n in input().split()]
    a = sorted([int(n) for n in input().split()], reverse=True)
    b = sorted([int(n) for n in input().split()], reverse=True)
    c = sorted([int(n) for n in input().split()], reverse=True)
    va = np.array(a)[:, np.newaxis, np.newaxis]
    vb = np.array(b)[np.newaxis, :, np.newaxis]
    vc = np.array(c)[np.newaxis, np.newaxis, :]
    vx = np.arange(1, x + 1)[:, np.newaxis, np.newaxis]
    vy = np.arange(1, y + 1)[np.newaxis, :, np.newaxis]
    vz = np.arange(1, z + 1)[np.newaxis, np.newaxis, :]
    print(*(sorted((va + vb + vc)[(vx * vy * vz) <= k], reverse=True))[:k], sep="\n")


main()

結論から言えばこれはREでした。

方針としてはすべての組み合わせについてのケーキの美味しさの合計を3次元行列の形で持ち、最終的な出力に含まれる可能性のあるケーキのみをブーリアンマスクで抽出して1次元リストに変換、それをソートして出力するというものです。

まあ、 $1000\times1000\times1000$ の3次元行列を作ったらREも起こしますよね。

提出2（公式解説：解法1）

import sys
import numpy as np


def main():
    x, y, z, k = [int(n) for n in input().split()]
    va = np.array(sorted([int(n) for n in input().split()], reverse=True))[:, np.newaxis]
    vb = np.array(sorted([int(n) for n in input().split()], reverse=True))[np.newaxis, :]
    xy = min(x*y, k)
    vac = np.array(sorted((va + vb).reshape(-1), reverse=True)[:xy]).reshape(xy, 1)
    vc = np.array(sorted([int(n) for n in input().split()], reverse=True))[np.newaxis, :]
    xyz = min(x*y*z, k)
    print(*(sorted((vac + vc).reshape(-1), reverse=True)[:xyz]), sep="\n")


main()

REを起こす原因として異常に大きな行列という推測が立てられたので、最大でも $3000(\leq K)\times1000$ の2次元行列で済むように解いてみました。方針としては2つのケーキの美味しさの合計を2次元行列の形で持ち、大きい方から $K$ 個を1次元リスト（ベクトル）の形に置き換えた後に残り1つのケーキの美味しさとブロードキャスト計算を行うといったものです。

しかしこちらはTLEになってしまいました。ブロードキャスト演算自体は高速で行われると思われるので、 $X\times Y$ （あるいは $K\times Z$ ）の2次元行列を1次元ベクトルに変換する処理に時間がかかっているものと推測されますが、実際の所はわかりません。

提出3（公式解説：解法1）

import sys


def main():
    x, y, z, k = [int(n) for n in input().split()]
    va = sorted([int(n) for n in input().split()], reverse=True)
    vb = sorted([int(n) for n in input().split()], reverse=True)
    xy = min(x*y, k)
    vab = (sorted([a + b for a in va for b in vb], reverse=True))[:xy]
    vc = sorted([int(n) for n in input().split()], reverse=True)
    xyz = min(x*y*z, k)
    print(*((sorted([ab + c for ab in vab for c in vc], reverse=True))[:xyz]), sep="\n")


main()

結局、Numpyを用いずに解いたところACできました（1757msかかっていますが）。リスト内法表記を使えばNumpyを用いるメリットも薄い…んでしょうか？まだよくわかっていないですね。

雑記

提出3のコードをPyPy3で提出すると727msしかかかりませんでした。Numpy…というよりPythonって難しいですね。

2019-06-05

AtCoder AGC 034 B - ABC (Python)

競プロ AtCoder AGC034 B問題 600点 Python

irisruneです。当初Pythonで解けなくてGoで解いていたのですが、ミスに気付いたのでPythonで解き直しました。~~TLEしたときにすぐPythonのせいにするのはよくないですね。~~

atcoder.jp

600点としてはかなり簡単な方で、少なくとも土曜日の企業コン500点問題よりは簡単だと思いました。

s = input()
ans = 0
cntA = 0
for i in range(0, len(s) - 1):
    if s[i] == 'A':
        cntA += 1
    elif s[i: i + 2] == "BC":
        ans += cntA
    elif i > 0 and s[i - 1: i + 1] == "BC":
        continue
    else:
        cntA = 0
print(ans)

方針としては、

"A"と"BC"が隣接していると"ABC"→"BCA"となる。
"AAA...A"と連続しているケースについても上記の操作を繰り返すと、"AAA...ABC"→"BCAAA...A"となる。
同様に"BCBCBC...BC"と連続しているケースについても上記の操作を繰り返すと、"ABCBCBC...BC"→"BCBCBC...BCA"となる。

という規則性を見つければ"A"と"BC"とそれ以外（"AC"とか"BB"とか）を判別しながら処理を行うだけとなります。"BC"が出現する直前の連続する"A"の個数が変換後の末尾の"A"の個数と一致するのがポイントですね。

ただ後で気付いたので仕方ないですが、解説のように"BC"を"D"に置換した方がかなり解きやすいですね。置換しなかった場合は上記コードのようにインデックスで回しながら隣接文字と同時にチェックするか、フラグ管理しながら1文字ずつチェックするかになってどちらにせよ煩雑になります。

雑記

Pythonで最初解こうとしたときは規則性を把握しきれず、二重ループにしてしまい計算量がになってTLEしてしまいました。
- 慣れていない言語で書くと色々気が回らなくなるものですね。
Goで"BC"を"D"に置換するのはそれはそれで難しいような気もしなくはないです。
- 文字列分割→文字列結合という処理になりそうですが、文字列長が大きいときに計算量が多くかかる気がします。
- stringsパッケージを使えば置換ができるようなのであとは計算量次第でしょうか。
  - 追記：置換を行ってもほとんど実行時間変わらずにACできました。

2019-06-05

AtCoder AGC 034 A - Kenken Race (Python)

競プロ AtCoder AGC034 A問題 400点 Python

irisruneです。Pythonを勉強し始めたので解ける問題はPythonで解くことが多くなると思います。

atcoder.jp

一見難しそうで思いつけば簡単…と思わせて引っ掛けポイントがある、そんな問題だと思います。

import sys
n, a, b, c, d = [int(x) for x in input().split()]
s = input()
for i in range(a, max(c, d)):
    if s[i - 1: i + 1] == "##":
        print("No")
        sys.exit()
if c < d:
    print("Yes")
    sys.exit()
for i in range(b - 1, d):
    if s[i - 1:i + 2] == "...":
        print("Yes")
        sys.exit()
print("No")

大体解説の通りですが気付く必要があるポイントは3つあり、

区間 $[A, C], [B, D]$ のいずれかで岩が2つ連続する部分が存在する場合、題意は達成不可能。
$D\lt C$ の場合、すぬけくんがふぬけくんを追い越すために岩のないマスが3つ連続する部分が必要。
すぬけくんがふぬけくんを追い越すためのスペースは区間 $[B-1, D+1]$ に存在する必要がある。

以上3つを守れば問題を解くことができます。特に見逃しやすいと考えたのは3つ目で、すぬけくんが通過する必要のある区間 $[A, C]$ のうち、ふぬけくんを追い越すことができるのはふぬけくんが通過する区間 $[B, D]$ のみとなります。そして追い越すためには岩のないスペース3つが必要なのですが、そのうち真ん中の1マスにふぬけくんがいればよいので、区間 $[B-1, B+1], [D-1, D+1]$ に岩がない場合でも追い越すことが可能となります。

長々と説明しましたが、解説のように区間 $[B, D]$ のいずれかのマスを中心とした3マス分のスペースと考えた方がわかりやすいですね。

雑記

岩の有無を1と0に変換した上でベクトル化するとnumpyを使ってうまく解けるかもしれません。
- 累積和を計算して、区間ごとの累積和の差を行列化する形にすればよさそうでしょうか。

2019-06-03

AtCoder ABC 128 D - equeue (Go)

競プロ AtCoder ABC128 D問題 400点 Go

irisruneです。この土日のコンテストは不参加だったのもあり記事にするのは間に合いませんでした。

https://atcoder.jp/contests/abc128/tasks/abc128_d

~~"D"equeueとかけてるからD問題なんですかね。~~B、Cが難しければDも難しいときました。効率の良い方法を探そうとするとドツボにはまりそうな問題です。

package main

import (
    "bufio"
    "fmt"
    "os"
    "sort"
    "strconv"
)

var sc *bufio.Scanner

func nextInt() int {
    sc.Scan()
    i, e := strconv.Atoi(sc.Text())
    if e != nil {
        panic(e)
    }
    return i
}

func minInt(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func maxInt(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func sumValue(jewels []int) int {
    ret := 0
    for _, j := range jewels {
        ret += j
    }
    return ret
}

func main() {
    sc = bufio.NewScanner(os.Stdin)
    sc.Split(bufio.ScanWords)
    n, k := nextInt(), nextInt()

    deque := make([]int, n)
    for i := range deque {
        deque[i] = nextInt()
    }

    ans := 0
    // i : 操作回数
    // j : 宝石を取り出す回数
    // m : 左から宝石を取り出す回数
    // l, r : 左右から宝石を取り出す処理を回す変数
    for i := 0; i <= minInt(k, n*2); i++ {
        for j := (i + 1) / 2; j <= minInt(i, n); j++ {
            for m := 0; m <= j; m++ {
                var jewels []int
                for l := 0; l < m; l++ {
                    jewels = append(jewels, deque[l])
                }
                for r := 0; r < j-m; r++ {
                    jewels = append(jewels, deque[n-1-r])
                }
                sort.Sort(sort.Reverse(sort.IntSlice(jewels)))
                jewels = jewels[0 : j-(i-j)]
                ans = maxInt(ans, sumValue(jewels))
            }
        }
    }

    fmt.Println(ans)
}

制約が非常に緩いので結局全探索するだけです。~~BもCも全探索だったような気はしますが~~全探索のアルゴリズムや実装を考える必要があるのでやや難しいとは思います。

今回取った全探索アルゴリズムは、

操作回数を $R=0,1,\dots,\min(2N,K)$ 回とおく。
宝石を取り出す回数を $A+B=\lceil\frac{2}{R}\rceil,\dots,\min(R,K)$ 回とおく。
左から宝石を取り出す回数を $A=0,1,\dots,A+B$ 回とおく。
右から宝石を取り出す回数を $B$ 回とおく。
取り出した宝石から価値の低い順に宝石を戻す動作を $R-(A+B)$ 回行う。
残った宝石の価値を合計する。

というものです。公式解説に変数名を揃えてみましたが、無駄に複雑なアルゴリズムになってるのがよくわかりますね。

主に1.と2.が無駄な処理になっており、全ての操作回数を定めた上で宝石を取り出す回数の合計も定めているため見た目が複雑になったり、計算量も[tex:O(R⁴\log R)(R=\min(N,K))]と余分にかかったりしています。

雑記

今週あたりPaizaの練習問題を扱うこともあるかもしれません。（スキルチェック問題は扱いませんよ！）

2019-05-31

AtCoder ARC 042 B - アリの高橋くんをテーマに弊社エンジニアで対談会

対談記録競プロ AtCoder ARC042 B問題 100点

irisruneです。ようやく対談会を記事にまとめることができました。

コードがなかったりいつもとスタイルが違いますが、お付き合いいただければと思います。

問題

atcoder.jp

登場人物紹介

筆者I:irisrune

エンジニアA:AtCoderはやったことはないが周りにやっている人がいた。また、Project Eulerで問題を解いていたことがある。

エンジニアB:一時期AtCoderをやっていたが、茶色になって以降数か月AtCoderをやっていない。

対談記録

A:なるほど。問題はわかりました。

B:これABCですか？…ARCですか、なるほど。

A:とにかく垂線を下ろせれば終わりって話ですね。配点は何点でしょうか。

I:この時期の問題は難易度で分けられていなかったので、全部100点の配点です。

A:これって数学の知識あればいけますか？

I:中学校～高校くらいの数学の知識ですかね。¹

A:三角関数使えれば楽そうですが。

I:三角関数は使いますかね？解説を見ると大学レベルの知識が必要かも…ですが垂線を下ろすのがお手軽だとおもいます。²

A:なんで垂線がお手軽なんだろう…

B:うーん、今回のゴールは僕が理解できることですね（笑）

I:いくらでもネット検索とか使って大丈夫ですよ（笑）

B:そうか、最短だからどうやっても垂線になるのか。これが5角形、6角形になると…中学校の数学の知識が危うくなってきましたね。辺の数が頂点の数だけある、そこから垂線を引くことをすべての辺について試していくと。

A:例えば、三角形を考えて…

I:（ググって垂線の長さの解説や、『点と直線の距離』の公式を出す）

A:2点から直線を求める公式をググればいいんですかね。あ、三角形の垂線の長さを求めてもいいですよね。すべての辺の長さがわかっている状態ならなんとか行ける気がするんで。

B:どんな多角形でも辺はある1点と1点の2点の間にあって、高橋君がいるのはどこかの辺の間の1点で、それを繋ぐとどうやったって三角形になる？

I:それはその通りです。ただ、三角形だと逆に難しくないですか？実装はともかく発想は点と直線の方が楽だと思います。³

B:頂点の中から一番近い頂点の直線で行くということ？

I:別に全部の辺を使ってもいいですよね。

A:これ、多い場合に抑える工夫はありますか？例えばかなり $N$ がでかいときとか…

I:ぶっちゃけないですね。どうやっても全探索になるし、どうやっても $N$ になる。

A:どの垂線が短いかという判断がつかないですよね？

I:そうですね、その判断は相当難しいですね。

B: $2N$ になりますか？

I:普通に $N$ ですね。

B:まずどうやっても、全部の点と頂点の距離を求めていくことにはなりますか。

A:そうですね。あ、ヘロンの公式っていうのがありますよ。3辺の長さがわかれば面積を求められるという。面積を2倍して、各辺の長さで割ってあげれば出る！

B:ヘロンの公式！なんかやったなあ。⁴

A:数学者って本当こういうの好きだよなあ（笑）

B:三角形があるとして、1番近い点と2番目に近い点を算出して…この2点を出して、点が結んでいる線に対して垂線を下ろす、という風にするとダメですかね？

I:うーん、まあダメですね。ダメな理由は、「近い頂点」というのがかなり危険ですね。遠い頂点でも簡単にギリギリのところに通せるので。

f:id:amifiable:20190531114341p:plain — 即興で作った例

A:では3辺の長さの比率が大事になる？角度は出せますよね？頂点の距離で考えるのであればですけど。頂点で考えるのは厳しいですね。

I:頂点を使うのならば、ヘロンの公式ですね。

A:やはり点と直線の距離ですかね。

I:点と直線の距離は、えげつないことを言いますと、3点があれば求められるという公式がググれば出てくるんですよね。ヘロンの公式を使った結果を展開しても同じになりますね。

B:標準入力だとだめですね…配列で受け取れない。Javaなら行けそうですけど。

I:（Pythonの）標準入力見てみましょうか。でもPython書くとなるとわからないので、書くならGoですね。⁵

A:公式に従ってやっていけばいいだけですよね。あれ、この問題ってインプットは何ですか？順番に点って与えられてるんですか？

I:（条件の部分を見せる）⁶

A:多角形が保証されていないと大変ですけど、それならいいですね。

B:保証されていないとどうなるんですか？

A:要は、頂点がランダムで与えられたときに構成される多角形って…

f:id:amifiable:20190531114414p:plain — 数字の順番に点が与えられたときのイメージ

A:どの点とどの点の間の辺なのかというのを特定しなければいけなくなると。

I:解こうと思えば解けますけど、難易度がかなり上がりますね。ARCでB（ABCでD）でもおかしくなくなるかな。今の状態だと300点あるか怪しいのが、400点くらいにはなりそうですね。

A:これってどのくらいの時間で解くんですか？

I:目指すレート帯にもよりますね。10分くらいで解ければ1200は目指せるでしょうか。

A:調べながらで、入出力がわかっていればまずまずいける範囲だと。

I:他の人の解答を見てみましょう。

A:まあそうなりますよね。あとは言語によって癖ありますよね。

B:やるべきことは何かを的確に見抜けること、その数式を実装できることが求められる。算数ができるかということですかね。

I:算数できなくても、調べる力があるというのが大事ですね。点と直線の公式というのを覚えていないと調べようがないかもしれませんが。

A:点と直線という単語を使わなくても、垂線を下ろすというのがわかればいけそうですね。実装自体はそんなに難しくないですね。

I:サンプルで試せば間違いは出てくるので、数式打ち間違えてもわかりますね。許容の誤差もありますし。

A:ルート取って割り算するだけだから、誤差も出ないですよね。2点間の距離があまりにも小さいとやばいかもしれない？

I:その場合も、相対誤差でいけるのでは。さっき答え見ちゃいましたけど、公式の解説も見てみましょうか。急に回転し始めましたね。（笑）

A:回転って、ローテーションめんどくさいイメージしかないですけど。

I:確かに普通にめんどい。平行移動まですると明らかに難易度跳ね上がってますよね。

A:嘘だろー、難しくなってるけど大丈夫か？

I:複素平面を用いると回転が楽になると。これは大学の知識ですね。解説が妙に難しいですね。

A:初見でこれ思いつく人って相当ですよ。問題に対してオーバースキルでは？でも計算量が抑えられるんですかね。

I:計算量は変わらないけど、記述量は抑えられますね。Rubyで複素平面を使った解答なんかはかなり短いですね。速さはあまり変わらなさそう。この問題についてはこんなところですかね。

A:ポイントは垂線を下ろすということに気付くかどうか。

I:全部の辺に対してというところ、全探索に気付くかどうか。あと最後の条件（凸多角形が保証される）は見落としても凹多角形でもいいかも…？⁷

（各人の感想）

A:細かい条件がわかっていないと解けるものも解けなくなるということ実感しました。あとなんだかんだ数学の知識がないと大変な時もあるのかなと。

B:競プロを解くって、（プログラミング知識があっても）競プロの脳みそにもっていくのが難しいなと。普段全く使わない方向に脳みそのベクトルを持っていかなくてはいけないのが辛い。楽しいといえば楽しいけど。自分も茶色に行くまでには6ヶ月かかったんで、何も考えてないない人間がやろうとするとそのくらいかかりますね。

I:今回アルゴリズムは難しくないものを議題に選んだので、早めに終わるかと思いましたが、考察詰めていくと結構時間がかかるなと思いました。⁸思い付きで走りがちなんですが、話し合うと注目するポイントも多いんだなという感想です。

A:慣れてくれば情報の取捨選択が速くなりますね。

I:逆に条件を見落とすこともありますけどね。例えば制約として $N=10^5$ が多いんですが、この問題は $N=10$ だから色々なやり方ができる。 $N=10$ だと、 $2^{10}$ もいけますし、（言語や処理内容によっては） $10^8$ とかもいけますね。

A:プログラミング言語ってうまくできているんだなと実感する瞬間が、競プロの問題を見ているとありますね。

I:あとはサンプルからどのくらい情報が取れるかですね。

A:前に何の情報もないサンプルありましたよね。（笑）⁹

I:ありましたね。（笑）YYMMかMMYYかを見分ける問題なんかは、サンプルを見て00年はあるけど00月はないということに気付いたりしましたね。

A:ちゃんと条件を把握しましょうということですね。

後書き

舵取りをある程度行えるように予習済みの問題を持ち込んだのですが、逆に少し急ぎ気味になりそうで難しいところはありました。

自分で解いたときには点と直線の距離を思いついてググって公式入れて終わらせてしまったのですが、他の人がどんな道筋で考えるのかを知るいい機会だったと思います。

対談会に協力してくださったエンジニアのお二方と記録を担当してくださった方々には感謝しています。

後は公式解説を軽くネタにしてしまってごめんなさいですね。

任意の二点を通る直線は中学生の範囲を超えてそうですね。↩
余弦定理を使ったり想定より難しい解法に向かいそうで内心焦ってました。↩
完全に個人の感想です。↩
使ったことがなかったので存在すら忘れていました。↩
最近Pythonをやる必要に迫られたので今ならPythonで書けそうです。↩
ここまで（予習済みの自分以外）条件を知らない状態でした。条件は考察する前に見ましょう、見せましょう。↩
ダメでした。↩
おもむろに点と直線の距離をググったり露骨な時短狙いしてましたね。↩
この問題のことです。記事にもしてます。↩

2019-05-29

AtCoder ABC 128 B - Guidebook (Go)

競プロ AtCoder ABC128 B問題 200点 Go

irisruneです。D問題を記事にする予定でしたがB問題が結構難しかったので取り上げてみました。

atcoder.jp

簡単なC問題（ex.ABC127C）より難しい気がします。

package main

import (
    "bufio"
    "fmt"
    "os"
    "sort"
    "strconv"
)

var sc *bufio.Scanner

func nextInt() int {
    sc.Scan()
    i, e := strconv.Atoi(sc.Text())
    if e != nil {
        panic(e)
    }
    return i
}

type restaurant struct {
    i int
    s string
    p int
}

type restaurants []restaurant

func (r restaurants) Len() int {
    return len(r)
}

func (r restaurants) Swap(i, j int) {
    r[i], r[j] = r[j], r[i]
}

func (r restaurants) Less(i, j int) bool {
    if r[i].s != r[j].s {
        return r[i].s < r[j].s
    }
    return r[i].p > r[j].p
}

func main() {
    sc = bufio.NewScanner(os.Stdin)
    sc.Split(bufio.ScanWords)
    n := nextInt()

    var rest restaurants = make([]restaurant, n)
    for i := range rest {
        sc.Scan()
        rest[i].i, rest[i].s, rest[i].p = i+1, sc.Text(), nextInt()
    }
    sort.Sort(rest)

    for _, r := range rest {
        fmt.Println(r.i)
    }
}

問題の条件として、

市名が辞書順で早いものから紹介していく。

同じ市に複数レストランがある場合は、点数が高いものから紹介していく。

というものがあるため、直感的に解く場合にはソートが必要不可欠となります。そして市名の昇順ソートと点数の降順ソートの両方が求められること、最終的な出力として要求されるレストランの番号も保持しておかなければならないことにより複雑さが増しています。

とりあえずソートにより解く場合について考えます。この場合の方法としては大きく3通り考えられ、

市名（昇順）と点数（降順）との複合条件でソートを実装する。
まず点数（降順）でソートを行い、その後安定なソートアルゴリズムで市名（昇順）についてソートを行う。
市名に辞書順で昇順になるように文字列と対応させた点数を結合させてそれについてソートを行う。
- 例えば、0点→100、1点→099、…、100点→000といったように100の補数表現を3桁表記にする形で実装可能。

といった方法になります。公式解説や上記のコードは1つ目の複合条件によるソートとなります。~~思いついたから書いてみましたが3つ目の方法は説明が難しいですね。~~

公式解説によるとPair型を適切に使えば単純なソートで実装できるようですが、それを含めてもB問題の範疇を大きく超えてしまっているとは思います。

なお、別解としてソートを使わずひたすらループを回して次に出力するレストランを探し続けるやり方（計算量 $O(N^2)$ ）が紹介されています。こちらのやり方はまだB問題らしいと思いますが、問題文がソートを使うよう誘導してくる上に解説もソートで解くことを前提としているので、やはりC問題と間違えてるような気がします。

雑記

D問題も一応解いてはいますが、あまりにもゴリ押しが過ぎる~~のと対談記事も上げたい~~ので記事にするかは未定です。

2019-05-29

AtCoder ABC 128 C - Switches (Go)

競プロ AtCoder ABC128 C問題 300点 Go

irisruneです。今日の記事は参加しなかった方のコンテストです。

atcoder.jp

ABC127とは打って変わって少々厄介な問題です。

package main

import (
    "bufio"
    "fmt"
    "math"
    "os"
    "strconv"
)

var sc *bufio.Scanner

func nextInt() int {
    sc.Scan()
    i, e := strconv.Atoi(sc.Text())
    if e != nil {
        panic(e)
    }
    return i
}

type light struct {
    ss int
    p  int
}

func main() {
    sc = bufio.NewScanner(os.Stdin)
    sc.Split(bufio.ScanWords)
    n, m := nextInt(), nextInt()

    lights := make([]light, m)
    for i := range lights {
        k := nextInt()
        for j := 0; j < k; j++ {
            s := nextInt()
            lights[i].ss += 1 << uint(s-1)
        }
    }
    for i := range lights {
        lights[i].p = nextInt()
    }

    ans := 0
    for x := 0; x < int(math.Pow(2.0, float64(n))); x++ {
        flg := true
        for _, l := range lights {
            elec := l.ss & x
            cnt := 0
            for i := 0; i < n; i++ {
                cnt += (elec >> uint(i)) & 1
            }
            if cnt%2 != l.p {
                flg = false
            }
        }
        if flg {
            ans++
        }
    }
    fmt.Println(ans)
}

制約条件が緩いので単純な全探索問題ではあります。今回は練習も兼ねてbit全探索で実装しましたがDFSでもいいですね。

ただし電球が点灯する条件が少々複雑で、簡潔に書く方法がなかなか思いつきませんでした。今回は、

予め各電球に対して対応するスイッチの組み合わせを2進数変数に変換しておく。
onになっているスイッチの組み合わせと1.で用意した電球に対応するスイッチの組み合わせとでAND演算した結果を取る。
2.の結果について1となるbit数を数え上げ、2で割った余りを求めて電球が点灯するか判定する。
3.をすべての電球に対して判定し、すべて点灯するなら解に1を足す。
onになっているスイッチの組み合わせすべてに対して2.から4.を繰り返す。

といった実装の方法をとりましたが、もっと簡潔に書ける気はしています。

全探索が思いついて実装できるかと、細かい処理を正確に実装できるかの両方が問われるのでなかなか難しい問題だと思います。~~前回のC問題がかなり易しかっただけとも言えそうです。~~

雑記

今回一番欲しかったのは変数名のセンスです。

2019-05-27

AtCoder ABC 127 D - Integer Cards

競プロ AtCoder ABC127 D問題 400点 Go

irisruneです。今日は試しに2記事公開してみました。

atcoder.jp

アルゴリズムの発想と計算量の抑え方の両面が重要となる問題だと思いました。半分嘘解法です。

package main

import (
    "bufio"
    "fmt"
    "os"
    "sort"
    "strconv"
)

var sc *bufio.Scanner

func nextInt() int {
    sc.Scan()
    i, e := strconv.Atoi(sc.Text())
    if e != nil {
        panic(e)
    }
    return i
}

type operation struct {
    b int
    c int
}

type ope []operation

func (o ope) Len() int {
    return len(o)
}

func (o ope) Swap(i, j int) {
    o[i], o[j] = o[j], o[i]
}

func (o ope) Less(i, j int) bool {
    return o[i].c < o[j].c
}

func main() {
    sc = bufio.NewScanner(os.Stdin)
    sc.Split(bufio.ScanWords)
    n, m := nextInt(), nextInt()

    aArray := make([]int, n)
    for i := 0; i < n; i++ {
        aArray[i] = nextInt()
    }

    var o ope = make([]operation, m)
    for j := 0; j < m; j++ {
        o[j].b, o[j].c = nextInt(), nextInt()
    }
    sort.Sort(sort.Reverse(o))

    cnt := 0
    for j := 0; j < m && cnt < n; j++ {
        for k := 0; k < o[j].b && cnt < n; k++ {
            aArray = append(aArray, o[j].c)
            cnt++
        }
    }
    sort.Sort(sort.Reverse(sort.IntSlice(aArray)))

    ans := 0
    for i := 0; i < n; i++ {
        ans += aArray[i]
    }

    fmt.Println(ans)
}

ベースとなる考え方は、元々ある $N$ 枚のカードと $j=1,2,\dots,M$ に対応する整数 $C_j$ の書かれた $B_j$ 枚のカードを合わせた中から、大きい順に $N$ 枚取り出した整数の合計を求めるというものです。ただし制約条件が $1\leq M\leq 10^5,1\leq B_j\leq N\leq 10^5$ であるため、最終的なカードの枚数は最大で $10^{10}$ 枚を上回ります。つまり安直にカードの集合を足し合わせてソートするとTLEしてしまいます。

それを解消するために取った方法が、集合に足し合わせるカードの枚数に $N$ 枚という上限を設けるものでした。これによりソート処理でTLEすることはなくなるため問題を解くことができます。

公式解説にあるように、足し合わせるカードを1枚ずつバラさずに集合のまま扱うとすべての集合を足し合わせた上でソートできるため記述はかなり易しくなると思います。

ちなみに、本コードの計算量は $O(M\log M + N\log N)$ となります。実際は後半が $2N$ であり、またカード追加の際に枚数で逐一判定しているため公式解説と比べると定数倍遅いと思います。

雑記

対談会の記事は先週公開と書いていましたが、今週予定に変更します。

2019-05-27

AtCoder ABC 127 C - Prison (Go)

競プロ AtCoder ABC127 C問題 300点 Go

irisruneです。水パフォですが久々にレートが伸びて嬉しい気分ですね。

atcoder.jp

最近のC問題にしてはかなりシンプルな問題だと思います。

package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
)

var sc *bufio.Scanner

func nextInt() int {
    sc.Scan()
    i, e := strconv.Atoi(sc.Text())
    if e != nil {
        panic(e)
    }
    return i
}

func maxInt(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func minInt(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func main() {
    sc = bufio.NewScanner(os.Stdin)
    sc.Split(bufio.ScanWords)
    n, m := nextInt(), nextInt()

    maxL, minR := 1, n
    for i := 0; i < m; i++ {
        l, r := nextInt(), nextInt()
        maxL, minR = maxInt(maxL, l), minInt(minR, r)
    }

    fmt.Println(maxInt(0, minR-maxL+1))
}

公式解説でいうところの考え方1の解き方です。単純に $L$ の最大値と $R$ の最小値を求めてそこから答えを導き出すだけでした。

考え方2についても考察してみましたがコード自体は結局変わらなさそうです。

雑記

ABC128は遅刻確定したのと2日連続参加の気力はなかったのとで未参加でした。

2019-05-24

AtCoder AGC 017 A - Biscuits で色々な解き方を試してみる (Go)

競プロ AtCoder AGC017 A問題 200点 Go

irisruneです。AtCoder ProblemsのRecommendations機能のおかげで精進に困らなくていいですね。

atcoder.jp

失敗例含め4回解いていますが、大筋はあまり変わらない上に~~想定解法が天才解法なので~~全部嘘解法です。

失敗例

package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
)

var sc *bufio.Scanner

func nextInt() int {
    sc.Scan()
    i, e := strconv.Atoi(sc.Text())
    if e != nil {
        panic(e)
    }
    return i
}

func bico(n, r int) int {
    if n < r {
        return 0
    }
    if r > 0 && n/r < 2 {
        r = n - r
    }
    denom, numer := 1, 1
    for i := 1; i <= r; i++ {
        denom *= n - i + 1
        numer *= i
    }
    return denom / numer
}

func main() {
    sc = bufio.NewScanner(os.Stdin)
    sc.Split(bufio.ScanWords)
    n, p := nextInt(), nextInt()

    cnt0, cnt1 := 0, 0
    for i := 0; i < n; i++ {
        a := nextInt()
        switch {
        case a%2 == 0:
            cnt0++
        default:
            cnt1++
        }
    }

    ans0 := 0
    ans1 := 0
    for j := 0; j <= cnt0; j++ {
        ans0 += bico(cnt0, j)
    }
    for k := p; k <= cnt1; k += 2 {
        ans1 += bico(cnt1, k)
    }

    fmt.Println(ans0 * ans1)
}

前回の雑記で触れた入力の最適化を行っているのでテンプレートが少し長くなっています。

大筋としては、ビスケットの数が偶数の袋と奇数の袋の数をそれぞれ数え上げ、偶数の袋を選ぶパターン数と奇数の袋を選ぶパターン数を二項係数として計算して掛け合わせるというものになります。

剰余を要求されていないため逆元を~~知らなくても~~使わなくても解くことができますね。

ただしこのコードは、例えば $N=50$ のとき計算結果（の分母部分）に $50\times49\times...\times25\simeq1.96\times10^{29}$ が入ってしまうので64bit型整数ではオーバーフローしてしまいます。そのためWAとなってしまいました。

ちなみに、計算量は $O(N^3)$ と大きめです。

有理数の形ではなく実数の形で計算結果をもつ

package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
)

var sc *bufio.Scanner

func nextInt() int {
    sc.Scan()
    i, e := strconv.Atoi(sc.Text())
    if e != nil {
        panic(e)
    }
    return i
}

func bico(n, r int) int {
    if n < r {
        return 0
    }
    if n < 2*r {
        r = n - r
    }

    ret := 1.0
    for i := 1; i <= r; i++ {
        ret *= float64(n - i + 1)
        ret /= float64(i)
    }
    return int(ret)
}

func main() {
    sc = bufio.NewScanner(os.Stdin)
    sc.Split(bufio.ScanWords)
    n, p := nextInt(), nextInt()

    cnt0, cnt1 := 0, 0
    for i := 0; i < n; i++ {
        a := nextInt()
        switch {
        case a%2 == 0:
            cnt0++
        default:
            cnt1++
        }
    }

    ans0 := 0
    ans1 := 0
    for j := 0; j <= cnt0; j++ {
        ans0 += bico(cnt0, j)
    }
    for k := p; k <= cnt1; k += 2 {
        ans1 += bico(cnt1, k)
    }

    fmt.Println(ans0 * ans1)
}

このコードでは、有理数の形で計算結果を持つとオーバーフローしてしまう問題を、逐一除算を行うことで実数の形にして解決しています。

欠点としては整数型でデータを持てないため、誤差が出る危険性があるかもしれません。二項係数の計算アルゴリズムで誤差が出るかどうかはよくわかりませんが…

また、計算量は先の方法と変わらず $O(N^3)$ となります。

パスカルの三角形を使う

package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
)

var sc *bufio.Scanner

func nextInt() int {
    sc.Scan()
    i, e := strconv.Atoi(sc.Text())
    if e != nil {
        panic(e)
    }
    return i
}

func main() {
    sc = bufio.NewScanner(os.Stdin)
    sc.Split(bufio.ScanWords)
    n, p := nextInt(), nextInt()

    cnt0, cnt1 := 0, 0
    for i := 0; i < n; i++ {
        a := nextInt()
        switch {
        case a%2 == 0:
            cnt0++
        default:
            cnt1++
        }
    }

    bico := make([][]int, n+1)
    for i := range bico {
        bicoLine := make([]int, n+1)
        bicoLine[0] = 1
        bicoLine[i] = 1
        bico[i] = bicoLine
    }

    for i := range bico {
        for r := range bico[i] {
            if i >= 1 && r >= 1 && r < i {
                bico[i][r] = bico[i-1][r-1] + bico[i-1][r]
            }
        }
    }

    ans0 := 0
    ans1 := 0
    for j := 0; j <= cnt0; j++ {
        ans0 += bico[cnt0][j]
    }
    for k := p; k <= cnt1; k += 2 {
        ans1 += bico[cnt1][k]
    }

    fmt.Println(ans0 * ans1)
}

パスカルの三角形と呼ばれる関係として、

$\displaystyle \binom{n}{0} = \binom{n}{n} = 1$

$\displaystyle \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$

というものがあります。¹これを用いて予めすべての二項係数を計算しておくことで問題を解くことができます。

（知らないと/調べないと辿り着かないこと以外は）欠点らしい欠点はなく、 $N\leq50$ の制約条件下ではオーバーフローの心配もなく、計算量も $O(N^2)$ で済むのでよい解き方だと思います。

逐一約分する

package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
)

var sc *bufio.Scanner

func nextInt() int {
    sc.Scan()
    i, e := strconv.Atoi(sc.Text())
    if e != nil {
        panic(e)
    }
    return i
}

func gcd(a, b int) int {
    if a < b {
        a, b = b, a
    }
    if a%b == 0 {
        return b
    }
    return gcd(b, a%b)
}

func bico(n, r int) int {
    if n < r {
        return 0
    }
    if r > 0 && n/r < 2 {
        r = n - r
    }
    denom, numer := 1, 1
    for i := 1; i <= r; i++ {
        denom *= n - i + 1
        numer *= i
        div := gcd(denom, numer)
        denom /= div
        numer /= div
    }
    return denom / numer
}

func main() {
    sc = bufio.NewScanner(os.Stdin)
    sc.Split(bufio.ScanWords)
    n, p := nextInt(), nextInt()

    cnt0, cnt1 := 0, 0
    for i := 0; i < n; i++ {
        a := nextInt()
        switch {
        case a%2 == 0:
            cnt0++
        default:
            cnt1++
        }
    }

    ans0 := 0
    ans1 := 0
    for j := 0; j <= cnt0; j++ {
        ans0 += bico(cnt0, j)
    }
    for k := p; k <= cnt1; k += 2 {
        ans1 += bico(cnt1, k)
    }

    fmt.Println(ans0 * ans1)
}

二項係数が最終的に（64bit整数の範囲内の）整数になることを利用して、逐一約分することで有理数の形のまま計算結果を記録する方法です。

誤差の心配がなく、また人力で計算する手順に近いため非常に直感的な解法だと思います。~~ごり押しとも言いますね。~~

ただし最小公倍数を毎回求める必要があるため、計算量としては $O(N^3\log N)$ になると思います。

雑記

想定解法が $O(1)$ なのですべてが霞みます。

$\binom{n}{k} = _nC_k$ （二項係数）↩

2019-05-22

AtCoder ABC 126 F - XOR Matching (Go)

競プロ AtCoder ABC126 F問題 600点 Go

irisruneです。2本立てはタイトルも本文もごちゃごちゃするので1記事に1本がよさそうですね。

atcoder.jp

適当に試行すれば解法が出てくると聞いたのでやってみたらACできました。~~しかし出力時点でミスしてWAを積み重ねました。~~

package main

import (
    "fmt"
    "math"
    "strings"
)

func main() {
    var m, k int
    fmt.Scan(&m, &k)
    n := int(math.Pow(2.0, float64(m)))
    if n == 2 && k == 1 {
        fmt.Println(-1)
        return
    }
    if n <= k {
        fmt.Println(-1)
        return
    }

    ans := make([]int, 0)
    for i := 0; i < n; i++ {
        if i == k && k != 0 {
            continue
        }
        ans = append(ans, i)
    }
    if k != 0 {
        ans = append(ans, k)
    }

    for i := n - 1; i >= 0; i-- {
        if i == k && k != 0 {
            continue
        }
        ans = append(ans, i)
    }
    if k != 0 {
        ans = append(ans, k)
    }

    str := fmt.Sprintf("%v", ans)
    str = strings.Trim(str, "[]")
    fmt.Println(str)
}