JTF2020参加レポート

はじめに

• JTF2020に参加させていただいたときのメモです。

JTF(July Tech Festa)とは

• インフラエンジニアのための祭典
• 今年のテーマは「Extend Your Engineering Life!」

メモ

凡例
☆: ToDo（追加で調べておくことなど）
⚫️: 重要（転用）ポイント

Kubernetes、第一歩のその後に ~基盤を支えるOSSとの関わり方~@太田 航平 (inductor)

• チュートリアルから先に進めていない人向け
• k8sの構成
• それらがどうやって開発しているか
• DockerはdotCloud社が公開したLXCベースのアプリケーションが始まり
• k8sはインフラを抽象化。統一されたインターフェイス。「どのホストに〜」ではなく「メモリ2G欲しい」
• k8sの3つの顔⚫️
  • コンテナオーケストレーション
    • コンテナをデプロイ
  • 分散システム
    • ノードをクラスタリング
    • 柔軟なジョブスケジューリング
    • 分散KVSが鍵
  • Platform for Platform
    • 新しい時代のLinuxカーネル
    • 基盤のための基盤
    • 拡張を前提に作られたAPIやリソース
• CNCF
  • Linux FoundationとGoogleが設立
  • Kubernetes以外にも
  • コンテナ技術単体ではない
  • ベンダーの偏っているプロジェクトは受け入れない
• SIGs
  • あらゆる決定はSIGによって行われる
  • SIGごとにチェア（代表）がいる
    • api-serverの標準化
    • テスト自動化の推進
    • ドキュメント化
• k8sそのものがコンポーネントにわかれたマイクロサービス
• k8sの構成⚫️
  • クラスター
    • クラスターを構成するコンポーネントをリソースと呼ぶ
    • リソースはAPIオブジェクトで、プログラム上で管理
    • 1台以上のノードの集合と捉えることもできる
    • ノードは物理または仮装マシンと非常に近い
      • VMがあって、その上で必要なプロセスが動いている
      • コントロールプレーンとワーカー
        • コントロールプレーン
          • 司令塔、管理用ノード。元master
          • etcdは外に出すことが多い
  • （補足）kube キューベ
  • kube-api-server
    • 全てがここを通る
    • etcdに触れる唯一の存在
    • kubectl
  • contoroller Manager
    • APIに定期的に問い合わせて、マニュフェストとの差分をチェック
    • cloud contoroller manager
      • クラウドの世界とKubernetesをつなげてくれるコンポーネント
      • こいつのおかげでオートスケールとかGCPのロードバランサーが使えたり
  • kube-schedurler
    • cronとかとは違う
    • 新しいPodが作られたときに、どこに配置するかを決定
  • kubelet
    • ノードに1台いて、まず、ノードがいるよ、と伝える
    • 命令を受けたら、コンテナ作成司令をコンテナランタイムに送信
  • kube-proxy
    • 「どのノードでも同じように動いて欲しい」=「ネットワークを透過的に」
    • iptables
  • コンテナランタイム
    • Docker以外も
    • kubeletのCRI（インターフェイス）が喋れるならいける
• どこで開発されているか
  • kubeで始まるものは大元のリポジトリ
  • それ以外は個別のSIG（cloud contoroller managerとか）
  • etcdは別
• 公式のチュートリアルがある
• 認定資格がある
• kubernetes the hard way⚫️
• k8sの基本構造はWebアプリケーションと同じ
• 自動化の恩恵をフルに活用するためには両方の知見が必要
• Don’t ask to ask
• Land Scape, Trail Map
• KEPで議論されている
• 世界で二番目に大きなコミュニティ⚫️
  • 1番はLinuxカーネル
• Docs以外で面白そうなSIG
• kube proxyがBGP?
  • CNIがBGPを使うことがある
• workerがdata planeに？名称を統一。今は動いていない。
• ☆構成全体像の図
  • https://kubernetes.io/docs/concepts/overview/components/
• ☆k8s記事への反映（k8s構成の説明）

AKSを活用した内製教育支援プラットフォームをリリースした話@河原 慎吾

• 経歴
  • オンプレLinuxやラッキング
  • VMware…
• テクノベーションセンター 　 * 全員が専任（他社では兼任があるある？）
  • ブランド向上、全社の技術スキル向上
• 内製教育のメリット
  • 実業務で発生した疑問をすぐに聞ける。いざ必要になった時に。
    • 勉強会は、現場と研究組織の接点⚫️
  • 講師は現場の状況を把握することができる
• 勉強会（イベント）の当初の課題
  • 申し込んだのを忘れるとか申請とか
• 開発の前にデザインシステム
  • ☆表
    • （参考）https://dojo.codebot.io/news/about-dev-process-20161031/
  • ペルソナ設計大事⚫️
    • インタビューの分析結果から、共通点を抽出し人物像を当てていく
  • カスタマージャーニーマップの作成⚫️
  • プロトタイプの作成⚫️
    • Prott
  • モックアップの段階でユーザテスト
  • デザインプロセスは時間がかかる
  • ペルソナやマップをアウトプットすることで後で立ち返れることがメリット⚫️
• なぜAKS使ったか
  • Web App for Containerでもよかった
  • 運用してみないと、k8sの良さや苦労が分からない。⚫️
• Azure ARM Template
  • コード化にこだわりすぎない。初期セットアップを楽にする、くらい⚫️
  • もし壊れても一から作り直せる安心感
  • パスワードは、実行するときに指定
  • 公式にクイックスタートテンプレートがある⚫️
  • 頻繁に変更が入るのはマニュフェストファイルの方。こっちはあんまり。
• 本番と検証でクラスタを分けている
  • k8sのアップデートの検証⚫️
  • ステージングは監視していない、開発環境と同居
  • 結局、開発とステージングは同ノードでnamespaceを分けて構築した⚫️
• Nginx Ingress
  • 社内からのみアクセスするように元IPを制御
• Let's Encrypt⚫️
  • Helm Install
• Helm⚫️
  • yumに近い
  • cart-managerを入れたり
  • upgrade
• アップデート⚫️
  • k8sはとにかく早い
• HPA
  • Podの使用状況に応じて
• ヘルスチェック
  • Podの再起動
  • Podへの通信を止める
  • 色々パラメータがある。ヘルスチェック開始までの時間とか
• Azure Monitorで監視
  • コンテナーが落ちても自己復旧だが、クラスタ自身は監視
  • Slackに通知
  • -> 細かくログを見るときはkubectl logs, describe⚫️
• コンテナレジストリ
  • 脆弱性スキャン⚫️
• CI/CD⚫️
  • drone
  • developブランチ→開発環境に
  • master->ステージング環境に
  • タグ→本番環境に
  • secretはWebUIから事前設定
  • コミットハッシュ値をタグに
  • デプロイはkubectl applyとかを書いていく
  • latestを使いたくない
    • 動的に変更したい
  • リリース後に不具合があった場合に、即座にリストアできるかどうかが大事
  • CI/CDはリストア駆動で設計する。劇的に生産性が上がるため、早めに作った方が良い。⚫️
• logはAzureに転送。ESとかは使っていない。Azureのlog analitics。

人のチームでどうやって開発者をkubernetes開発に巻き込もうとしているか@大平 譲

• Terraform Cloud, argocdでGitops⚫️
• 人数が少ないチームこそ自動化
• 連絡のフローを飛ばして、開発者にマニュフェストを書いて反映をしてもらっている
• マイクロサービス
  • コンテナが増えていったときにどうするか。保守作業
  • -> 開発チームの一人にインフラ構築を任せた
• uberとかはmicroではなくmacroくらい

Prowに学ぶKubernetesのCI環境@bells17

• k8sリポジトリへのPRに対してbotが自動でラベル付与
• chat ops
• Githubと親和性が高い
• prow自体がk8s上で動作する
• 嬉しいこと
  • ジョブの実行機能
  • Issue/PRの管理。リポジトリのライフサイクル
• アーキテクチャ
  • GithubからのHookを受けて、ProwのHookコンポーネントが受ける→各種リポジトリに設定されたプラグインを実行
  • ユニットテストを実行したり
  • だいたいPresubmit
• GitLabは未対応
• GitHubのbotアカウントが必要
• アクセス制限はoauth-proxyとかで⚫️
  • 認証機能のないアプリケーションでOAuth2認証を提供する
  • OAuth2 Proxy は、リバースプロキシサーバーのように動作

Kubernetesを用いた車両用クラスタ管理とvehicle service mesh@Yong Jun Kai / @天地 知也(tomoyamachi)

• 車向けの注意点
  • linuxと限らない
  • NWの切断
• Misaki
  • k8sベース
  • 組み込みを学ぶ必要がない
  • NW瞬断問題に対応
  • まだプロトタイプ
• ECU
• 仕組み
  • Cloudにmasterがいて、車にnode
  • VPNで接続
  • 車のスペックによって載せるコンテナ（機能）は変える
• Helmでデプロイを管理
• サービスメッシュとは
  • ネットワークレイヤの管理
  • ロードバランシング、デプロイ、ポリシーコントロール、モニタリング、TLS接続の管理
  • Istioなどが有名
  • 各コンテナにproxyを置く+コントロールプレーンを介してやりとりする
  • ☆サービスメッシュのメリットの図
  • ccc = cross cutting concerns
  • サービス開発者が、ネットワークを考慮しなくていい
  • configはproxyのコードに入れれば良い
• control planeとdata plane
• ローカルのDNSマスク

”ワタシハ セフ チョットデキル" への道

• Ceph
• マジイケ頭足類
• SPOFなし
• オブジェクトストレージもファイルシステムもブロックデバイスも
  • NFSも
• 勝手にリバランスしたりスクラブしたり。運用負担を減らしてくれる。
• APIが色々
• 専用ハードは必要なし
• ☆かっこいい公式動画がある
• 歴史
  • 2003年（S3は2006年）
  • 原理的な部分は当初から洗練されている
• だいたい1年に1回のメジャーリリース
  • ライフサイクルは2年
• アーキテクチャ
  • RADOS（れいどす）
    • ベースとなる仕組み
    • データのアルゴリズムはCRUSHアルゴリズム
      • 誰でも計算できる=単一障害点をなくす
    • MON/MGR/OSD
    • MON
      • クラスターの状態を監視
      • クラスターマップを作成/更新/配布
      • クライアントも、このマップを利用すれば、直接OSDアクセスが可能
    • MGR
      • MONとセットで動く
      • 外部へ監視情報を提供したりする。ダッシュボードの機能も提供する
    • OSD
      • データの出し入れをする
      • OSDは互いに死活監視している。異常があればMONに報告する。
• CRUSHアルゴリズムとは
  • オブジェクトをどのOSDに配置するか決定するアルゴリズム
  • メタデータを中央集約するサーバが不要⚫️
  • Pool=オブジェクトを保存するための論理的な領域
  • Erasure RAID5/6 パリティ 速度はかかる。レプリカの方が早い
• CRUSH Map & Rule
  • 物理配置トポロジーを定義
  • フロアを分けるとかラックを分けるとか
  • 物理配置を考慮してデータを配置してくれるように
  • poolごとに設定。poolAはhostレベルの分散でいい、rackレベルの分散でいい、roomレベルの分散までする、など
• Placement Group
  • clientは、どのPGにデータを預けるかだけ
  • weightを考慮（人が計算するわけではない）
• librados
  • 各種言語向け
• rados gateway
  • S3互換
• RBD
  • ブロックデバイス
• ファイルシステムのメタデータはMDSが管理
• NFS Exportも可能
• MDS
  • CephFSのメタデータ管理のデーモン（メモリ上で管理）
• コンテナ仮してコンテナオーケストレーション基盤上で管理しやすい
  • Rook
• 分散システムなので、速いネットワークは正義

ツイートしたこと

kubernetes the hard way
Kubernetesクラスタを立ち上げるための必要な各タスクを確実に理解するための、長い道のり
https://springmt.github.io/kubernetes-the-hard-way-ja/kubernetes_the_hard_way/#0
#JTF2020 #JTF2020D

CI/CDはリストア駆動で設計する。劇的に生産性が上がるため、早めに作った方が良い。
Droneを利用。latestタグを使わないために動的に変更するようゴニョゴニョ工夫。
#JTF2020 #JTF2020D

直近業務で活かしたいこと

• CI/CD
  • Ansibleと、k8s(マニュフェスト)それぞれ
  • 定期的にAnsible実行してデグレチェック
  • GitOpsも検討
• k8sの環境設計
  • NameSpaceを分けるかどうか
  • 検証用の環境
• Helmの活用検討
• デザインシステムの導入
  • ペルソナ設計、カスタマージャーニーマップ作成、ユーザヒアリング
• アップデート対応の準備
  • k8s
    • k8sはとにかく早い（masterもworkerも）
  • Docker
  • ドライバ
  • cuda
• ジョブの並列実行対応
  • ガイドラインの整備
• 障害時切り分けの手順整備
  • kubectl logs, describe
• コンテナレジストリで脆弱性スキャンを実施

Kubernetesについて調べたことメモ

はじめに

• Kubernetesまわりについて復習したときのメモ

参考

• コンテナ・ベース・オーケストレーション
• しくみがわかるKubernetes
• ネットワークまわりを確認&勉強しながら、Kubernetesの環境構築をしてみた

メモ

Docker全般

• コンテナとは
  • ホストOS上に論理的な区画（コンテナ）を作って、一つのサーバのようにしたもの
• コンテナの利点
  • アプリケーションのポータビリティ
  • 軽量で高速に動作する
    • サーバ仮想サーバと比較してオーバーヘッドが少ない
• その他
  • プロキシ配下で使うとき
    • /etc/systemd/system/docker.service.d 配下にconfファイルを作成してフラッシュ & Dockerデーモン再起動

Kubernetes全般

• オーケストレーション
  • マルチホストで構成されたクラスタでコンテナを運用するのに必要になってくる
    • 起動停止、ホスト間のネットワーク接続、ストレージ管理、どのホストで稼働させるかなどのスケジューリング機能、監視
  • クラスタを構成するノードとリソースの管理
  • アプリケーションのスケジューリング
• Docker Compose
  • 複数のDockerコンテナをサービスとして定義/実行するための、コマンドラインツール
    • 複数コンテナ/イメージの同時構築・同時実行・ログ表示
  • -> しかし、コンテナの常時監視する機能がない、複数のクラスタにデプロイできない
  • -> Swarmが生まれた
• Kubernetes
  • コンテナに対応したアプリケーションクラスタ環境上へ自動的にデプロイするためのオープンソースのフレームワーク
  • Kubernetesが目指すところ
    • システム構築のための手作業を減らす
    • システムをセルフサービスで運用する
  • エコシステム
    • パッケージ管理: Helm(apt-get的な)
    • モニタリング: Prometheus
    • ログコレクタ: Fluentd
    • 分散KVS: etcd
    • コンテナランタイム: containerd
    • サービスメッシュ: Istio
  • 「宣言的設定」と「APIセントリック」が特徴
    • リソースのあるべき状態定義による宣言的アーキテクチャと、リソースの変更監視をトリガーとしたイベントドリブンアーキテクチャを組み合わせることで、疎結合でスケーラブルなクラスタ管理システムを実現している
  • 分散システム
    • 分散システムの設計と運用は、例外処理との戦い
  • kubectl
    • Kubernetesクラスタの状態を確認したり、構成を変更したりするためのもの
    • 認証
      • ~/.kube/configに書かれている情報をもとにクラスタへ接続する
      • 接続先のサーバ情報や認証情報
    • kubectl コマンド タイプ 名前 フラグ
      • リソース: Kubernetesでは、コンテナアプリケーションであれネットワークであれジョブの実行であれ、全てリソースという抽象化した概念で管理する
      • 名前: リソースには識別するための固有の名前がついている

Kubernetesのサーバ構成

• ハードウェア構成
  • クラスタを構成するマシンはMasterとNodeの二種類
  • Masterは奇数台。（etcdの特性に起因）

Kubernetesクラスタへのデプロイの仕組み

• ① Masterに対してデプロイすべきコンテナのイメージや個数などの情報を指示する
  • Masterが提供するAPIサーバーに対してRESTでリクエストを送信（通常はラップしたkubectl）
• ② Masterは指示された構成情報をetcdに永続化する
• ③ Masterは情報に基づいて、コンテナをデプロイすべきNodeを決定する
  • MasterのSchedulerが、コンテナなどのリソースをどのNodeにデプロイするかを決定する
• ④ MasterはNodeに対してコンテナの実行を指示する
  • NodeのKubeletがMasterと通信
• ⑤ Nodeは必要に応じて指定されたコンテナイメージをpullしたうえで実行する
  • MasterのContoroller Manager
    • 指定したコンテナが、指定した個数だけ稼働しているかチェックしてくれる
    • リソースの変更を監視しており、変更を検知すると必要なコントローラを実行してくれる

Kubernetesのコンポーネント

• Master
  • API Server
    • リソース情報を管理するためのフロントエンドのREST API
    • 各コンポーネントからリソースの情報を受け取りデータストア（etcd）上に格納する
    • API Serverへのアクセスは基本的にkubectl
  • Scheduler
    • PodをどのNodeで動かすかを制御する（Podの配置先の割り当て）
  • Controller Manager
    • クラスタの状態を監視し、あるべき状態を維持する
    • 定義ファイルで指定したものと実際のNodeやコンテナで動作している状態をまとめて管理する
  • データストア（etcd）
    • どのようなPodをどう配置されるかなどの情報を持ち、API Serverから参照される
    • マニュフェストの内容が保存される
• Node
  • kubelet
    • エージェント
    • Podの定義ファイルに従ってコンテナを実行したりストレージをマウントしたり
    • • Nodeのステータスを定期的に監視、API Serverに通知する
  • kube-proxy
    • 様々な中継、変換を行うネットワークプロキシ

Kubernetesのリソース

アプリケーションの実行

• Pod
  • Kubernetesではコンテナを素の状態でデプロイしない
  • 一個以上のコンテナを包含する「Pod」という単位でデプロイする
  • 「1コンテナ:1プロセス」を守りつつ複数プロセスを協調動作させるための仕組みがPod
  • Pod内の全コンテナが同一のNodeにデプロイされることが保証される
  • Pod内の複数のコンテナで仮想NIC（プライベートIP）を共有する
  • localhostでコンテナ間が通信できる
• ReplicaSet
  • Deploymentとの使い分けに注意
  • オートヒーリングの機能を実現するためのリソース
  • Podを直接デプロイすることもできるが、Podに障害があっても自動回復しない
  • -> ReplicaSetは、稼働しているPodの数がreplicasと一致しているかどうかをチェックする
  • = クラスタ内で指定された数のPodを起動しておく仕組み
  • クラスタ内にPodをいくつ起動しておくかの値をレプリカ数と呼ぶ
  • もしPodが一つ異常終了したら、すぐに新しい別のPodを一つ起動する
  • Podのヘルスチェック
    • HTTP GetやExec（指定されたコマンドを実行し、ステータスコードが0であることを確認）
• Deployment
  • 単純なアプリケーションのデプロイは、Pod・ReplicaSet・Serviceでいい。
  • -> Podを一つずつ更新していく、ローリングアップデートやロールバックを宣言的に行う仕組み
  • -> Deploymentを利用する場合は、ReplicaSetを明示的に作成せず、Deploymentによって自動的に生成されたものを利用するようになります
  • ReplicaSetの履歴を持つことで、ローリングアップデート・ロールバックを可能にする
  • Deployment作成コマンド
    • kubectl create -f nginx-deployment.yaml --record
• DaemonSet
  • ReplicaSetは、どのマシンに配置されるが分からないが、どのノードにも配置したいPodがある
  • ログコレクタなど
  • 実はkube-proxyもこのDaemonSetを利用して動いている

ネットワークの管理

• Service
  • ネットワークを管理する仕組み
  • PodにアサインされるIPはランダムに割り当てられる
  • -> Serviceはあるサービスの入り口となり、複数のPodで構成されるサービスを代表する
  • いくつか種類がある
    • LoadBalancer
      • Serviceに対応するIPアドレス+ポート番号にアクセスすると、複数のPodに対するL4レベルの負荷分散が行われる
  • Cluster IP と External IP
    • Cluster IP: クラスタ内のPod同士で通信するためのプライベートIP。
    • External IP: クラスタの外部に公開するIP。環境変数として参照できる。
  • External Service
    • RDBに接続するなど、PodからKubernetes外のサービスにアクセスするための仕組み
    • 外部サービスをクラスタ内のサービスと同様に扱うことができる
• Ingress
  • L7の機能を提供

アプリケーション設定情報の管理

• ConfigMap
  • 環境依存情報をコンテナイメージに含めてしまうと、環境ごとにコンテナイメージをビルドし直すことになり、ポータビリティが損なわれてしまう
  • -> 環境情報はConfigMapに分離しておく
  • ボリュームとしてマウント、環境変数やPod定義のパラメータとして参照する
• Secret
  • 特殊なConfigMap
  • バイナリデータを格納（Base64エンコード）
  • データはメモリ上に展開される（ディスクに書き込まれない）
  • 暗号化された状態でetcdに書き込まれる

バッチジョブの管理

• Job/CronJob
  • Podは停止=異常終了だが、JobまたはCronJobは停止=ジョブの終了
  • ReplicaSetのバッチジョブ対応版
  • なぜJobを使うのか
    • Node障害時に別のNodeで実行
    • プロセス異常終了時の再起動
      • 処理が成功するまで、JobコントローラがPodを作り直す
    • タイムアウト
    • 実行回数と並列度

その他のリソース

• ボリューム系
  • emptyDir
    • Podと同じライフサイクル
    • Podの消滅時に削除される
    • -> 同一Pod内の複数コンテナ間でのファイル共有のために利用される
  • 外部ストレージ
    • NFSやAWS EBSなど
    • Podの定義の中で、ボリュームの定義 -> コンテナのvolumesMountsの定義から参照し、コンテナ内のマウントパスを指定、もできる
    • -> が、Pod定義が環境依存になるので、PersistentVolumeを使う
  • PersistentVolume
    • 外部ストレージを、Podから見て抽象化
    • 利用フロー
      • インフラ担当がNFSなどを用意
      • -> クラスタ担当がPVとしてKubernetesに登録
      • -> アプリケーション提供者がPVCを作成
      • -> KubernetesがPVCの条件に合致するPVがあればPVCとPVをバインドする
    • -> が、クラスタ管理者がPVを事前に準備しておく必要があるので、ダイナミックプロビジョニングを使う

Kubernetesの運用

拡張性

• HorizontalPodAutoscaler（HPA）
  • 指定したメトリックをコントローラがチェックし、負荷に応じて必要なPodのレプリカ数になるよう自動でPodを増減する
  • Metric Serverを使ってリソースの使用状況を収集する
  • マニュフェストとしては、kindがHorizontalPodAutoscalerで、scaleTargetRefにスケールするReplicaSetを指定する
  • メトリックの収集は、Nodeで動くkubeletのcAdviserというエージェントで行う
  • メトリックをまとめて管理するのがMetric Server。Podの一つとして動いている。収集したメトリックの情報はメモリ上で管理する。
• ノードのスケール
  • HPAとCluster Autoscalerは共存できる
  • 自動スケールのメトリックとして、外部のメトリックを使ったりもできる
    • メッセージキューを使うことが多い

運用作業

• バージョンは、MasterおよびNodeの両方に気を配る必要がある
• NodeのバージョンがMasterのバージョンより3つ以上古くなると、そのNodeは正しく動作しない場合がある
• サーバのアップデート=OSや導入しているパッケージのアップデートを指す
• unattended-upgradesパッケージを使ったり
• 再起動をどうするかがポイント
  • Cordon/Uncordon/Drain

監視

• Liveness Probe

その他

• アドオンコンポーネントのPodはMasterではなくNodeに配置される
• リソース分離で一番分かりやすいのはクラスタの分離。次に大きいのはNameSpace。
• User Account と Service Account
  • Kubernetesは「人」を管理する仕組みがない
  • 一般ユーザを管理せず、統合管理できる外部のID管理システムにそれを任せている

Kubernetesの設計のポイント

• ラベルのルール
  • 本番/開発環境
  • プロジェクト
  • GPU付き
• リソース分離
  • NameSpace
    • プロジェクト
    • defaultは使わないように？
• NodeSelector
• Resource Requests
  • Podをスケジューリングするときは、実際のノードの使用量をチェックするわけではない
• Limit Range
  • Namespaceで動く一つ一つのPodのリソース上限（総量ではない）
• ResourceQuota
  • 総量を制限
• 監視
  • メトリックバックエンド、ログ収集、ログバックエンド、可視化、アラート、サービス監視（外形監視）、オールインワン

ABC129-D_Lampをpythonで解いた（動的計画法）

問題

• ABC129-D_Lamp

問題概要

任意のマスから光線が上下左右に伸びる（ただし、障害物は透過しない）。 明かりによって照らされるマスの個数を最大値を計算する。

解法

• 障害物のあるグリッドなので、幅優先探索などの方法が考えられるが、上下左右にしか光線は伸びないので、ここはDPで解いていくのが良いと思われる。

方針

• 今回の場合漸化式を解く際に一度にマスの計算をすることは難しい（理由は口頭で）。
  なので今回は以下のテーブルを準備する。 $$$ U[i][j] : \quad 上に何マス照らせるマスがあるか？\ D[i][j] : \quad 下に何マス照らせるマスがあるか？\ R[i][j] : \quad 右に何マス照らせるマスがあるか？\ L[i][j] : \quad 左に何マス照らせるマスがあるか？ $$$ （ただし、$$D[i][j]、R[i][j]$$に関してはループの回す方向に注意する。）

更新式

$$$ U[i][j] = U[i-1][j] + 1\ D[i][j] = D[i+1][j] + 1\ R[i][j] = R[i][j+1] + 1\ L[i][j] = L[i][j-1] + 1 $$$ もし障害物のマスの場合は $$$ U[i][j] = 0\ ... $$$

最後合計のマスを計算する際、重複しているマス数3を引いておく。

コード

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

U = [[0]*W for i in range(H)]
D = [[0]*W for i in range(H)]
R = [[0]*W for i in range(H)]
L = [[0]*W for i in range(H)]

for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            U[i][j] = 0
        elif i == 0 and S[i][j] == '.':
            U[i][j] = 1
        else:
            U[i][j] = U[i-1][j] + 1
            
    for j in range(W):
        if S[i][j] == '#':
            L[i][j] = 0
        elif j == 0 and S[i][j] == '.':
            L[i][j] = 1
        else:
            L[i][j] = L[i][j-1] + 1
            
for i in range(H-1,-1,-1):
    for j in range(W-1,-1,-1):
        if S[i][j] == '#':
            D[i][j] = 0
        elif i == H-1 and S[i][j] == '.':
            D[i][j] = 1
        else:
            D[i][j] = D[i+1][j] + 1
            
    for j in range(W-1,-1,-1):
        if S[i][j] == '#':
            R[i][j] = 0
        elif j == W-1 and S[i][j] == '.':
            R[i][j] = 1
        else:
            R[i][j] = R[i][j+1] + 1
            
ans = 0 

for i in range(H):
    for j in range(W):
        ans = max(ans,U[i][j]+R[i][j]+D[i][j]+L[i][j]-3)        
print(ans)    

written by 友達のtaniponyo

ABC128-D_equeueをpythonで解いた（その他）

問題

• ABC128-equeue

問題概要

宝石が$N$個横一列に並んでいる。
以下の４操作を$K$回まで行う。

• 操作A: 左端の宝石を取る。
• 操作B: 右端の宝石を取る。
• 操作C: 持っている宝石から１個左端に置く。
• 操作D: 持っている宝石から１個右端に置く。

方針

• 全探索すると、$O(4^K)$なので厳しい。
• 操作C、Dは持っている宝石どれを置いてもよいので、先に操作A、Bをしてから操作C,Dをすれば良いのでは？$\rightarrow$実際正解。

解法

• 左から$l$個、右から$r$個取り出し、どの宝石を戻すのかを探る。
• 宝石の価値がマイナスになっているものを戻せばよい（ソートすればわかる）。

コード

N,K = map(int,input().split())
V = list(map(int,input().split()))

ans = -1

for l in range(N+1):
    for r in range(N+1):
        tmp = V[:l] + V[N-r:]
        if l+r > N:
            break
        res = K - (l+r)
        if res < 0:
            break
        tmp.sort()
        for i in range(min(res,len(tmp))):
            if tmp[0] < 0:
                tmp.pop(0)
            else:
                break
        ans = max(ans,sum(tmp))
            
print(ans)

written by 友達のtaniponyo

ABC127-D_IntegerCardsをpythonで解いた（その他）

問題

• ABC127-Integer Cards

問題概要

カードが$$N$$枚あり、それぞれ整数$A_i$が書かれている。
$M$回以下の操作を行う。
カードを$B_j$枚まで選ぶ。選んだカードを$C_j$に書き換える
カードに書かれた数字の合計の最大値は？

解法

• 小さい数字のカードを書き換えるのが正解？と思いきや、書き換えるカードの枚数は決まってはいないので、その解法では間に合わない。
• カードの数字を書き換えることなく、計算する方法を考えよう。

方針

• あらかじめ$C_j$で降順ソートしてあげ、$tmp += [C_j]*B_j$ といったリストを作成
• $A + tmp$を降順ソートし、前から$N$枚の合計を計算することで、書き換えたこととなる。

例

$A = [1,2,3,4,5]$
$B,C = 2,3$
ならば、 $A + tmp = [1,2,3,4,5,3,3] = [5,4,3,3,3,2,1]$となり、$1,2$を書き換えるのが最善の操作である。

コード

N,M = list(map(int,input().split()))
A = list(map(int,input().split()))
BC = [list(map(int,input().split())) for i in range(M)]

BC.sort(key=lambda x:-x[1])
temp = []
for i in range(M):
    temp += [BC[i][1]]*BC[i][0]
    if len(temp) > N:
        break
    
A += temp

A.sort(reverse = True)

print(sum(A[:N]))

written by 友達のtaniponyo

ABC172-D_SumofDivisorsをpythonで解いた（約数）

問題

• ABC172-D_SumofDivisors

問題概要

Xの正の約数の個数をf(X)とするとき、∑K×f(K)

解法

ポイント

• 整数問題は書き出して規則を捉える
  • 1から始まるときは（ある特定の区間でないときは）特に、一発で答えが出たりする
• 横に集計しても、縦に集計しても同じ
  • -> 横に集計しづらいときは、縦に集計してみる
• 約数の問題は、都度約数を求める場合と、小さい方から予めn倍して格納しておくといい場合がある

コード

• かつっぱさんのコード
  • pypyだと268ms, pythonだと3101ms

n = int(input())

def calc(b, e):
    # 等差数列の和
    cnt = e // b
    return (b + e) * cnt // 2

ans = 0

for i in range(1, n+1):
    ans += calc(i, n//i * i)

print(ans)

ABC172-C_Tsundokuをpythonで解いた（累積和+二分探索or尺取り法）

問題

• ABC172-C_Tsundoku

問題概要

• 机が二つ。それぞれに本が積まれている。上から順に読んでいく。k分を超えない範囲で、何冊読めるか。

解法(1)

ポイント

• 2つの変数の和の（条件下での）最大値を探す
  • -> 一つを固定して、二分探索 or 尺取り法
  • <- 単調増加であることが大事

• 累積和

配列aに対して累積和sを求めると、配列aの区間[left, right]の総和が
s[right] - s[left]
でO(1)で求められる

from itertools import accumulate
a_list = list(map(int, input().split()))
# -> [60, 90, 120]

sum_a_list = list(accumulate([0] + a_list))
# -> [0, 60, 150, 270]

• 二分探索

import bisect

example_list = [1,3,4,5,6,7,9,10,13,16,18,22,24,25,26] 
target = 22

example_list = sorted(example_list)

target_index = bisect.bisect_left(example_list,target)

print(target_index)

コード

n,m,k = map(int,input().split())
a_list = list(map(int,input().split()))
b_list = list(map(int,input().split()))

from itertools import accumulate
import bisect

sum_a_list = list(accumulate([0] + a_list))
sum_b_list = list(accumulate([0] + b_list))

ans = 0
b_idx = 0
for a_idx in range(n+1):
    if sum_a_list[a_idx] > k:
        continue

    time_rest = k - sum_a_list[a_idx]
    # 同じ数字を取った場合を考慮してleftでなくright
    b_idx = bisect.bisect_right(sum_b_list,time_rest) - 1

    ans = max(ans, a_idx + b_idx)

print(ans)

解法(2)

ポイント

• 尺取り法
  • しゃくとり法を復習してみた(Python)
  • 単調増加であることを利用して、「インデックスを下げ続ける（初期化しない）」ことが計算量を削減するポイント

* 実装イメージ
  * i(left)はfor文で最初から最後まで動かしていく
  * j(right)はwhile文で条件を満たす限り動かしていく
    * ポイントは、iをすすめるときに、jを初期化（i+1などに）しない。jはそのまま進めていく（ここで計算量を減らす）
    * = 単純に考えれば、right = left, left+1, left+2, ..., と調べて行って、条件を満たさなくなる場所を検出することで実現できるが、
    * ->left を固定して right を右に動かして、今度は left を 1 増やして...」という動きをさせる。この動きがしゃくとり虫のようなので、しゃくとり法と呼ばれます。

コード

n,m,k = map(int,input().split())
a_list = list(map(int,input().split()))
b_list = list(map(int,input().split()))

from itertools import accumulate
sum_a_list = list(accumulate([0] + a_list))
sum_b_list = list(accumulate([0] + b_list))

ans = 0
b_idx = m
for a_idx in range(n+1):
    if sum_a_list[a_idx] > k:
        continue

    while sum_a_list[a_idx] + sum_b_list[b_idx] > k:
        b_idx -= 1

    ans = max(ans, a_idx + b_idx)

print(ans)