【AtCoder】ABC204 感想戦

2021/6/6に開催されたABC204を振り返ります。
結果はA~Cの3完でした。
順位：3449位、パフォーマンス：778、レート：742→746(茶)

• A問題：A - Rock-paper-scissors
  じゃんけんであいこを出す問題です。
  あいこになるパターンは2つあって、全て同じ手か、全て違う手である。
  よって、XとYが同じなら同じ手を、XとYが違うなら残りの手を出力すれば良い。

def main():
    X, Y = map(int,input().split())

    if X == Y:
        return X
    else:
        return 3 - X - Y

print(main())

• B問題：B - Nuts
  木に実が実っていて、実の数が10個以下なら収穫せず、10個以上なら10個を残して残りの全てを収穫する。
  これは単純にそれぞれ木毎に10個以上であれば余剰分を答えに足していけばよい。

def main():
    N = int(input())
    A = list(map(int, input().split()))
    ans = 0

    for a in A:
        if a > 10:
            ans += a - 10
    
    return ans

print(main())

• C問題：C - Tour
  C問題でグラフっぽい問題が出ましたね。
  BFSで解いている人が多かったですが、私はDFSで解きました。
  この問題、最初の2行は再帰回数の上限を増やすおまじないですが、これを書き忘れて2回ほどREを出してしまい、やらかしました。
  解法としては、各地点スタートにした時のゴールとしてあり得る地点をDFSでみていきました。
  初めて本番でDFSが自力で解けました。
  成長を実感しました。

import sys
sys.setrecursionlimit(1000000)

N, M = map(int,input().split())
g = [[] for _ in range(N+1)]
ans = 0

def dfs(v):
    if visited[v]:
        return
    
    visited[v] = True
    global ans
    ans += 1
    for nv in g[v]:
        dfs(nv)

for _ in range(M):
    A, B = map(int,input().split())
    A -= 1
    B -= 1
    g[A].append(B)

for i in range(N):
    visited = [False] * (N+1)
    dfs(i)

print(ans)

• D問題：D - Cooking
  オーブンを使うスケジュールを最適化する問題です。
  問題を見た時、解けそう！と興奮しましたが、結局解けませんでした。
  Dにしてはチャンス問題だったのでは、と思います。
  方針としては、Tの総和の半分より大きい数字かつ最小の数値をTの部分集合で作る、です。
  以下のようにDPで解けます。

import math
def main():
    N = int(input())
    T = list(map(int, input().split()))
    S = sum(T)

    # Tの部分集合を用いてS/2より大きい数値かつ最小のものを作る。
    # dp[i]: Tの部分集合を用いて合計iを作れるか。
    dp = [False] * (S+1)
    dp[0] = True

    for t in T:
        for i in range(S, t-1, -1):
            # tを見ている場合、i-tが作れるならばiも作れる。
            dp[i] |= dp[i-t]
    
    ans = math.ceil(S/2)

    # Tの総和の半分から一つずつインクリメントしていき、作れる数がでてきたらそれが答えになる。
    while dp[ans] == False:
        ans += 1
    
    return ans

print(main())

• まとめ
  今回はCで凡ミスでREを2回喰らい、レートは現状維持でした。
  D解きたかった...
  とはいえCのDFSを自力で解けたのは嬉しかったです。
  6月中に入緑を目指して頑張りたいと思います。
  お疲れ様でした。

【AtCoder】ABC203 感想戦

2021/5/30に開催されたABC203を振り返ります。
結果はA~Cの3完でした。
順位：1997位、パフォーマンス：1087、レート：694→742(茶)

• A問題：A - Chinchirorin
  3つサイコロを振って、2つが同じときは残りの1つのサイコロの目を、同じものがないときは0を出力する問題です。
  スマートな解き方があるかと思い、少し考えましたが結局全パターンチェックに落ち着きました。

def main():
    a, b, c = map(int,input().split())

    if a == b:
        return c
    elif a == c:
        return b
    elif b == c:
        return a
    else:
        return 0

print(main())

• B問題：B - AtCoder Condominium
  マンションの部屋番号の総和を求める問題です。
  このマンションはN階建てで、各階K室の部屋があり、i階のj号室の部屋番号はi0jで表されます。
  部屋番号はi * 100 + jで求められるので、部屋毎に足していけば良いです。

def main():
    N, K = map(int,input().split())
    ans = 0

    for n in range(1,N+1):
        for k in range(1, K+1):
            room = n * 100 + k
            ans += room
    
    return ans

print(main())

• C問題：C - Friends and Travel costs
  10¹⁰⁰ + 1個の村があり、村i → 村i+1に移動するのに1円かかります。
  友達がいる村にたどり着いた場合、その友達からお金をもらうことができます。
  この条件でどこの村までたどり着けるか求める問題です。
  方針としては、友達がいる一番近い村までたどり着けるかどうか検証しながら所持金を管理してどこまで進めるかを調べました。

def main():
    N, K = map(int,input().split())
    AB = [list(map(int, input().split())) for _ in range(N)]
    AB.sort()
    mura = 0

    for a, b in AB:
        dist = a - mura
        if dist > K:
            return mura + K
        else:
            mura += dist
            K += b - dist
    
    return mura + K

print(main())

• D問題：D - Pond
  制約条件的に二分探索かな？と頭によぎりましたが、全く手が動きませんでした。
  この問題は2次元配列での累積和を求めるやり方を学びました。
  こういうテクニックは知らないと使えないですね。
  やっぱりまだDの壁は厚いな〜と実感しました。

def main():
    N, K = map(int,input().split())
    A = [list(map(int, input().split())) for _ in range(N)]
    S = [[0]*801 for _ in range(801)]

    ng = 0
    ok = 10**9 + 1

    lim = int(K*K/2 + 1)

    # 二分探索
    while ng+1 < ok:
        mid = (ng+ok) // 2

        # 2次元配列の累積和を求めておく。
        for i in range(N):
            for j in range(N):
                S[i+1][j+1] = S[i+1][j] + S[i][j+1] - S[i][j]

                if A[i][j] > mid:
                    S[i+1][j+1] += 1

        ext = False
        for i in range(N-K+1):
            for j in range(N-K+1):
                if S[i+K][j+K] + S[i][j] - S[i][j+K] - S[i+K][j] < lim:
                    ext = True
        
        if ext: ok = mid
        else: ng = mid
    
    return ok

print(main())

• まとめ
  今回はC問題を早解きできたこともあり、レートが結構上がりました。
  Cの難易度によってレートが不安定になるので、早くD問題を解けるようになりたいです。
  6月中に入緑を目指して頑張りたいと思います。
  お疲れ様でした。

【AtCoder】ABC202 感想戦

2021/5/22に開催されたABC202を振り返ります。
結果はA~Cの3完でした。 順位：3205位、パフォーマンス：819、レート：679→694(茶)
今回はCまではスラスラ解けてこの順位なので、Cが簡単だったみたいです。

• A問題： A - Three Dice
  3つのサイコロのでた目に関する問題です。
  出た目と反対側の目の値を足すと7になることを利用して、21からa+b+cを引けば答えになります。

def main():
    A, B, C = map(int,input().split())
    return 21 - (A+B+C)

print(main())

• B問題：B - 180°
  0, 1, 6, 8, 9からなる文字列(S)を180度回転させた文字列を出力する問題です。
  回転させた際、6を9に、9を6に、それ以外はそのまま、に変換します。
  私はまずSを逆順に並び替え、その後6→9, 9→6に変換しました。
  単純にreplaceなどで変換しようとすると、6→9に変換した後、9→6にする際にまた戻ってしまうため、少し注意が必要です。
  今回の制約条件的に先頭から1文字ずつ見ていっても間に合いますし、6→Q、9→6、Q→9など違う文字を経由してreplaceするか、どちらでもよいかと思います。 私は前者で実装しました。

def main():
    S = input()
    S = list(S[::-1])

    for i in range(len(S)):
        if S[i] == "6":
            S[i] = "9"
        elif S[i] == "9":
            S[i] = "6"
    
    return "".join(S)

print(main())

• C問題：C - Made Up
  3つのリスト(A, B, C)が与えられ、条件を満たす整数(i, j)が何通りあるか、という問題です。
  制約条件的に1重のイテレーションで解きたいです。
  私はCをイテレーションしました。
  CからBの要素を特定し、その要素がAに何個あるかを求める、を繰り返します。
  TLE対策として、予めcollectionsライブラリのCounterメソッドを利用してAの各要素数を求めておきます。

from collections import Counter
def main():
    N = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    C = list(map(int, input().split()))
    ans = 0
    cnt = Counter(A)

    for c in C:
        b = B[c-1]
        ans += cnt.get(b, 0)
    
    return ans

print(main())

• D問題：D - aab aba baa
  A個の"a"、B個の"b"からなる文字列において、辞書順でK番目のものを求める問題です。
  まず、文字列のパターン数はA+B個の中からA個を選べばよいので、(A+B)CAで求められます。
  方針としては、先頭の文字から順番に確定させていきます。
  先頭を"a"としたとき、残りの文字列のパターン数がK以上の場合、先頭の文字は"a"、小さい場合は"b"を選ぶ、を繰り返します。
  イテレーション毎に累積をとっておくことも忘れないようにしましょう。

def calc_combinations_count(n, r):
    import math
    if n < r:return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def main():
    A, B, K = map(int,input().split())
    acm = 0
    ans = []

    # 先頭の文字から順番に決めていく。
    for _ in range(A+B):
        # aが無ければ自動的にbを選ぶ。
        if not A:
            ans.append("b")
        else:
            # 先頭の文字をaと過程し、先頭以降の文字列の総数を計算する。
            cnt = calc_combinations_count(A+B-1, A-1)
            
            if acm + cnt >= K:
                A -= 1
                ans.append("a")
            # どのパターンでもまだK番目にならないため、先頭文字としてbを選ぶ。
            else:
                acm += cnt
                B -= 1
                ans.append("b")
    
    return "".join(ans)

print(main())

• まとめ
  今回は解ける問題を着実に解いた、という印象です。
  D問題は復習すれば納得ですが、なかなか本番で解くのは難しいです。
  とりあえずレートの最高値を更新できたのでよかったです。
  緑色を目指して来週も取り組んでいきます。
  お疲れ様でした。

【AtCoder】ABC201 感想戦

2021/5/15の開催されたABC201を振り返ります。
結果はA~Cの3完でした。C問題に手こずってしまいました。
順位：4241位、パフォーマンス：619、レート：686→679(茶)

• A問題：A - Tiny Arithmetic Sequence
  数列を並び替えて等差数列にできるかどうかを判断する問題です。
  まずソートして、要素間の差を比較すればよいです。

A = list(map(int, input().split()))
A.sort()

if (A[1]-A[0]) == (A[2]-A[1]):
    print("Yes")
else:
    print("No")

• B問題：B - Do you know the second highest mountain?
  与えられた入力から2番目に高い山を出力する問題です。
  同じ高さの山はありません。
  これはkeyを指定してソートする方法を知っていれば簡単です。

N = int(input())

ST = []
for _ in range(N):
    S, T = input().split()
    T = int(T)
    ST.append([S, T])

ST.sort(key=lambda x: x[1], reverse=True)

print(ST[1][0])

• C問題：C - Secret Number
  絶対使った数字、使ったかもしれない数字、絶対使ってない数字の情報からあり得る4桁の暗証番号が何通りあるか求める問題です。
  数学的に解こうとして手間取ってしまいましたが、素直に10000通り全探索すればよかったんですね。

S = input()
ans = 0
for v in range(10000):
    v = str(v).zfill(4)
    res = 1
    for i, x in  enumerate(S):
        # 絶対に使っている数字なのに、暗証番号にない場合
        if x == "o" and str(i) not in v:
            res = 0
        
        # 絶対に使ってないのに、暗証番号にある場合
        elif x == "x" and str(i) in v:
            res = 0
            
    ans += res

print(ans)

• D問題：D - Game in Momotetsu World
  動的計画法で解こうと思いたちましたが、どう定義するかわかりませんでした。
  dp[i][j]: コマが(i, j)にあるときの「高橋得点 - 青木得点」の最適値
  ゴールから逆算して処理していくのがポイントです。

H, W = map(int, input().split())
A = [input() for _ in range(H)]

dp = [[0]*W for _ in range(H)]

for i in reversed(range(H)):
    for j in reversed(range(W)):
        if i == H-1 and j == W-1:
            continue
        
        dp[i][j] = - float("inf")

        if i+1 < H:
            score = 1 if A[i+1][j] == "+" else -1
            dp[i][j] = max(dp[i][j], -dp[i+1][j] + score)

        if j+1 < W:
            score = 1 if A[i][j+1] == '+' else -1
            dp[i][j] = max(dp[i][j], -dp[i][j+1] + score)

if dp[0][0] == 0: print("Draw")
if dp[0][0] > 0: print("Takahashi")
if dp[0][0] < 0: print("Aoki") 

• まとめ
  CでWAを連発してしまい、順位が奮いませんでした。
  気を取り直して次回も頑張りたいと思います。
  お疲れ様でした。

【名探偵コナン】緋色の弾丸レビュー・前編

子供の頃からコナンオタクで、4/16に公開された「名探偵コナン 緋色の弾丸」を初日と5/4に鑑賞してきました。
感想や考察を徒然なるままに書きます。
※ 以下ネタバレを含みますのでご注意ください。

• 全体感
  正直、う〜ん…でしたね。
  歴代でみても下から数えた方が早いと思いました。
  要因としては、後ほど掘り下げますが
  • 赤井さんが空気
  • ミステリー皆無
  • 1年おあずけによる期待値の高騰
  • クライマックスの不完全燃焼

等が挙げられるかなと思います。
勿論良かった点も沢山あるので、簡単に時系列に沿って考察していきます。

• プロローグ

  • 15年前、アメリカの回想シーン
    ハーモニカの演奏をバックにオシャレな始まり方ですごくワクワクしていました。
    コナン映画の始まりとして「から紅の恋歌」や「純黒の悪夢」のように、ド頭にクライマックスのようなド派手なアクションを取り入れるか、しっとりと映画の軸となる事件の導入から入るか、の2パターンますが、今回は後者でした。
    頭のアクションに尺を使うと後のストーリーが薄くなる印象があるので、今回の始まり方は好きでした。

  • パーティー
    まずゲスト声優の浜辺美波さん、声聞いた瞬間にわかりましたが、とても上手かったと思います。
    歴代ゲスト声優の中で1番上手かったのではないでしょうか。
    リニアのチケットが抽選と発表された時、光彦が「鈴木財閥がWSGのスポンサーだから園子に頼めばいい」と発言。 少年探偵団、ずる賢くなってしまいましたね。
    「ベイカーストリートの亡霊」の頃は子供ながら知恵を出し、自分たちのヤイバーカードと交換してコクーンの体験バッチを手に入れていました。 あの頃の純粋な少年探偵団に戻って欲しいものです。
    このパーティー編に関しては、コメディあり、小事件ありで映画の始まりとしてはいい感じだったのではと思います。
    久々に元太のうな重好き設定も出てきましたし、哀ちゃんのセルフ乾杯もかわいかったです。
    余談ですが、2回目見た時に気づいたのですが、鈴木史郎さんが発見された時に落ちていた制服、サイズがXLで犯人の体格が示されてたんですね。 完全に見落としてました。

• オープニング
  素直にかっこよかったです。
  これも2回目見た時に気づいたのですが、このオープニング、赤井さんが撃った弾丸視点だったんですね。
  トンネルの中を進み、リニア車内を通り、最後にコナン登場の流れだったので恐らく間違いないかと思います。
  小技が効いてますね。

• 序盤

  • 博士クイズ
    今年のクイズ、なんかしっくりきませんでした。
    Q : 世界初の「真空超電導リニア」に既に乗っているのは誰？
    1.弁護士, 2.医師, 3.宣教師
    A : 宣教師は伝道師と言い換えることができ、真空超電導リニアの「電動」と「伝道」をかけている3.宣教師が答え。
    言い換えて言葉が掛かっていることはわかるのですが、それがリニアに既に乗っていることになるのか、釈然としませんでした。
    有識者の方おられましたら教えて下さい。
    あと、気になったのは園子は父親を発見してくれた少年探偵団に感謝を込めてチケットを元から譲る気でクイズ勝負をしていましたが、蘭は何も言わずしれっとチケットをゲットしています。
    結果的にチケットもらうにしても、ちょっとくらい園子を気遣う描写があってもよいのでは？と思いました。

  • 小五郎のおっちゃんの味噌汁こぼし
    蘭がリニアに乗ることを聞いて、おっちゃんが絶句し味噌汁をこぼすシーン。
    違和感ポイントその１です。
    蘭が依頼者と同じリニアに乗るからと言って、あの小五郎のおっちゃんがあんな腑抜けたリアクションするでしょうか。
    まだ驚いて茶碗ひっくり返す方が有り得そうです。
    おっちゃんの上裸を見せたかったのかわかりませんが、このシーンは不要、残してももっと短くて良いと感じました。

  • 蘭と新一の電話 今回唯一のラブコメシーンでした。
    特にコメントはありませんが、まぁ短い尺で一応差し込んだ、という印象ですね。

  • 空港・クエンチ 今回、コナン映画おなじみの爆発に代わる新しい試みとしてクエンチ、これはチャレンジングでした。
    クエンチとは液体ヘリウムが急激に気化し放出される現象で、クエンチによって酸素濃度が下げられることで窒息してしまいます。
    今回のリニアの仕組みも自然に絡んでいて、かつ謎で不気味な感じもあり、コナンが知らず灰原に教えてもらう展開も新鮮でよかったと思います。
    爆発に一工夫加えたこのチャレンジ、とても良かったと思いました。
    あと、少し場面は戻りますが、空港で蘭がコナンと哀ちゃんに帰れるか訪ねたシーン、まんまと笑いました。
    この辺の笑いのツボはしっかり押さえてますね。

徒然なるままに書いていたら思いの外分量が多くなってしまったので、記事分けたいと思います。
次回は中盤、今作の見どころ赤井家ファミリージークンドーバトルがありますね。

お疲れ様でした。

【Angular】トラブルシューティング：Can't bind to 'ngIf' since it isn't a known property of 'div'

Angularというフレームワークを用いてWebアプリフロントエンド開発をしているのですが、題名のエラーに遭遇し地味にハマったので、私が犯したミスを共有致します。
だれかのお役に立てば幸いです。

さてこのエラー、まずは脳死でググります。
するとありがたいことに複数ヒットします。

qiita.com

stackoverflow.com

ざっくり内容としては、「CommonModuleがインポートされていない」、「Observable周辺が原因」と書いてあるのですが、私の場合には当てはまりませんでした。

途方に暮れ30分程度さまよいましたが、解決しました。
私の場合の原因は、新規作成したcomponentをapp.module.tsでimportしていない、という凡ミスでした。

このエラーに遭遇した方、まずはapp.module.tsのimportを確認してみましょう。

お疲れ様でした。

【Udemy】アルゴリズム・データ構造入門 ソート #3.3

ソート	Average	Best	Worst	安定	備考
radix	O(n)	O(n)	O(n)	Yes	countソートの改良
quick	O(n log n)	O(n log n)	O(n2)	No	データの比較と交換回数が非常に少ないのが特徴で、ランダムに散らばっているデータに対して、最も効率良く並べ替えを実行
merge	O(n log n)	O(n log n)	O(n log n)	Yes	整列されていないリストを2つのリストに分割して、それぞれを整列させた後、それらをマージして整列済みのひとつのリストを作成
tim	O(n log n)	O(n)	O(n log n)	Yes	insertionソートとmergeソートを使用

• radixソート

from typing import List

def counting_sort(numbers: List[int], place: int) -> List[int]:
    counts = [0] * 10
    result = [0] * len(numbers)

    for num in numbers:
        index = int(num / place) % 10
        counts[index] += 1

    for i in range(1, 10):
        counts[i] += counts[i-1]

    i = len(numbers) - 1
    while i >= 0:
        index = int(numbers[i]/place) % 10
        result[counts[index]-1] = numbers[i]
        counts[index] -= 1
        i -= 1

    return result


def radix_sort(numbers: List[int]) -> List[int]:
    max_num = max(numbers)
    place = 1
    while max_num > place:
        numbers = counting_sort(numbers, place)
        place *= 10
    return numbers

• quickソート

from typing import List

def partition(numbers: List[int], low: int, high: int) -> int:
    i = low - 1
    pivot = numbers[high]
    for j in range(low, high):
        if numbers[j] <= pivot:
            i += 1
            numbers[i], numbers[j] = numbers[j], numbers[i]
    numbers[i+1], numbers[high] = numbers[high], numbers[i+1]
    return i+1


def quick_sort(numbers: List[int]) -> List[int]:
    def _quick_sort(numbers: List[int], low: int, high: int) -> None:
        if low < high:
            partition_index = partition(numbers, low, high)
            _quick_sort(numbers, low, partition_index-1)
            _quick_sort(numbers, partition_index+1, high)

    _quick_sort(numbers, 0, len(numbers)-1)
    return numbers

• mergeソート

from typing import List

def merge_sort(numbers: List[int]) -> List[int]:
    if len(numbers) <= 1:
        return numbers

    center = len(numbers) // 2
    left = numbers[:center]
    right = numbers[center:]

    merge_sort(left)
    merge_sort(right)

    i = j = k = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            numbers[k] = left[i]
            i += 1
        else:
            numbers[k] = right[j]
            j += 1
        k += 1

    while i < len(left):
        numbers[k] = left[i]
        i += 1
        k += 1

    while j < len(right):
        numbers[k] = right[j]
        j += 1
        k += 1

    return numbers

• timソート

def merge_sort(data: list, l: int, m: int, r: int) -> list:
    len_left, len_right = m - l + 1, r - m
    left, right = [], []
    for i in range(0, len_left):
        left.append(data[l + i])
    for i in range(0, len_right):
        right.append(data[m + 1 + i])

    i, j, k = 0, 0, l
    while i < len_left and j < len_right:
        if left[i] <= right[j]:
            data[k] = left[i]
            i += 1
        else:
            data[k] = right[j]
            j += 1
        k += 1

    while i < len_left:
        data[k] = left[i]
        k += 1
        i += 1

    while j < len_right:
        data[k] = right[j]
        k += 1
        j += 1

    return data


def insertion_sort(data: list, left: int, right: int) -> list:
    for i in range(left + 1, right + 1):
        temp = data[i]
        j = i - 1
        while j >= left and data[j] > temp:
            data[j + 1] = data[j]
            j -= 1

        data[j + 1] = temp
    return data


def tim_sort(data: list, size: int = 32) -> list:
    n = len(data)
    for i in range(0, n, size):
        insertion_sort(data, i, min((i + 31), (n - 1)))

    while size < n:
        for left in range(0, n, 2 * size):
            mid = left + size - 1
            right = min((left + 2 * size - 1), (n - 1))
            merge_sort(data, left, mid, right)
        size = 2 * size
    return data

ソートの紹介は以上になります。
お疲れ様でした。