大学生が初めて学ぶ情報技術

お久しぶりです。ブログを更新するのは8ヶ月ぶりです。ブログを更新しない間、Unityを触ったりwebを触ったり組込系のソフトウェア開発をやってたり就職活動に虐殺されたりしてました。 内定募集中です。 今回は最近よく触ってたweb周りの話をしようと思います。 注意書き VTuberや勘に頼った適当な実装がお嫌いな方はブラウザバック推奨です。 また知識が浅いため誤った内容を書いてる部分があるかもです。そういった部分とか誤字脱字があればコメントなどで教えていただけると助かります。 目次 概要 一週間で作成した背景 リファクタリングの動機 リファクタリングの内容 なぜ改修に骨が折れたのか 今後の展望とか 最後に 概要 内容としては今年の9月末に一週間で作成した非公式ファンサイトを改修するのに3ヶ月ほどかかった話です。改修は以下のような内容をやってました。 レスポンシブ対応 Atomic Components導入 バグ修正 非公式ファンサイトの内容としては観てもらうことを目的としたものとなってます。なので状態管理とかサーバーサイドの実装とかはしてないです。firebaseにデプロイしているのでよろしければ見てもらえると製作者及び1ファンとして冥利に尽きます。( デプロイ先 ) ソースコードは公開してます。 公開先(github) 一週間で作成した背景 そもそも初心者が一週間でwebサイトを作ろうとする部分がおかしいと思いませんか？僕はそう思います。なので背景を書きます。ざっとまとめると、 締切日(1.5周年の日)の存在を勘違いしてた インターンに参加していたため製作期間の確保が出来なかった の2つです。１つ目としては、デビュー日が3/30でその半年後を12/30と勘違いしてた感じです。 数学の単位が取れない人間が足し算なんて出来ないので仕方ないですよね。 この勘違いに気づいたのが締め切り1週間前でした。もともと1.5周年をお祝いすることは自分の中で決めていたので1週間で作る羽目になりました。死。 2つ目としては9/1 ~ 9/25までインターンに参加してたため時間が取れなかった話です。期間中は毎日12時間ぐらい作業してたためこっちの開発に時間が回せなかったです。インターンのお話とか毎日12時間ぐらい作業していた理由については今後書くかもしれない。 リファクタリングの動機 リフ

タイトルの通り、AtCoder緑になりました！！！！！！ ということで今回は、(よくある)私が緑色になるまでにやってきたことを書いていきます。 精進量について 私が習得したアルゴリズムなどに触れていく前に、どれだけ精進したかについて書いていきます。 精進量は多くも少なくもないといったものだと思います。 次は精進量の推移についてです。今年に入ってから精進量を一気に増やしました。 今年に入ってからは、ABCのA・B埋めと新しいアルゴリズムの開拓の2つを中心に精進しました。 結果として、ABCのA・B埋めは早解きを安定させた要因の一つになったはず。 開拓したアルゴリズムは直近のコンテストには出てこなかったので今後に期待という感じです。 取り組んできた内容 この部分は所謂、「こんなアルゴリズムを習得した」とか、「このようなテクニックが少し使える」とかを書いていきます。 また、テンプレの作成や特定のアルゴリズムを用いる際に参考にしているサイトも合わせて紹介していきます。 その1. 基本的なものであれば取り扱えるようになったアルゴリズム・テクニック 全探索(DFS・BFS) 順列(next_permutation) STLの一部 最大公約数・最小公倍数・約数列挙 累積和 その2. 理論部分は曖昧だが、何とか取り扱えるアルゴリズム・テクニック DP(ナップザックDP・桁DPを含む) bit全探索 MOD演算(逆元を用いたものも含む) 二項係数(テーブルを事前作成するタイプのもの) ダイクストラ法 ワーシャルフロイド法 Union Find その3. アルゴリズム・テクニック以外で取り組んだ内容 AtCoderの自動提出ツール タイピングの練習 全探索(DFS・BFS) ここで挙げるDFS・BFSを除いた全探索のレベルとしては、 ABC85 C Otoshidama のような問題をスムーズに実装出来る程度です。 DFS・BFSについては他のアルゴリズムと組み合わせて解く高度な問題を除いた基本的な問題を解くことが出来るレベルです。 例 : ARC31 B 埋め立て , ABC160 D Line++ 参考にしている記事 BFS : BFS (幅優先探索) 超入門！

タイトルの通りAGC43 A問題をC++で解いた話です。 問題のリンク 今回はDP(動的計画法)を用いた解法を説明していこうと思います。 注意事項 この記事は筆者なりの解法を説明しています。 筆者は初心者です(重要)。 よって高度な解法は出来ないため効率が良い解き方などを求めている方だとあまり参考にならないと思います... また、DPに関して筆者も現在勉強中のため一部内容に不備があるかもしれません。 その時はコメントやTwitterのDMなどで連絡していただけると幸いです。 Twitterのリンク 考察を行う前に 今回与えられた問題を要約すると、左上のマスから右下のマスまで最も少ないコストを用いて移動するときそのコストを求めるというものです。 ポイントは 常に右か下にしか移動できない という点です。 これを言い換えると、ある点を(i,j)とするとその点に遷移することが出来るのは、 (i-1,j)か(i,j-1)の2点しか存在しないということです。( 0 < i,j ) そして今回入力例にはない重要なパターンがあります。 具体例を挙げます。 このような入力が与えられた時、右下までの最短コストは1です。 以下の長方形の部分の色を1回変更することによって右下まで移動することが出来ます。 これからわかる情報としては、#が連続している部分を通るルートが最もコストが低い場合も存在するということです。 考察 先程の、入力をもう一度用います。 最短経路について考察します。 最短経路は以下の画像の通りになります。 これを文字列として表現すると、 ####. となります。 この場合のコストは1です。 次に,以下の画像のようなルートを考えます。 これを文字列として表現すると、 #..#. となります。 この場合のコストは2です。 もう一つ別のルートを考えてみます。 これを文字列として表現すると、 ##.#. となります。 この場合のコストは2です。 以上の3つの例から、ある経路に対するコストは、 連続している#を1つの#に置き換えた後の文字列のうち、#の個数 ということがわかります。 DPとして考える そしてやっとDPの登場です。 今回用いるDPは、 d

タイトルの通りABC155 C問題をC++で解いた話です。 問題のリンク 今回は筆者が最近よくやるsetとmultisetを組み合わせた探索を説明していこうと思います。 問題 N枚の投票用紙があり、i(1 <= i <= N)枚目には文字列Siが書かれている。 書かれた回数が最も多い文字列を全て辞書順で小さい順に出力してください。 方針 Sの中で最も書かれた文字列が何回書かれたかを求める部分、 最も書かれた回数が多い文字列を列挙する部分の2回全探索をする。 制約 1 <= N <= 2 * 10^5 1 <= Siの長さ <= 10 問題点 どうやら通常のfor文だとTLEするらしい。 解決策 探索部分の計算量を削減する。 削減方法として先程述べたsetとmultisetを組み合わせた探索を紹介します。 int main() { ll N; cin >> N; multiset<string> S; set<string> roop_itr; for( ll i = 0; i < N; i++) { ll tmp; cin >> tmp; S.insert(tmp); roop_itr.insert(tmp); } # Sの中で最も書かれた文字列が何回書かれたかを保持する ll most = 0; # 一番多く書かれている文字の回数を探索 for(set<string>::iterator itr = roop_itr.begin(); itr != roop_itr.end(); ++itr) { if( S.count( *itr ) > most ) most = S.count( *itr ); } vector<string> ans; # 一番多く書かれている文字列を列挙する for(set<string>::iterator itr = roop_itr.begi

タイトルの通りARC98のC問題をC++で解いた話です。 問題のリンク 今回は累積和を用いて解きました。 累積和についてピンと来ない方は以下の記事が個人的におすすめです。 累積和を何も考えずに理解する: https://qiita.com/drken/items/56a6b68edef8fc605821 解法 今回求めたいものを少し言い換えると、 リーダーの左側にいるWを向いている人 + リーダーの右側にいるEを向いている人 が最小になるようにリーダーを決めると取ることが出来ます。 ということは、与えられたSの先頭からそれぞれリーダーにした場合を考えると解けます。 ただこの解法だとO(N^2)となってしまいTLEになってしまいます。 そこで累積和を用いました。 先頭からEを向いている人とWを向いている人をそれぞれ累積和をとってあげるとO(N*2)程度になるのでTLEを回避できます。 もう少し詳細に書きます。 先頭からEを向いている人をEast, 先頭からWを向いている人をWestという配列を用いて累積和を作っていきます。 (予めそれぞれの配列に初期値0を挿入しておく) 入力例に 5 WEEWW が来た場合、それぞれの配列の中身は、 East = [0, 0, 1, 2, 2, 2] West = [0, 1, 1, 1, 2, 3] になります。 そしてリーダーの左側にいるWを向いている人 + リーダーの右側にいるEを向いている人は、 East[一番最後] - East[リーダーの位置] + West[リーダーの位置-1] で表現することが出来ます。 自分の解答

タイトルの通りABC155 C問題をC++で解いた話です。 問題のリンク 今回は筆者が最近よくやるsetとmultisetを組み合わせた探索を説明していこうと思います。 問題 N枚の投票用紙があり、i(1 <= i <= N)枚目には文字列Siが書かれている。 書かれた回数が最も多い文字列を全て辞書順で小さい順に出力してください。 方針 Sの中で最も書かれた文字列が何回書かれたかを求める部分、 最も書かれた回数が多い文字列を列挙する部分の2回全探索をする。 制約 1 <= N <= 2 * 10^5 1 <= Siの長さ <= 10 問題点 どうやら通常のfor文だとTLEするらしい。 解決策 探索部分の計算量を削減する。 削減方法として先程述べたsetとmultisetを組み合わせた探索を紹介します。 int main() { ll N; cin >> N; multiset S; set roop_itr; for( ll i = 0; i < N; i++) { ll tmp; cin >> tmp; S.insert(tmp); roop_itr.insert(tmp); } # Sの中で最も書かれた文字列が何回書かれたかを保持する ll most = 0; # 一番多く書かれている文字の回数を探索 for(set ::iterator itr = roop_itr.begin(); itr != roop_itr.end(); ++itr) { if( S.count( *itr ) > most ) most = S.count( *itr ); } vector ans; # 一番多く書かれている文字列を列挙する for(set ::iterator itr = roop_itr.begin(); itr != roop_itr.end(); ++itr) { if( S.count( *itr