れとろのメモ置場

とあるSEのメモ置場

AtCoder Beginner Contest197 (ABC197) のメモ

AtCoder Beginner Contest197に参加しました。

結果

A,B,C問題の3問正解でパフォーマンスが813でした。 D問題は幾何学とか図形の問題っぽい? E問題はなんとなく解けそうで、でも解けなかった。最小化するの難しい。近い解なら求められるんだけどなあ。

A - Rotate

文字列の扱い方を知っているかどうかという問題だったのかな。 問題だと3文字って制限があるけど、何文字になろうと2文字目から最後までの部分文字列+最初の文字で新しい文字列を作成すればおしまい。

B - Visibility

マス(X,Y)から上下左右を障害物に当たるまで順番に探索すればいい。 探索の初期値にマス(X,Y)を含むなら重複して数えているのでその分減らして、探索の初期値にマス(X,Y)を含まないならマス(X,Y)分を増やす。

C - ORXOR

区間の作り方がちょっと難しかった。こう言う時のきれいな区間の分け方を知らないので、制約的にNが小さかい点に注目してbit全探索の力技で乗り切った。 2ビット目からビットが1か0かを確認して、ビットが1のときは1ビット前のものと同じ区間に入れる。ビットが0のときは1ビット前とは別の区間とする。ってことにして区間を分けた。 分けれてしまえばあとはOR演算とXOR演算で計算して最小値を求めれば良い。 bit全探索を使っているので全通りの区間の分け方を確認できて最小値をちゃんと求められる。

D - Opposite

図形の問題っぽい。賢い方法がわからなかった。 正多角形だからどの頂点も同心円状にあるとか、Nの制約的に x _ {0} x _ {\frac{N}{2}} は直線状にあるから円の中心は求められるな、円の半径も求められるなとかは思ったけど、 そこからx_{1}の座標を確実に求めるのはちょっと難しかった。

E - Traveler

これも解けそうで解けなかった。 問題文的に C_{i}が小さい順位にボールを集める、反復横跳びみたいにこまめに方向転換してると無駄が多いから同じ色のボールを回収する間は1方向に進んだ方が良いくらいはすぐに思いついてけど、それだけで愚直に実装してみるとサンプルの時点で微妙に答えが違った。 あと1,2個なにか実装方針が必要な気がしたけど何も思いつかなかった。

座標0からスタートして座標0に帰ってるから循環セールスマン問題っぽい気もした。

AWS上でRedmineサーバーを作ってみた(1日目:ネットワーク構築)

せっかくAWS SAAの試験勉強でAWSアカウント作ったし、色々サービスの勉強もしたのでなにかサーバーを立てみたくなり、タスク管理用にRedmineサーバーを作ってみた。 (やったことをメモ程度に書くだけで意外と疲れたので記事を2,3個に分割しておく。長過ぎると読むの疲れるし。)

やったこと

詰まったこと

  • VPCの設定(通信許可の設定周り)
  • RDSで作ったインスタンスに追加のユーザー作成、追加ユーザーでログイン
  • Apacheとpassengerの連携設定

構築までの手順

  1. VPCやサブネットの作成、セキュリティグループ・ネットワークACLの設定
  2. RDSでPostgresインスタンスの構築、Redmine用のDB作成
  3. EC2でRedmineのインストール、動作確認
  4. apacheとpassengerを連携させてWebサイトとしてRedmineの公開

※今回の記事では1だけを記載

VPCの構築

ウィザードを使えば一発でVPCの作成からサブネットの構築までできるけど、1回くらい手動で作ってみたいなと思って手動でVPC、パブリックサブネット、プライベートサブネットを作成してみた。

1.VPCの作成

VPC名とIPv4CIDRブロックを指定してVPCを作成する。

2.インターネットゲートウェイの作成

名前を指定してインターネットゲートウェイを作成する。

その後、作成したインターネットゲートウェイVPCにアタッチする。これでVPCからインターネットに通信する口ができる。

3.サブネットの作成

どのVPCの中に作成するか指定して、サブネットの名前、配置するアベイラビリティーゾーン、IPv4CIDRブロックを指定してサブネットを作成する。今回はインターネットからアクセスできる用のパブリックサブネットとインターネットからはアクセスできないプライベートサブネットの2つ用意したいので、サブネットを2つ作成する。 ※RDSでインスタント作成時にサブネットグループを作成する関係で結局パブリック:1個、プライベート:3個のサブネットを作成した。

1度作成したサブネットのサイズは変更できないので必要なIPの数より大き目に設定する。今回は深く考えずに/24で作成。(後々このサブネットに色々サーバー立ててみようとするだろうから)

4.セキュリティグループの作成

作成したVPC用にセキュリティグループを作成する。デフォルトで作成されているものもあるけど、そのままだとインターネットからVPCへの通信は全部拒否されているのでSSHだけ許可するセキュリティグループを作成。

5.ネットワークACLの作成

サブネット用にネットワークACLを作成する。こっちにもSSHを許可するように設定をしてからサブネットに関連付けを行う。 アウトバウンドルールにはすべての通信を許可するように設定しておく。(理由は後述)

セキュリティグループとネットワークACLの両方で通信を許可されていないとサブネット内のインスタンスと通信できないので設定内容に気をつける。 最小限のポートしか開けたくないと思ってアウトバウンドもSSHだけ許可設定してたらちょっとはまった。

6.ルートテーブルの作成

サブネット用にルートテーブルを作成する。初期設定でVPC内の通信用のルートは設定されていた。パブリックサブネット用ならここにターゲットがインターネットゲートウェイのルートを追加する。 今回はインターネットゲートウェイへのルートを設定したパブリックサブネット用のルートテーブルとインターネットゲートウェイへのルートは設定してないプライベートサブネット用の2つを作成。 その後、作成したルートテーブルをサブネットに関連付ける。

ここまで設定するとサブネット内とインターネット間で通信ができるはず。EC2インスタンスを用意して通信できるかどうか確認して、ダメそうなら設定内容を確認する。 1回目はここでEC2インスタンスSSH接続できなくて、設定見直してもどこが悪いのかわからなかったので1回全部削除してやり直すことに・・・

この記事書きながら何やったか思い出すついでに、できたばかりの大阪リージョンでやってみたらまたEC2につながらない・・・VPCはウィザード使って構築するのが無難だなあ。

その後、ネットワークACLのアウトバウンドルールにすべてのトラフィックを許可するとつながるようになった。許可設定は最小限にしたいからアウトバウンドルールもSSHだけ許可してたけどそれが原因だったみたい。 そういえばSSHサーバはポート番号22だけど、SSHクライアントはボート番号22じゃなくてランダムになるんだっけ。アウトバウンドルールでポート番号22だけ許可にしてたからSSHサーバ(EC2インスタンス)からこっちのPCへの通信ができなかったのか。原因がわかってスッキリ。

アウトバウンドとは言えすべてのポートでの通信を許可するのはセキュリティ的にどうなのかなあとは思うけど、ステートレスなファイアウォールだから仕方ないのかなあ。

続きはまた別の記事で。 あとはDBサーバの構築、RedmineのインストールとapacheRuby on Railsのアプリを動かす設定をしたらおしまい。

パナソニックプログラミングコンテスト(AtCoder Beginner Contest195)のメモ

パナソニックプログラミングコンテスト(AtCoder Beginner Contest195)に参加しました。

結果

A,B,C問題がの3問正解でパフォーマンスが699でした。B問題もC問題も解くのが遅かったのでパフォーマンスは結構低め… C問題は解き方自体は合ってたのに解答を管理する用変数の型選択をミスったのでWAを量産しちゃった。long longがオーバーフローするのは想定外だった。

A問題

剰余計算してHがMで割り切れるかどうかを判断するだけ。 何回か前のABCでも似たように剰余計算してIFで分岐するっていう問題があった気がする。

B問題

B問題にしては難しい気がするけど、解けてる人数見ると普段どおりだからそんなに難しくなかったのかなあ。結局ちゃんとACしてるから良かったけど。

いろいろ試してだめだったので、最終的にはWをAとBでそれぞれ割って個数の範囲に当たりをつけてから、 個数\times A \leq Wキロ  \leq 個数\times Bを当たりをつけた範囲の下からと上から探索して最初に式を満たす個数を求めました。 答えがxとすると、みかん1つあたりの平均の重さはWキロ/xになるのでこれがA \leq Wキロ/x \leq Bの範囲に入っていれば良い。各項をx倍するとA\times x \leq Wキロ \leq B\times xになるので数式を満たすxの最大と最小を求めればそれが答えになるはず。どのグラム数のみかんが何個って詳細は求められてないのでこれでなんとか解ける。

Wキログラムピッタリにするって方法を考えるのが難しかった。X _ {i}グラムのものがN _ {i}個ある時とかならもう少し楽だったと思う。Aグラム以上Bグラム以下の全通りが無限個選択できるって考えると前通りするのが大変だなあって思って。難しく考えすぎてるだけな気もするけど。

C問題

制約をみると1 \leq N \leq 10^{15}なので全探索すると余裕でTLEになるはわかる。と言うことは全探索以外方法を使って探索数を減らさないといけないことになる。 順番に整数xの時コンマをいくつ書くのかだと間に合わないので、3桁後、6桁後、・・・、15桁後のコンマそれぞれが何回書かれることになるのかを考えて数えて数え上げました。 例えば3桁後のコンマは1,000~Nまで毎回書かれるのでN-1,000+1回書かれることになるし、6桁後のコンマは1,000,000~Nまで毎回書かれるのでN-1,000,000+1回書かれることになる。 こんな具合に10^{15}まで順番に計算していけば答えが求められる。これがO(1)で求まるってのは意外。順番に数えるとO(N)になることを考えるとだからだいぶ早くなる。

答えはlong longでもオーバーフローするみたいでそれに気付かず何回かWAになった。型をdoubleにするだけでACしたのでもったいなかった。 long longがオーバーフローするのはちょっと想定してなかった。

D問題

制約自体は全体的に小さめなので全探索しても間に合いそうなのと、前のクエリの結果は影響しないので毎回独立して問題を解いて良いのはわかった。 B,C問題で時間使いすぎててじっくり考える余裕がなかったので10分くらいで直感のままに一気に一通り実装したけどバグ取りが間に合わなかった。

AtCoder Beginner Contest194 (ABC194) のメモ

AtCoder Beginner Contest194に参加しました。

結果

A,B,C問題の3問正解でパフォーマンスが815でした。 C問題に少し悩み、D問題はあんまり解いたことがない期待値を求める問題で苦戦した。

A問題

問題文通り実装すればOK。 乳固形分がAとBの和という点に気をつけるぐらい。

B問題

問題文を読むとややこしそうな気がするけど、成約を見ると  2 \leq N \leq 1000とNが小さいので2重ループで全通り確認しても間に合う。 仕事Aに従業員i、仕事Bに従業員jを割り当てるのを 1 \leq i,j \leq Nの全パターン確認して時間の最小値を求めれば良い。 仕事が終わる時間は、i=jのときは  A _ {i} + B _ {j}になって、 i \neq j のときはA _ {i}B _ {j} の大きい方になる。

C問題

成約を見ると2 \leq N \leq 3\times10 ^ {5}なので2重ループで解こうとすると最大で10 ^ {10}くらいになるのでTLEになる。 ダメ元で2重ループで解いて提出したら案の定TLEになった。

どうやって計算量減らそうかなと考えながら成約を見ると|A _ {i}| \leq 200と高々400通りくらいしか種類がない。 つまり大体のA _ {i}は別のものと値が被ってる。同じ計算を何度もする必要はないので計算を省略できる。 A _ {i}のどの値が何個あるのかを数えて、A _ {i}の値の種類全通りで差の2乗を計算する。あとは各A _ {i}が何個あるのかをもとに何組その計算をすることになるのか数えて2乗和にかけて積み上げていく。

D問題

解けそうで解けなかった。 問題文を読んで確率DPってやつかなと思って解いてけど、解説を読むとDPじゃなくてただの数学だったっぽい。

AWS認定ソリューションアーキテクトアソシエイトに合格しました

先日AWS認定ソリューションアーキテクトアソシエイト(AWS SAA-C02)に合格しました。 3年後くらいに更新したり、今度は別の資格を取る場合に備えてて今回の勉強で何をしたのかメモしておこうと思います。 (あとブログを書く練習も兼ねて) そう思いつつ下書きでほったらかしてはや1ヶ月とりあえず公開しておいて適宜追記しようかな。

資格取得のきっかけ

会社から資格を取るように言われてたのがきっかけでした。 退職したり更新せずに資格の期限切らしたりで、社内でAWSの資格を持ってる人が減ってきたから増やそうとしているらしい。 (とはいえ社内は分業が進んでてAWSとかインフラ周りは専門部隊がいるし、日々神エクセルと格闘してるだけの設計かお客さんと打ち合わせしかしないSIer企業なので業務でAWS触ることは今までもないし今後の完全になさそう。転職したいなあ…

試験結果

747点で合格でした。ボーダーが720点なので割とぎりぎりで危なかった。でも合格は合格。

使った教材

Udemyの講座

  • これだけでOK!AWS認定ソリューションアーキテクト-アソシエイト試験突破講座(SAA-C02試験対応版)
     ハンズオン中心の講座。実際に動かして各サービスがどんなものか把握するのに役立った。

  • 【SAA-C02版】AWS認定ソリューションアーキテクトアソシエイト模擬試験問題集
     全6回分の模擬試験。難易度普通の1回と難問ばっかりの4回にC02対策の1回で計6回分。難問ばっかりの4回は本当に難しかった。その分勉強にはなったけど。

Architecting on AWS(会社が手配してくれた研修)の資料

勉強方法

Architecting on AWSのテキストを使ってWell-Architectedや試験によく出るサービスの特徴を把握しつつ、Udemyの講座で別の人の視点からサービスの勉強をしたり、ハンズオンをやってみたりしてました。

試験受ける1週間くらい前からは模擬試験を1日1回分解いて復習して、翌日以降は毎日解き直してを繰り返し。 何度も繰り返し解いてなぜその選択肢が正解なのか、なぜ他の選択肢は不正解なのかを覚えていき各サービスの理解を深めたり、間違って認識してたサービスの内容を訂正しつつ詰め込んでいきました。
あとは、このサービスでこの観点で最適かはどうするかって聞かれたらこう答えるみたいなパターンを覚えたり。 (試験まで時間がなかったので1週間くらいで詰め込んでたけどもっと期間を取ったほうが良かった。毎日夜遅くまで勉強することになってたから翌日起きるのが辛かった……)
模擬試験は1回目解くときは正答率が50%前後だったけど2周目以降は90%前後は正解できるようになってたので、試験で似た問題が出たときは自信を持って答えられて良かった。

試験を受けてみての所感

試験問題と模擬試験は文章量とか問われている内容・観点がそこそこ違ってたので試験中は終始この問題はどの知識を問いているのかよくわからないなあと思いながら解いてました。模擬試験と似た内容の問題があったときはラッキーと思いつつそんな問題は2,3割くらいしかなかった。
1時間位かけて1週して残り時間で必死に見直ししてたけど、もっとちゃんと勉強しとかないと厳しいなあと思いました。このサービスはリージョン・AZ・サブネットどこまでに対応してたんだっけとか、このサービスはマルチAZ・マルチリージョン対応してたっけとか。考えれば考えるほど曖昧な部分がどうだったかわからなくなってきた。 1年位業務で触ってればその辺りも把握できてくるのかなあ。

SAAは2020年の春頃にC02に移行して試験の傾向が変わったらしいので、情報とか教材が出揃うまで受験は見送ってたけど結局教材の方はあんまり出てこなかったなあ。12月ころにSAA-C02対応のテキストがやっと発売されたくらいだったと思う。こういった試験対策のテキストって2,3ヶ月もすればC02対応版が出てくると思ってたから意外。

今回はほとんど利用しなかったから書いてないけど、Kindle Unlimitedを登録すると無料で読める本の中にSAAの教材やAWS関連の技術書が結構あった。C01版の試験だった頃にいろいろな人の合格報告でおすすめされてたやつとか。試験対策にお金をあまりかけたくない人は試してみては。

キャディプログラミングコンテスト2021(ABC193)のメモ

キャディプログラミングコンテスト2021に参加しました。

結果

A,B,C問題の3問正解でパフォーマンスが754。D問題が以降がやっぱり解けない。 とはいえD問題もほとんど解けてて、たぶんコーナーケースを漏らしてるのが原因で7ケースがWA。

8割位通るけどなんかのコーナーケースを見逃してるのが原因でWAってのが多いから、頭を柔らかくしてコーナーケースを気付けるようになりたい。

A問題

算数ができれば解ける問題。何%引きって聞かれると戸惑うけど落ちつて計算すれば解ける。

B問題

A分後にはA台在庫が減ってるのでX-Aが1以上の店が考える対象となる。 X-Aが1以上の中から最小のPを求めれば良い。

C問題

1から順番にa^{b}で表せるかどうかを確認するのは面倒だから、a^{b}で表せるものの数を数えてNから引くという方針で解きました。

 2 \leq a,b \leq Nの範囲で全探索って思ったけど、N^{10}なので二重ループで処理しようとするとO(N^{100})くらいだから全然間に合わない。 少し考えて、bが2以上という条件から探索範囲は a^{2} \leq a^{b} \leq N になるから、aは最大でも \sqrt{N} = 10^{5}程度って気づいたので、 2 \leq a \leq \sqrt{N} , 2 \leq b \leq N かつ  a^{b} \leq Nの範囲を二重ループで探索。bの範囲はもう少し小さくできそうだけど、とりあえずAC。

D問題

5枚目のカードとしてあり得るのは高橋くん、青木くんそれぞれ9通り。よって手札は最大で81通りの組み合わせ。 81通りそれぞれのパターンでカードの残り枚数的に可能かどうかを確認しつつ、そのパターンになるカードの選び方を数え上げて、高橋くんが勝つかどうかも確認して、最終的に 高橋くんが勝つ確率を算出。

方針はあってると思うけど、何かのケースを見逃してるみたいでいくつかのテストケースがWA。 後で解説読んで復習しておこう。

(2021/02/28追記)

点数計算間違えてただけだった。単純なミス。10^{c_{i}}だからカードが0枚のときは1になるのに何故か足してなかった。 1版最初に提出したコードの点数計算部分直したらACできた… レーティング的にすごく惜しいことをしてた。

SOMPO HDプログラミングコンテスト(ABC192)のメモ

SOMPO HDプログラミングコンテスト(ABC192)に参加しました。

結果

A,B,Cの3問正解でパフォーマンスが612。相変わらず茶色くらいのパフォーマンス。やっぱり安定してD問題くらいまでは解けないと緑や水色にはなれないなあ。

E問題が前回同様グラフの問題だったから解きたかったなあ。D問題はどれくらい調べればいいのかわからなかった。

A問題

100 - (入力 \% 100)を出力するだけ。標準の入出力+剰余計算を知っているか・できるかどうかって言う問題。

B問題

問題文通りに実装。文字が大文字かどうかを判断する方法をどう実装するのかという問題。 C++ならisupperやislowerというステキな関数があるのでそれを使えば楽。それ以外ならcharの値が'A'~'Z'、'a'~'z'のどっちに含まれるかで判断かなあ。

C問題

3種類の関数を実装して、初項から順番に計算していく。 入力を文字列として受け取って、ソートして、数字に変換して計算するって処理を繰り返す。 文字列を受け取ってソートして数字に変換して返すって部分を関数化すればコードはスッキリする。

D問題

X桁の数字をN進数から10進数に変換する処理はできたけど、入力のXが桁数多すぎると10進数に変換してもオーバーフローするしなあとか、何進数まで調べればいいのかわからないなあってなってギブアップ。 解説読むと二分探索使うってあったけど、コンテスト中は完全に頭から抜けてたなあ。二分探索はこんなときに使うのか。

E問題

前回のABC191でのE問題同様グラフでしかもダイクストラ法の問題。 コスト計算するときにK_iの倍数+T_iになるようにすればいいんでしょと思って、ダイクストラ方のコスト計算部分をちょっとごにょごにょして実装したけど半分くらいTLEとWAになって悲しくなった。