れとろのメモ置場

とあるSEのメモ置場

AtCoder Beginner Contest210

AtCoder Beginner Contest210に参加しました。

結果

A,B,C問題の3問正解でパフォーマンスが640でした。 最近パフォーマンスが悪くて少しずつレーティングが落ちてきてやばい… 時間作って精進したい。

A - Cabbages

問題文の通りに実装する。
値段が変わる境目がAなのでNがA以下かどうかで処理が分岐する。 N \leq Aの時はN \times Xが答えになって、N>Aの時は A \times X + (N-A) \times Yが答えになる。

B - Bouzu Mekuri

文字列Sの中で最初に1がでるのは誰のターンの時かを答える問題。文字列の長さは最大でも 10 ^ {5}なので先頭から順番に見ていっても十分間に合う長さ。結局、文字列Sで最初に1が出るのは先頭から奇数番目なのか偶数番目なのかをもとにその時のプレイヤーの名前を答えれば良い。偶奇の判断は2で割った余りをもとにするれば良い。

C - Colorful Candies

連続するK個分の区間の中で何種類の色があるのかを計算して最大値を答える問題。
区間がK個と固定なので1~K個の区間を最初に確認してそこからは順番に、区間最後尾の要素を削除・区間先頭を1つずらす・区間内で何種類の色があるのかを数える を先頭が数列の最後尾に来るまで繰り返して、要素の種類が最大でいくつになるのかを答えれば良い。
区間で何種類あるのかはC++だったのでmapのsize()とerase()を使って数えたけど、他に賢いやり方がなにかありそう…

AtCoder Beginner Contest208

AtCoder Beginner Contest208に参加しました。

結果

A,B,C問題の3問正解でパフォーマンスが614でした。 途中で急にPCがフリーズして焦った。
D問題は相変わらず解けそうで解けない… C問題までは問題をななめ読みして解きがちだから途中まで問題を少し勘違いして解いてて時間がかかった。

A - Rolling Dice

BがA以上6A以下かどうかを判断する。

B - Factorial Yen Coin

1!から10!までを計算して、大きい方から順番にPから引いていく。最終的には何回引けたかを答えればOK

C - Fair Candy Distribution

いろいろ解き方はあると思う。
全体に何回配れるか(K/N)と端数がどれくらいあるか(K mod N)を計算する。 次にa _ {i}を小さい順に並べた時(K mod N)番目の値が何かを確認して、 後はa _ {i}がその値より大きいかどうかでK/Nを出力するかK/N+1を出力するかを判断する。

D - Shortest Path Queries 2

時間が足らなかった…
グラフの問題なのでダイクストラ法をベースに問題用にところどころ修正して解こうとしたけど、ちょっとうまくできなかった。 解説を読むとワーシャル-フロイド法で解く問題だったらしい。ワーシャル-フロイド法はO(N^{3})ですごく遅いアルゴリズムって認識だったのでそもそも検討してなかったや。(サンプルのコード自体は用意してるのになあ)
制約見ると珍しく制限時間が3秒だったのメタ読みすれば思いつけたのか。

AtCoder Beginner Contest207

AtCoder Beginner Contest207に参加しました。

結果

A,B,C問題の3問正解でパフォーマンスが1145でした。
前回同様D問題が解けそうで解けず、E問題がもうすこし頑張れば解けそうな気がした。解説読むとE問題は方針自体は間違ってなかったから、もう少し考察がちゃんとできてれば正解できてたのかなあ。
あと、今回は普段よりも頭の回転が鈍ってた気がする。B,C問題が問題文読んでもすぐにはよく理解できなかった…

A - Repression

3通りある解候補(A+B,A+C,B+C)を計算して最大のものを出力すれば良い。
他には、3つを配列に入れてソートして上位2つを足したものを出力しても良い。

B - Hydrate

初期状態が水色A個、赤色0個に対して水色Bx個、赤色Cx個ずつ足していって A+BxがCDx以下になる最小のxを求める問題。
x自体は何回足したか数えながらループで処理すれば求められる。問題は何回足してもA+Bx>CDxにしかならない場合の判断方法。 結局B \geq CDの時は条件を満たせないのでループ前に確認して対応する。

C - Many Segments

制約を見るとN \leq 2000だから二重ループくらいまでなら間に合いそう。なのでi,jの組合せは全通り探索できそう。
あとは手短に区間iと区間jに重なっている部分があるかどうかを判断できれば正解できそう。
注目している区間が閉区間の場合は問題ないけど半開区間、開区間がある場合は判断がやりづらい。端点を含まない場合の表現方法を知らなかったので、とりあえず今回は0.1だけずらして対応してみた。 区間が被っているかどうかは開区間の処理後に2つの区間の両端の大小関係をもとに判断した。

D - Congruence Points

回転して平行移動すると一致させられるかどうかを答える問題。 点の回転なので回転行列と掛ければ良さそう。でも結局解けなかった。
制約を見るとNは小さいし角度も360度程度しかないので、Sのある点を回転させて平行移動するとTのある点に一致させられるかどうか、一致する時は全部の点を同様に回転・平行移動させて全部一致させられるかどうかを360度全部確認はできそう。実際は小数点以下で誤差があるのかうまく行かなかった…

E - Mod i

問題文を読んでDPで解けそうだと思ったから DP[i][k][x]=A _ {i}までの部分数列をk個に分割する(k個目の部分数列はA _ {x}から始まる)時の何通りあるかで解こうとしたけど O(N ^ 3)なので案の定TLEした。解説を読むとバッチリこの方法だとTLEするって書かれてた…

AWS上でRedmineサーバーを作ってみた(2日目:データベース構築)

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

1日目はこっち
AWS上でRedmineサーバーを作ってみた(1日目:ネットワーク構築) - れとろのメモ置場

やったこと

詰まったこと

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

構築までの手順

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

※今回の記事は2だけが対象

RDBインスタンスの構築

RDSでDBサーバを作成する。とりあえず無料枠を使える設定で構築。 f:id:Retro_00:20210623215548j:plain f:id:Retro_00:20210623215553j:plain f:id:Retro_00:20210623215556j:plain f:id:Retro_00:20210623215600j:plain f:id:Retro_00:20210623215603j:plain f:id:Retro_00:20210623215606j:plain f:id:Retro_00:20210623215609j:plain f:id:Retro_00:20210623220941j:plain f:id:Retro_00:20210623215542j:plain

DBはpostgressを選択してインスタンスを作ろうとしたところ、サブネットグループの指定が必須だった。
そんなの知らなかったなあと思いつつ、複数作っておいたプライベートサブネットでサブネットグループを作成。 (名前と説明、VPC、AZ、グループに入れるサブネットを選択してサブネットグループを作成。すごく簡単。)
ついでにセキュリティグループも作成。セキュリティグループの切り分け単位が迷子だけど、DBインスタンスに設定する想定で作成。SSHとはじめに作成したVPC用のセキュリティグループを設定しているインスタンスからの通信を許可するセキュリティグループを作成した。
サブネットグループとDBインスタンス用のセキュリティグループを作ってから改めてDBインスタンスを作成。

Redmine用のDB・ユーザーを作成

RDBインスタンスはプライベートサブネット上に作ったので、DB作成とかでアクセスしたい場合はパブリックサブネット経由じゃないとアクセスできない。 そこでEC2インスタンスにクライアントツールをインストールしてパブリックサブネット上のEC2インスタンスから接続して設定など操作を行う。
まずは操作用のEC2インスタンを作成してSSHでアクセス後にPostgreSQLのクライアントツールをインストールする。
yum install postgresql
インストール後psqlコマンドでDBにアクセスしに行く。オプションを含むコマンドは以下の通り。RBDインスタンスのエンドポイントはAWSRDBインスタンス詳細画面から確認しておく。
psql --host=RDBインスタンスのエンドポイント --port=5432 --username=作成時設定したマスターユーザー --password

f:id:Retro_00:20210623220206j:plain 公式のインストールガイドによるとPostgreSQLの場合は以下のコマンドを実行すればいいらしいのでコマンドを実行する。

CREATE ROLE redmine LOGIN ENCRYPTED PASSWORD 'my_password' NOINHERIT VALID UNTIL 'infinity';
CREATE DATABASE redmine WITH ENCODING='UTF8' OWNER=redmine;

実行するけど2つ目のコマンドを実行するとエラーになる。いろいろ調べた結果、ログイン中のユーザーは1行目で作成したロールに関する権限がないので所有者がredmineになるデータベースが作れないっぽい。 なので以下のコマンドでマスターユーザーにredmineロールの権限を付与する。
GRANT redmine TO マスターユーザー;
その後改めてエラーとなった2行目のコマンドを実行する。 (1度うまく行かなかったのでDBインスタンスを作り直したら今度はできた。PostgreSQLはあんまり触ったことがないからよくわからないや。)
作成したredmineユーザーがちゃんとログインできるのかを確認する。

psql --host=RDBインスタンスのエンドポイント --port=5432 --username=redmine --password

ちゃんとログインできればDB作成は完了。ログイン出来ないときはエラー内容を調べて対応する。 (ロール作成時にパスワードを設定したはずなのにパスワードが設定されてなくてログイン出来ないことがあった。 他にはredmineロールを付与するときに何回やっても権限が設定できてないみたいでCREATE DATABASEが失敗したけどDBインスタンス作り直すと1発でうまく行ったり。)

参考

http://guide.redmine.jp/RedmineInstall/#step-2- https://qiita.com/bwtakacy/items/845c193c6da3218a546d

AtCoder Beginner Contest206

AtCoder Beginner Contest206に参加しました。

結果

A,B,C問題の3問正解でパフォーマンスが879でした。
D問題が解けそうで解けず、E問題がもうすこし頑張れば解けそうな気がした。結局時間は足らなかったけど…

A - Maxi-Buying

問題文の通り税込価格を計算して、計算結果に応じて適切な文字列を表示させる。 注意点は言語によっては計算結果を整数型に変換する処理が必要かもしれないくらい。

B - Savings

ループ文で1+2+・・・を計算してN以上になったタイミングで何日目なのかを表示させれば良い。
少し考えると、1+2+・・・+X=\frac{1}{2}X(X+1)なのでX(X+1)=2Nになる。ほぼX^{2}=2NだからX=\sqrt{2N}あたりの値が答えになりそう。

C - Swappable

問題文を読むと結局、Aの各値に対して注目している A _ {i}の値と異なる A _ {j} の個数を求めて足していけば答えになる。
Aにはどの値が何個含まれるか数えておき、各値(Xとする)に対してN-値Xの個数を足していけば良い。

E - Divide Both

問題文と制約を読むと全探索は明らかに難しそう。条件を満たす整数組を数え上げるのは難しそうなので全体から条件を満たさない整数組を除外していき、残ったものを数えていけば良さそうな気がする。
条件を見ると

  •  g\neq1からx,yは互いに素ではない。
  • \frac{x}{g} \neq 1からx \neq gとなる。つまりx,yの最大公約数がxではない → yはxの倍数ではない。

が言える。また、x<yだけ考えて、最後に2倍すれば答えになりそう。 後はL以上R以下の範囲で、ある値xに対して

  • x以上
  • xの倍数
  • 互いに素じゃない

数を探してx以上R以下の値から除外すれば求めたい条件を満たすyになると思う。
互いに素じゃないという部分が難しい気がした。約数列挙とかエラトステネスの篩とか使って求めようとしたけどうまくできなかった…

AtCoder Beginner Contest205

AtCoder Beginner Contest205に参加しました。

結果

A,B,C問題の3問正解ででした。 (レーティングの更新がまだなのでパフォーマンスは不明) C問題で普段より苦戦しすぎたなあ

A - kcal

問題文通りに計算をする。注意点は、小数点が出てくる可能性があるので変数は整数型じゃなくて浮動小数点を扱えるものにするのにするくらいかなあ。

B - Permutation Check

やり方は色々あるけど、Aをソートしてi番目がiになっているかどうかで判断すれば良さそう。他にはiが何個あるか数えて1以外の場合はNoになるとか、setに入れて要素数がNになっているかどうかで判断するとか色々解き方はありそう。

C - POW

問題文のとおりに計算すると変数が扱える値以上の数値になりそうなので愚直に計算するのは良くなさそう。Pythonなら扱える数値の上限はないけど試しに提出したらTLEになった。累乗計算はそこまで早いわけじゃなさそう。
真面目に考察すると、Cが偶数のときは結果が必ず正になるからAとBの絶対値の大小比較の問題になる。 Cが奇数のときはAとBの大小を比較すればいい。累乗してもAとBの大小関係は変わらない。

D - Kth Excluded

解けそうで解けなかった。
制約的に前から順に数え上げるのはTLEになるのが予想できるので何かしら省略する工夫が必要そう。
Kが与えられたときにK以下の最大のAの値を二分探索で探せば高速にK以下かつAに含まれている数の個数がわかりそう(Aのインデックス=Aに含まれるK以下の数の個数になる※1-インデックスの場合。0-インデックスの場合は1ズレる  であってると思う)
後はKから順番にAに含まれて不足している個数分Kから数えれば答えになりそう。 でも結局二分探索後の処理がうまく実装できなかった。

AtCoder Beginner Contest204

AtCoder Beginner Contest204に参加しました。

結果

A,B,C問題の3問正解でパフォーマンスが 867でした。
最近またD問題が解けなくなってきてる。C問題までを早解きしてなんとかパフォーマンスは稼げてるけど…

A - Rock-paper-scissors

問題文の通りじゃんけんをすれば良い。
全員が同じ手を出しているか、全員がバラバラの手を出しているかの2パターンあるのでどちらのパターンか判断して適切な手を選ぶ。
グーチョキパーが0,1,2に変換されているので、全員がばらばらのパターンの場合2人の手を足したものが1,2,3のどれになっているかで足りない手を判断すれば良い。

B - Nuts

制約を見るとNが1000と小さいので前から順番に条件を満たすかどうか確認して、累積和を計算すれば良い。
具体的にはA _ {i}が10より大きい場合はA _ {i} -10を足していけば良い。或いは、max(A _ {i} -10 , 0)を足し続けていくのでも良い。

C - Tour

各都市をスタートとして全部の都市に対して経路計算をしてどの都市からどの都市にたどり着ける・たどり着けないを判断する。たどり着ける都市の組合せを数えればそれが答えになる。
経路計算は幅優先探索でもダイクストラでもなんでも良さそう。

D - Cooking

解けそうで解けなかった問題。 問題文を読むと結局次の問題を解けば良いと思った。

  • N個のアイテムを2つのグループに分ける。
  • 2つのオーブンの使用時間の大きい方を最小化する。

2つ目の最大値の最小化問題なら二分探索を使うのが定番。 1つ目の2つのグループに分けるって方がうまくできなかった。 bit全探索とか色々試したけどだめだった。