自分用メモ

プログラミングとかのメモを書きたいです

競プロ典型 90 問:079 - Two by Two(★3)

問題

atcoder.jp

挑戦結果

  • 挑戦日:2021/11/01
  • 結果:解けた
  • 時間:10分

考えたこと

  • 一番右下1箇所だけ更新してよいのか?を迷った。
    • そうだとすると、どんな場合もBに一致できそうだし、例とその答えとも一致しなくなるので、あくまで4箇所更新が必須という前提かと思った。
  • Aの左上から順番、Bに寄せていく作業をやってみて、その回数をカウントすれば良さそう
  • 最後までやってみて、Bに一致すればその回数が最短手数になるし、Bに一致しなければ不可能パターン(その場合は右下がずれる)。
  • 例えば下記のようなことを繰り返す感じ。
    •  A _ {1,1} B _{1,1}に寄せる。(その際、 A _ {1,2}, A _ {2,1}, A _ {2,2} も更新)
    •  A _ {2,1} B _{2,1}に寄せる。(その際、 A _ {2,2}, A _ {3,1}, A _ {3,2} も更新)
    • ・・・

公式解説

https://twitter.com/e869120/status/1410007233262276612/photo/1

解説を読んだふりかえり

  • キーワード:操作順序によらない

ソース

H,W= [int(x) for x in input().split()]
A,B = [],[]

for _ in range(H):
    a = [int(x) for x in input().split()]
    A.append(a)

for _ in range(H):
    b = [int(x) for x in input().split()]
    B.append(b)


cnt = 0
# 左上から合わせていく。一致できない場合は右下が一致しない。
for w in range(W-1):
    for h in range(H-1):
        diff = B[h][w] - A[h][w]
        A[h][w] += diff
        A[h+1][w] += diff
        A[h][w+1] += diff
        A[h+1][w+1] += diff
        cnt += abs(diff)

if A==B:
    print('Yes')
    print(cnt)
else:
    print('No')

競プロ典型 90 問:078 - Easy Graph Problem(★2)

問題

atcoder.jp

挑戦結果

  • 挑戦日:2021/11/01
  • 結果:解けた
  • 時間:10分

考えたこと

  • グラフをマトリックスで持つと、1頂点について確認するのにグラフをナメないと行けないのでTLEするのかなと思った。
  • グラフを集合もってもナメないとダメなので、優先度付きキューで持てばlogで抑えられそうかなと思った。
  • そんなことを考えていたけど、翌々考えたらノード番号より小さい方だけをカウントすれば良いだけと気がついた。
  • カウントしてみて、1の数をカウントすればOK。
    • pythonのfilter関数を使って見たけど、count関数のほうがシンプルだった

公式解説

https://twitter.com/e869120/status/1409644684561944579

解説を読んだふりかえり

  • ★2ということもあって、グラフの基本を知ろうというのがテーマだったらしい。
  • この問題については隣接グラフはMLEで、隣接リスト形式を使おうというのがテーマだったらしい。作成者の意図に反した解法になっているのかも。

ソース

N,M = [int(x) for x in input().split()]

# Cは自分自身より頂点番号が小さいものの数
C = [0] * (N+1)
for _ in range(M):
    a,b = [int(x) for x in input().split()]
    # aを小さい方とする
    a,b = min(a,b), max(a,b)
    # b(大きい方)
    C[b] += 1

# 1の数を数える
print(C.count(1))

問題

atcoder.jp

挑戦結果

  • 挑戦日:2021/10/31
  • 結果:解けた
  • 時間:15分

考えたこと

  • 1周して戻るときは、modをとって計算
  • しゃくとり法の感じで、現在が求めたい面積より多いときは縮める、少ないときは伸ばすをしていき、見つかるかどうかを行えば良い

公式解説

https://twitter.com/e869120/status/1408599656209080322

解説を読んだふりかえり

  • 模範解法は円環を列にして二倍しておき、累積和をとっておき、開始位置を1~N-1とした上で、二分探索で求めたい面積があるかを調べるだった。
  • しゃくとり法のほうが実装もしやすいような気はした。

ソース

N = int(input())
A = [int(x) for x in input().split()]

# トータルの大きさ
all = sum(A)

# 現在の大きさ(先頭0、末尾0)
cur = A[0]
s,e = 0,0
ans = "No"
# 開始位置は一周しない。終了位置-開始位置で長さチェック
while s<N and e-s<N:
    # 十分の一が見つかったら終了
    if cur * 10 == all:
        ans = 'Yes'
        break
    # 小さいときは、末尾を拡大する
    elif cur * 10 < all:
        e += 1
        cur += A[e%N]
    # 大きいときは、先頭を縮める
    elif cur * 10 > all:
        cur -= A[s]
        s += 1

print(ans)

競プロ典型 90 問:075 - Magic For Balls(★3)

問題

atcoder.jp

挑戦結果

  • 挑戦日:2021/10/31
  • 結果:解けた
  • 時間:5分

考えたこと

  • まずは素因数分解する。いちばん効率が良いのは、 ab = x a, bを一番効率よく分割するのは、 a bの素因数の数が同じになるようにすること。
  • 素因数分解はいぜんにライブラリ化してある
  • 最も効率よく分割すると、素因数の数を Kとして、 log_{2} (K) を切り上げた回数になる。
  • スルッと解けてよかったけど、少数計算の誤差は不安かも。きにせず投げたらAC。

公式解説

https://twitter.com/e869120/status/1408195203538690048

解説を読んだふりかえり

  • 答えは[2 ^ {x} >= K]を満たす最小の xとのこと。logだと小数の誤差が不安だから、整数計算のほうが良いと思った。

ソース

from math import ceil, log2
N = int(input())

# 素因数分解
# prime_decomposition(24)     # --> [2, 2, 2, 3]
def prime_decomposition(n):
    i = 2
    table = []
    while i * i <= n:
        while n % i == 0:
            n //= i
            table.append(i)
        i += 1
    if n > 1:
        table.append(n)
    return table

L = prime_decomposition(N)
ans = ceil(log2(len(L)))

print(ans)

WSL2のGUIアプリ

Windows10でこのURLに書いてあるようなことをやった。

astherier.com

WSLg というのもやってみたかったけど、Insider PreviewやWin11を使うのもまだ早いと思ってやめておいた。

  • Xサーバをインストール
    • VcXsrv
    • 設定として、Display numberを明示的に0にすること、「-ac -nowgl」をつけたほうが良いとのこと。あとWSLはパブリックネットワーク扱い。
  • WSLの方の環境変数設定(DISPLAY)

WSL2のIPアドレス

WSLのIPアドレス

WSLのIPアドレスの確認方法

(1)WSL内から確認:ごちゃごちゃしてる

ip addr

(2)WSL内から確認:こっちのほうがシンプル

hostname -I

(3)Windows側から確認:(2)と結局同じ

wsl hostname -I

Windows側でipconfigとかを見ても分からない

(1)WSL側でIPアドレスを確認する

$ hostname -I
172.31.255.189 172.17.0.1

(2)WSL側のdockerでWeb系を動かす

docker run -p 80:8080 -it tomcat-war-demo:1

(3)Windowsのブラウザからアクセスする

http://172.31.255.189:80/demo/

図にすると下記の感じ f:id:ebinafactory:20211030164700p:plain

WSL2のUbuntuでDocker環境を動かす

やったこと

  • Windows10のWSL2でdockerを使えるようにした
  • 参考にしたサイトの手順をやっただけ

参考にした手順

zenn.dev

メモ

  • 公式サイトの手順にたいして次の設定追加をしている感じ。
    • wsl起動時にdocker daemonが起動する用にする(.bashrc で service docker status を実行して、dockerを起動してなければ起動する。そのさい sudoersでパスワードが不要なように設定しておく必要がある)
    • DockerDesktopが自動設定した CredentialStoreを戻す。