競プロ典型 90 問:079 - Two by Two(★3)
問題
挑戦結果
- 挑戦日:2021/11/01
- 結果:解けた
- 時間:10分
考えたこと
- 一番右下1箇所だけ更新してよいのか?を迷った。
- そうだとすると、どんな場合もBに一致できそうだし、例とその答えとも一致しなくなるので、あくまで4箇所更新が必須という前提かと思った。
- Aの左上から順番、Bに寄せていく作業をやってみて、その回数をカウントすれば良さそう
- 最後までやってみて、Bに一致すればその回数が最短手数になるし、Bに一致しなければ不可能パターン(その場合は右下がずれる)。
- 例えば下記のようなことを繰り返す感じ。
- をに寄せる。(その際、 も更新)
- をに寄せる。(その際、 も更新)
- ・・・
公式解説
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)
問題
挑戦結果
- 挑戦日: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))
■
問題
挑戦結果
- 挑戦日: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)
問題
挑戦結果
- 挑戦日:2021/10/31
- 結果:解けた
- 時間:5分
考えたこと
- まずは素因数分解する。いちばん効率が良いのは、 の を一番効率よく分割するのは、との素因数の数が同じになるようにすること。
- 素因数分解はいぜんにライブラリ化してある
- 最も効率よく分割すると、素因数の数をとして、 を切り上げた回数になる。
- スルッと解けてよかったけど、少数計算の誤差は不安かも。きにせず投げたらAC。
公式解説
https://twitter.com/e869120/status/1408195203538690048
解説を読んだふりかえり
- 答えは[2 ^ {x} >= K]を満たす最小のとのこと。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アプリ
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/
図にすると下記の感じ