競プロ典型90問：003 - Longest Circular Road（★4）
問題
https://atcoder.jp/contests/typical90/tasks/typical90_c
挑戦結果
- 解けなかった
考えたこと
- ワーシャルフロイドで全ノード間の距離を求めて、その最長の距離に+1すれば良いと思った。
- コード書いたけどTLEした。$N3$では無理だった。
- グラフの直径を求めれば良いことがわかった。ググったところアルゴリズムは理解した。
- ただ、上手に実装できなくてTLEした。
木の直径を求めるアルゴリズム
- 任意の頂点から最長の頂点uを探索
- 頂点uから最長の頂点vを探索
- uとvを結ぶパスが最長
解説を読んだふりかえり
- グラフをマトリックスで持ったことで計算量が上がっているようだった。
ソース
from collections import deque N = int(input()) INF = float('inf') # グラフ G = [[] * (N+1) for _ in range(N+1)] for _ in range(N-1): a, b = [int(x) for x in input().split()] G[a].append(b) G[b].append(a) # stからの距離を配列で返す def getdist(st): visited = {st} dist = [INF] * (N+1) dist[st] = 0 Q = deque([st]) while len(Q)>0: node = Q.popleft() for nextnode in G[node]: if nextnode in visited: continue dist[nextnode] = min(dist[nextnode], dist[node]+1) visited.add(nextnode) Q.append(nextnode) return dist ## グラフの直径を求める # 任意の場所stから各ノードへの最短距離を求める st1 = 1 dist1 = getdist(st1) # stからの距離が最大なノード(idx)を求める d = idx = 0 for i in range(2,N+1): if d<dist1[i]: d=dist1[i] idx = i # idxから各ノードへの最短距離を求める dist2 = getdist(idx) # 各最短距離の中で、最大の値がグラフの直径。 今回の問題は直径+1が答え。 print(max(dist2[1:]) + 1)
競プロ典型90問：002 - Encyclopedia of Parentheses（★3）
問題
https://atcoder.jp/contests/typical90/tasks/typical90_b
挑戦結果
- 解けた
- 時間：20分ぐらい
考えたこと
- すべて列挙なのでループして求める
- N文字なら、開カッコがN/2個、閉カッコがN/2個
- 閉じカッコが先行する場合がNG
- (と)の全順番を$2N$パターン作成してチェックするのもアリかと思ったけど、再帰的にOKパターンだけ作れそうな気がした
- 方針
- 左から確定していき全パターンを保持。(と)の数を持ちつつ、末尾に追加していく。
振り返り
- とりあえず解けたのは良かった。
- 解説は「ステップ1：bit全探索」＋「ステップ2：'(' - ')(の累積計算」だった。自分はステップ2を思いついていなかった。
- 解説を読んだあとにbit全探索版でもやってみたら、TLEになった。
- pypy3 なら通った
コード
# インプット N = int(input()) # n：残りの長さ # op:( の数 # cl:) の数 # L：現時点でリストアップしているカッコ文字列のリスト # 戻り値：カッコ文字列のリスト def f(n, op, cl, L): # 残りが0文字なら、Lを返す if n==0: return L ret = [] # カッコが開いてるときは、閉じカッコを末尾に追加可能 if op > cl: L1 = [s+')' for s in L] ret += f(n-1, op, cl+1, L1) # 開きカッコを使い切ってなければ、開くカッコを末尾に追加可能 if op < N//2: L2 = [s+'(' for s in L] ret += f(n-1, op+1,cl, L2) return ret # Nが奇数のときはNG ans = [] if N%2==0: # 初期値は長さNの文字列が欲しい、開きカッコも閉じカッコも0、既存リストは空文字。 ans = f(N, 0, 0, [""]) # ソート ans.sort() # 結果の出力 for a in ans: print(a)
ソース(解説読んだあとにBit全探索版で書き直し)
# インプット N = int(input()) # i番目のビットが立っているか BIT_LENGTH = N def isOne(bit_pat, i): return (bit_pat & 1 << (BIT_LENGTH - 1 - i)) > 0 # 結果用 ret = [] # bit全探索で全パターン列挙 for bit_ptn in range(1<<N): # 開きカッコを+1、閉じカッコを-1でカウント kakko_cnt = 0 # カウントがマイナスになったらNGになる isOK = True # カッコの開きと閉じをカウント for i in range(N): if isOne(bit_ptn, i): kakko_cnt += 1 else: kakko_cnt -= 1 # 一時的にでもマイナスになったらNG if kakko_cnt < 0: isOK = False # 開きカッコと閉じカッコの数が同数ならOK if isOK and kakko_cnt==0: # bitから文字列に変換 s = "" for i in range(N): if isOne(bit_ptn, i): s += "(" else: s += ")" ret.append(s) # ソートして出力 ret.sort() for s in ret: print(s)
競プロ典型90問：001 - Yokan Party（★4）
問題
https://atcoder.jp/contests/typical90/tasks/typical90_a
挑戦結果
- 解けなかった
- 時間：30分ぐらい
考えたこと
- 苦手なDPと思ってずっと考えていたけど、あきらめた。
- 解説を見たら「答えで二分探索」の問題だった
解説を読んだあとのふりかえり
- 長さM以上のピースに分割できるかの関数を作った。けっこうハマって時間がかかった。
- 作成した関数をforで回して結果を確認。この戻り値がTrue→Falseになる瞬間を二分探索でもとめればOKであることを確認。
- 二分探索を作成。これはスムーズにできた。
ソース
# Keyword：答えで二分探索 # インプット N, L = [int(x) for x in input().split()] K = int(input()) A = [int(x) for x in input().split()] # 計算用に先頭と末尾に加えておく A = [0] + A + [L] # 長さM以上のピースに分割できるか？ def check(M): l = cnt = 0 for i in range(N+1): l += (A[i+1] - A[i]) if l>=M: l=0 cnt +=1 # return cnt > K or (cnt == K and l>=M) return cnt > K #### デバッグ・確認用 # 二分探索をせずに各スコアのの実現可否の列挙 # Trueである最も大きい値がこの問題の答え。 # for i in range(1,L): # print(f"{i}, {check(i)}") # 二分探索。lはTrue、rはFalseを想定。 def binarysearch(l,r): # 終了条件 if l+1 == r: return l # lとrの中間のTrue/Falseで範囲を狭くする m = (l + r) //2 if check(m): return binarysearch(m, r) else: return binarysearch(l, m) # 二分探索で求める print(binarysearch(1, L))
ラズパイにUSBのHDDをつなげる
背景
USBのHDDを購入した。NTTのPR-500MIのUSBポートにつないで簡易NASにしようと思ったのに、つないでもどうも使えない。 PR-500MIにはUSBポートもあるし、Web画面にはUSBストレージ機器についてのメニューもあるのに、簡易NAS的な使い方はできないらしい。。。
- NTTのPR-500MI（終端装置）を使っているのですが、U... - Yahoo!知恵袋
- 最初に見つけた知恵袋コメント。だめっぽいことが書いてある。
- https://www.ntt-west.co.jp/kiki/download/flets/pr500mi/
- 公式ページ。一番下の「その他」にUSBポートが使えない記載がある。
騙された設定画面
USBのHDDの自動マウント
このサイトを参考にさせてもらった。 kowaza.blue
参考サイトと一点違うかなというのは、自分はMacも持っているので、NTFSよりexfatのほうが便利かと思ってHDDをexfatでフォーマットしている。設定内容もそれにあわせてexfatにした。
SakuraVPSのCentOS7でDockerのインストール
とりあえず、dockerの依存性を見てみる。
$ yum deplist docker 読み込んだプラグイン:fastestmirror, langpacks Loading mirror speeds from cached hostfile * base: www.ftp.ne.jp * epel: mirror.dmmlabs.jp * extras: www.ftp.ne.jp * updates: www.ftp.ne.jp パッケージ : docker.x86_64 2:1.13.1-53.git774336d.el7.centos 依存性 : /bin/sh provider: bash.x86_64 4.2.46-29.el7_4 依存性 : docker-client = 2:1.13.1-53.git774336d.el7.centos provider: docker-client.x86_64 2:1.13.1-53.git774336d.el7.centos 依存性 : docker-common = 2:1.13.1-53.git774336d.el7.centos provider: docker-common.x86_64 2:1.13.1-53.git774336d.el7.centos 依存性 : libassuan.so.0()(64bit) provider: libassuan.x86_64 2.1.0-3.el7 依存性 : libaudit.so.1()(64bit) provider: audit-libs.x86_64 2.7.6-3.el7 依存性 : libc.so.6(GLIBC_2.17)(64bit) provider: glibc.x86_64 2.17-196.el7_4.2 依存性 : libdevmapper.so.1.02()(64bit) provider: device-mapper-libs.x86_64 7:1.02.140-8.el7 依存性 : libdevmapper.so.1.02(Base)(64bit) provider: device-mapper-libs.x86_64 7:1.02.140-8.el7 依存性 : libdevmapper.so.1.02(DM_1_02_97)(64bit) provider: device-mapper-libs.x86_64 7:1.02.140-8.el7 依存性 : libdl.so.2()(64bit) provider: glibc.x86_64 2.17-196.el7_4.2 依存性 : libgpg-error.so.0()(64bit) provider: libgpg-error.x86_64 1.12-3.el7 依存性 : libgpgme.so.11()(64bit) provider: gpgme.x86_64 1.3.2-5.el7 依存性 : libgpgme.so.11(GPGME_1.0)(64bit) provider: gpgme.x86_64 1.3.2-5.el7 依存性 : libgpgme.so.11(GPGME_1.1)(64bit) provider: gpgme.x86_64 1.3.2-5.el7 依存性 : libpthread.so.0()(64bit) provider: glibc.x86_64 2.17-196.el7_4.2 依存性 : libpthread.so.0(GLIBC_2.2.5)(64bit) provider: glibc.x86_64 2.17-196.el7_4.2 依存性 : libpthread.so.0(GLIBC_2.3.2)(64bit) provider: glibc.x86_64 2.17-196.el7_4.2 依存性 : libseccomp.so.2()(64bit) provider: libseccomp.x86_64 2.3.1-3.el7 依存性 : libsystemd.so.0()(64bit) provider: systemd-libs.x86_64 219-42.el7_4.10 依存性 : libsystemd.so.0(LIBSYSTEMD_209)(64bit) provider: systemd-libs.x86_64 219-42.el7_4.10 依存性 : rtld(GNU_HASH) provider: glibc.x86_64 2.17-196.el7_4.2 provider: glibc.i686 2.17-196.el7_4.2 依存性 : systemd provider: systemd.x86_64 219-42.el7_4.10
特に気にせずインストール
Dockerの公式サイトに手順が載っているけど、無視してコマンド一発で済ませる。 Get Docker CE for CentOS | Docker Documentation docker-ceとdocker-eeの内容の違いは不明。(コミュニティーエディションとエンタープライズエディションらしい)
sudo yum install docker docker --version → Docker version 1.13.1, build 87f2fab/1.13.1
バージョン1.13は結構古いみたいだけど、気にしないことにする。
起動と自動起動
sudo systemctl start docker sudo systemctl enable docker → Created symlink from /etc/systemd/system/multi-user.target.wants/docker.service to /usr/lib/systemd/system/docker.service.
Dockerの起動(ただしrootで)
docker run ubuntu:14.04 /bin/echo 'Hello world' → /usr/bin/docker-current: Got permission denied while trying to connect to the Docker daemon socket at unix:///var/run/docker.sock: Post http://%2Fvar%2Frun%2Fdocker.sock/v1.26/containers/create: dial unix /var/run/docker.sock: connect: permission denied. See '/usr/bin/docker-current run --help'.
権限のエラーが出てしまった。とりあえずrootで再実行。
sudo docker run ubuntu:14.04 /bin/echo 'Hello world' → Unable to find image 'ubuntu:14.04' locally Trying to pull repository docker.io/library/ubuntu ... 14.04: Pulling from docker.io/library/ubuntu 324d088ce065: Pull complete 2ab951b6c615: Pull complete 9b01635313e2: Pull complete 04510b914a6c: Pull complete 83ab617df7b4: Pull complete Digest: sha256:b8855dc848e2622653ab557d1ce2f4c34218a9380cceaa51ced85c5f3c8eb201 Status: Downloaded newer image for docker.io/ubuntu:14.04 Hello world
とりあえず動いた。
ユーザをdockerrootグループに追加
下記の話はあるみたいだが、とりあえずユーザをdockerグループに追加してみる。 qiita.com
ただし、dockerrootグループになっているようだった。
cat /etc/group root:x:0: bin:x:1: ： 略 ： dockerroot:x:991:
# グループに追加 sudo gpasswd -a username dockerroot # 再実行(結局ダメだった) docker run ubuntu:14.04 /bin/echo 'Hello world' → /usr/bin/docker-current: Got permission denied while trying to connect to the Docker daemon socket at unix:///var/run/docker.sock: Post http://%2Fvar%2Frun%2Fdocker.sock/v1.26/containers/create: dial unix /var/run/docker.sock: connect: permission denied. See '/usr/bin/docker-current run --help'.
下記の話らしい。 qiita.com
ls -l /var/run/docker.sock → srw-rw---- 1 root root 0 5月 15 22:36 /var/run/docker.sock sudo chown root:dockerroot /var/run/docker.sock
再度、一般ユーザで実行
docker run ubuntu:14.04 /bin/echo 'Hello world' → /usr/bin/docker-current: Got permission denied while trying to connect to the Docker daemon socket at unix:///var/run/docker.sock: Post http://%2Fvar%2Frun%2Fdocker.sock/v1.26/containers/create: dial unix /var/run/docker.sock: connect: permission denied. See '/usr/bin/docker-current run --help'.
同じエラーだった。なぜだろう・・・。 とりあえず、/var/run/docker.sockはdocker再起動後にはroot:rootに戻ってしまうことと、root:dockerrootになっていてもダメみたいだ。
qiita.com こんな記事を見つけたので、試してみたけど、結果は変わらずだった・・・。
sudo groupadd docker sudo gpasswd -a username docker sudo systemctl restart docker
できないと思ったけど、記事の末尾に書いてあるとおり、ログインし直したらdockerコマンドが使えるようになった！！
ついでに、docker-composeもインストールした。
sudo yum install docker-compose
SAKURAのVPSで設定したこと
前提
- SAKURA用意されたCentOS7を使用
# 全体的なアップデート yum clean all yum update reboot
SELinux
無効化するつもりだったけど、最初から無効化されていた
確認
getenforce → Disabled
一時的な無効化
setenforce 0 getenforce
永続的な無効化
# vi /etc/selinux/config SELINUX=disabled
FW
有効になっていたので、そのまま有効にする
systemctl status firewalld → Active: active (running)
ホスト名の変更
リブート後に有効になる。
hostnamectl set-hostname skr01 reboot
localeの確認と変更
# 確認
localectl status
System Locale: LANG=C
VC Keymap: jp106
X11 Layout: jp
# 設定可能なロケールの一覧
localectl list-locales | grep ja
ja_JP
ja_JP.eucjp
ja_JP.ujis
ja_JP.utf8
japanese
japanese.euc
# 変更
localectl set-locale LANG=ja_JP.utf8
# 変更後の確認
localectl status
System Locale: LANG=ja_JP.utf8
VC Keymap: jp106
X11 Layout: jp
# source /etc/locale.conf で良いらしいけど、リブート
reboot
自動起動が有効になっているもののチェック
[root@skr01 ~]# systemctl list-unit-files -t service | grep enabled abrt-ccpp.service enabled abrt-oops.service enabled abrt-vmcore.service enabled abrt-xorg.service enabled abrtd.service enabled atd.service enabled auditd.service enabled autovt@.service enabled chronyd.service enabled crond.service enabled dbus-org.fedoraproject.FirewallD1.service enabled dbus-org.freedesktop.NetworkManager.service enabled dbus-org.freedesktop.nm-dispatcher.service enabled dmraid-activation.service enabled fail2ban.service enabled firewalld.service enabled getty@.service enabled irqbalance.service enabled libstoragemgmt.service enabled lvm2-monitor.service enabled mdmonitor.service enabled NetworkManager-dispatcher.service enabled NetworkManager.service enabled postfix.service enabled rngd.service enabled rsyslog.service enabled smartd.service enabled sshd.service enabled sysstat.service enabled systemd-readahead-collect.service enabled systemd-readahead-drop.service enabled systemd-readahead-replay.service enabled tuned.service enabled
不要サービスの停止
# 不要サービス(postfix)の停止と自動起動の停止 systemctl stop postfix.service systemctl disable postfix.service → Removed symlink /etc/systemd/system/multi-user.target.wants/postfix.service.
# 結局、その後、再度可動させた。(Centos7ではrootにメールが来るらしい？ので念の為) systemctl enable postfix.service Created symlink from /etc/systemd/system/multi-user.target.wants/postfix.service to /usr/lib/systemd/system/postfix.service. systemctl start postfix.service
一般ユーザを作成
useradd -G wheel hoge passwd hoge
SSHのrootログインの無効化
PermitRootLogin no systemctl restart sshd
ログの表示
journalctl -u sshd.service
SSHのポート変更とfirewalld
vi /etc/ssh/sshd_config # ポート番号を20022にする(デフォルトは22) Port 20022 # SSH2だけにする Protocol 2 # rootでのログインを不可とする PermitRootLogin no # パスワードでのログインを許可する PasswordAuthentication yes # パスワードなしでのログインを不可とする PermitEmptyPasswords no # hoge というユーザだけログインを許可する AllowUsers hoge #＃ 再起動 systemctl restart sshd
# 空いているサービスの確認 firewall-cmd --list-services → dhcpv6-client ssh # 空いているポートの確認 firewall-cmd --list-ports → なし。 # ポート20022を開ける(一時的な有効化) firewall-cmd --add-port=20022/tcp → success # ポート20022を開ける(永続的な有効化) firewall-cmd --permanent --add-port=20022/tcp → success # もともと有ったsshサービス(ポート22)を消す firewall-cmd --permanent --remove-service=ssh → success # firewalldを再起動 systemctl restart firewalld.service # 空いているサービスの確認(sshが消えた) firewall-cmd --list-services → dhcpv6-client # 空いているポートの確認(ssh用の20022が空いた) firewall-cmd --list-ports → 20022/tcp
SSHの接続を証明書に変更
# この作業はSSHでつなぎに行く一般ユーザでやる # RSA＆2048bitでも大丈夫っぽい。 ssh-keygen -t rsa -b 4096 # 移動 cd ~/.ssh # 公開鍵を追記する cat id_rsa.pub >> authorized_keys # authorized_keys が 644 ではダメらしい。700に変更。なお変更しないと後術のエラーになる。 chmod 700 authorized_keys
メモ * ~/.ssh/にファイルが生成される * id_rsa * 秘密鍵(SSHクライアントに入れる) * パーミッションは600になっていた * id_rsa.pub * 公開鍵(サーバ側のauthorized_keysに追記する) * パーミッションは644になっていた
# 出力されるテキスト Generating public/private rsa key pair. Enter file in which to save the key (/home/hoge/.ssh/id_rsa): Created directory '/home/hoge/.ssh'. Enter passphrase (empty for no passphrase): パスワードを入れる Enter same passphrase again: パスワードを入れる Your identification has been saved in /home/hoge/.ssh/id_rsa. Your public key has been saved in /home/hoge/.ssh/id_rsa.pub. The key fingerprint is: SHA256:hCK6wwxOcEU/ePWkVPUEHW1hQa1VOyIyOk+dIjxjvcc hoge@servername The key's randomart image is: +---[RSA 4096]----+ | .o o.o.oo+B*| | . o + + oo *| |. o o = oo.. ..* | |.o . o.oo + o o .| |o. OS+ o | |*. . B + | |o+ o E | | . . | | | +----[SHA256]-----+
メモ：入力したパスワードは、SSHクライアント側で秘密鍵を使用する際に入力することになる。
ハマったこと
秘密鍵/公開鍵でSSH接続するときのauthorized_keysのパーミッション
# エラーログ journalctl -u sshd.service | tail → 5月 03 18:52:05 skr01 sshd[3600]: Authentication refused: bad ownership or modes for file /home/hoge/.ssh/authorized_keys
