ABC290感想（C, D）
C問題
入力を読み取るときに，setのデータ構造で読み取るようにすれば，読み込んだ段階でソートされていることになるので，これは一つテクニックとして覚えておきたい．std::setは任意の値を探したい時に，見つけたらそのインデックスを返すfindという関数を持っている．もしそのデータ構造の中に含まれていなかったらA.end()を返すのでそれを今回も利用した．また，std::vectorで似たようなことをやりたかったら，std::find(A.begin(), A.end(), i) == A.end()のように書く．その際，#include <algorithm>を忘れずに．
#include <iostream> #include <vector> #include <set> int main() { int N, K; std::cin >> N >> K; // set型にしておくことで，最初からソートされる std::set<int> A; for (int i = 0; i < N; i++) { int a; std::cin >> a; A.insert(a); } // std::sort(A.begin(), A.end()); // Kが答えの時は，falseのままでKより小さい値が全て含まれる． for (int i = 0; i < K; i++) { if (A.find(i) == A.end()) { std::cout << i << std::endl; return 0; } } std::cout << K << std::endl; return 0; }
D問題
自分的にはかなり難しかったが，緑レベルの問題なのか．．．という感じ．与えられた条件の操作を素直にやるだけだとTLEでうまくいかない．そこで上手い方法を考えるわけだが，最大公約数をうまく使うことで，O(1)で求めたい値を求められる．また，long long型にするのもポイントで，intだとオーバーフローによりエラーを出す．
#include <iostream> #include <vector> int mygcd(int a, int b) { if (b == 0) return a; return mygcd(b, a%b); } int main() { int T; std::cin >> T; for (int i = 0; i < T; i++) { int N, D, K; std::cin >> N >> D >> K; K--; int g = mygcd(N, D); int times = N / g; std::cout << (long long)D*K % N + K / times << std::endl; } return 0; }
ABC289感想(C, D, E)
C問題
bit全探索で解く問題．2m-1の選び方がある問題だから，bit全探索で解く問題だとは思ったが，部分集合を足し合わせた集合に1~Nが全て含まれているかどうかを判別するアルゴリズムが思いつかなかった．
解答を見て納得した．std::setというライブラリを使ってそこに値をinsertで格納していくことでそれを実現している．std::setというライブラリは，そこに格納された値は自動的にソートされ，さらに重複した値は新しく格納されないという特徴を持っている（multisetというライブラリなら重複を許容する）．つまり，部分集合に含まれる値を全てset配列に格納していき，その配列の長さがNになるかどうかで判別問題を解いている．
#include <iostream> #include <vector> #include <set> int main() { int N, M; std::cin >> N >> M; std::vector<std::vector<int> > C; for (int i = 0; i < M; i++) { int c_num; std::vector<int> a_vec; std::cin >> c_num; for (int i = 0; i < c_num; i++) { int tmp; std::cin >> tmp; a_vec.push_back(tmp); } C.push_back(a_vec); } int result = 0; for (int i = 0; i < (1 << M); i++) { std::set<int> S; for (int j = 0; j < M; j++) { if ((i >> j) & 0b1) { for (auto& v: C[j]) S.insert(v); } } if (S.size() == N) result++; } std::cout << result << std::endl; return 0; }
D問題
dpで解くことはわかったが，二次元だと勝手に思い込んだせいで，メモリオーバー・時間オーバーでずっと通らなかった．縦軸を回数で取っていたが，全くそうする必要がないことに気づき，一次元で実装し直したら通った．ただ以下の自分の実装だと，初期値の0, 餅があって通れない段を1, 通れる段を2としていて，3種類も使う必要がないのではと思っていて，解答の実装を確認したら，最初に1で初期化した後に餅がある段は0にしている．これはどうせそれぞれの段について改めて調べていくから初期値は1にして問題ないという魂胆．
#include <iostream> #include <vector> int main() { int N, M; std::vector<int> A; std::vector<int> B; int X; std::cin >> N; for (int i = 0; i < N; i++) { int tmp; std::cin >> tmp; A.push_back(tmp); } std::cin >> M; for (int i = 0; i < M; i++) { int tmp; std::cin >> tmp; B.push_back(tmp); } std::cin >> X; // 2=ok, 1=no, 0=first std::vector<int> dp(X+1, 0); for (auto &val: B) { dp.at(val) = 1; } // initialize dp.at(0) = 2; for (int i = 1; i < X+1; i++) { if (dp.at(i) == 1) continue; for (auto &val: A) { if (i - val >= 0 && dp.at(i-val) != 1) { if (dp.at(i-val) == 2) { dp.at(i) = 2; } } } } if (dp[X] == 2) std::cout << "Yes" << std::endl; else std::cout << "No" << std::endl; return 0; }
E問題
二つの座標を持ってして一つの状態として，それを遷移させてBFSを行うという方法．完全に解法がわからず解答を見てから実装をした．遷移可能な状態は全て探索しているので，計算量が大きくなると思いきや，意外とそこまで大きくはならないというのもポイントかも．計算量の議論も厳密にできるようになりたい．
#include <iostream> #include <vector> #include <queue> #include <limits> #define myprint(st) std::cout << st << std::endl; const int inf = std::numeric_limits<int>::infinity(); int main() { int T; std::cin >> T; for (int i = 0; i < T; i++) { int N, M; std::cin >> N >> M; std::vector<int> C(N); for (int j = 0; j < N; j++) { std::cin >> C.at(j); } // 可変長のベクトルを要素にもつマトリックスを作る．データ構造に関するポイント． std::vector<std::vector<int> > Matr(N, std::vector<int>(0)); for (int j = 0; j < M; j++) { int u, v; std::cin >> u >> v; // 頂点のnumberが実際の値から1を引いたものだから． Matr.at(u-1).push_back(v-1); Matr.at(v-1).push_back(u-1); } std::queue<std::pair<int, int> > A; A.push(std::make_pair(0, N-1)); std::vector<std::vector<int> > dist(N, std::vector<int>(N, -1)); dist.at(0).at(N-1) = 0; while (A.size() > 0) { int a, b; a = A.front().first; b = A.front().second; A.pop(); int d = dist[a][b]; for (auto &val_a: Matr.at(a)) { for (auto &val_b: Matr.at(b)) { if (C.at(val_a) == C.at(val_b) || dist.at(val_a).at(val_b) != -1) continue; A.push(std::make_pair(val_a, val_b)); dist[val_a][val_b] = d+1; } } } std::cout << dist[N-1][0] << std::endl; } return 0; }
ABC128 (C問題) bit 全探索
探索系の問題をやりたくてこのサイトを見ていた。そしてbit全探索に馴染みがなかったので、今回はABC128のC問題に取り組んだ。 問題設定が自分にとっては複雑で、まずはこれを理解するのに時間がかかった。競プロには迅速な情報処理能力も求められていると改めて実感した。bit 全探索のbit[]配列に0 or 1の値を詰めていくところは先のサイトを参照した。そして以下のコードを書き、見事ACすることができた。switchは1~Nであるが、配列は0~N-1のインデックスと対応していることを忘れていて割とデバッグに時間がかかってしまったので、そこは反省。
#include <iostream> using namespace std; int main() { int N, M; cin >> N >> M; int k[M]; int s[N][M]; for (int i = 0; i < M; i++) { cin >> k[i]; for (int j = 0; j < k[i]; j++) { cin >> s[j][i]; } } int p[M]; for (int i = 0; i < M; i++) { cin >> p[i]; } int ans = 0; for (int i = 0; i < (1<<N); ++i) { int bit[N]; int result = 0; // ここでbit[]配列に0,1を詰めていっている // Divで割ることでその桁のbitがわかる for (int j =0; j < N; j++) { int Div = (1<<j); bit[j] = (i / Div) % 2; } for (int j = 0; j < M; j++) { int tmp = 0; for (int q = 0; q < k[j];q++) { // ここの-1を忘れない！ tmp += bit[s[q][j]-1]; } if (tmp % 2 == p[j]) result++; } if (result == M){ ans++; } } cout << ans << endl; return 0; }
メモ
もはや競プロとは全く関係ないが今日学んだことがあるので、それについて。
gitにはインタラクションモードというものがあり、細かい操作はインタラクティブに行った方が楽な場合がありそう。例えばステージングする時、git add -iとすることで、インタラクティブにステージングの操作が行える。ファイル毎のステージングやパッチ毎のステージング（つまり同じファイルであっても変更箇所ごとにステージングするか否かを決めることができる）なども簡単に行えるようだ。詳しくはここを参照。
それと高速逆平方根(fast inverse square root)についての話を聞く機会があったのでメモ。詳しくはこれを参照すると良い。こんな簡単に実装できてしまうのかと驚いた。これを思いつくのは凄すぎる。プログラミングにおけるニュートン法のあり方・ユースケースをあまり理解していないので、勉強する必要性を感じた。
ABC281(C問題) 感想
本日はABC281のC問題について。
以下が私が最初に書いたコード。まずこれはセグフォで通らなかった。理由としては、ベクトルの要素数を定義していないのに関わらずA[i]のようにベクトル要素にアクセスしてしまっているからである。そこでstd::vector<int> A(N)のように要素数を決めてしまうのが良い。ただ、今回は新しく配列に要素を追加するというようなことがないので、ただの配列を用いるだけの方がスマートだった気がする。
#include <iostream> #include <vector> using namespace std; int main() { int N, T; cin >> N >> T; std::vector<int> A; int total_time = 0; for (int i = 0; i < N; ++i) { cin >> A[i]; } for (int i = 0; i < N; ++i) { total_time += A[i]; } cout << A[0] << endl; int tmp = total_time % T; int song_num = 0; int time_from_start = 0; for (int i = 1; i <= N; ++i) { if (A[i-1] > tmp) { song_num = i; time_from_start = tmp; break; } tmp -= A[i-1]; } cout << song_num << " " << time_from_start << endl; return 0; }
ただベクトルの要素数を決めただけだと通らなかった。そこでこの似たような間違いをした人がどのように修正してACしたかを教えてくれる素晴らしいサイト(https://atcoder-companions.kakira.dev/)を用いて自分の解答を分析した。するとどうやら型の問題で、intとしているのがおかしいみたい。実際問題のそれぞれの整数の範囲を確認する。すると1≤A[i]≤109, 1≤T≤1018 という条件を確認することができる。int型は32bitで、大体2*109程度までを符号付きで表せるだけであるので、オーバーフローしてしまう。そこで、Tを64 bitのlong long型にしてあげる必要がある。そうして見事以下のコードでACした（以下ではA[i]もlong long型にしているが本来そうする必要ない）。
#include <iostream> #include <vector> using namespace std; using ll = long long; int main() { ll N, T; cin >> N >> T; std::vector<ll> A(N); ll total_time = 0; for (int i = 0; i < N; ++i) { cin >> A[i]; total_time += A[i]; } ll tmp = T % total_time; ll song_num = 0; ll time_from_start = 0; for (int i = 1; i <= N; ++i) { if (A[i-1] > tmp) { song_num = i; time_from_start = tmp; break; } tmp -= A[i-1]; } cout << song_num << " " << time_from_start << endl; return 0; }
ABC281 (A, B) 感想
お久しぶりです。ちょっと忙しくて投稿ができていませんでした。 年末ということもあって、街の空気も師走の忙しさやクリスマスに対する晴れやかな気持ち、お正月に向かう穏やかな気持ちなどが入り混じったような感じですが、自分はやっぱり卒論とプロジェクトの方が忙しくてそれどころではないという感じです。 そんな中今日からは、再び毎日投稿をとりあえず12/31までを目標に再開しようと思います。そして投稿内容は競プロにします。自分が書いたコードや感想、学んだことをざっくばらんに書き連ねていく予定です。どうぞお付き合いください。
ABC 281
A問題
これは流石にA問題なので流石に簡単でした。言及はしません。
#include <iostream> using namespace std; int main() { int N; cin >> N; for (int i = N; i >= 0; i--) cout << i << endl; return 0; }
B問題
文字列を扱う問題ですが、文字列の長さが決まっているので、もっと愚直に「2文字目から7文字目までを取り出して、文字列から数値に変換する」のような実装の方が良かったような気がします。全て文字列で扱っているため100000~999999を判別するのに、最上位桁に留意する必要があるため関数を二つも用意する羽目になってしまっています。最初がまた、string型を使いましたが、char*で扱った方がiteratorなども出てこず簡単だったように感じます。
ただここで一つ学びだったのが、string型のiteratorに要素参照の*をつけると、char型が返ってくることがわかりました。勝手にstring型のサイズ1の要素が返ってくると思っていたので、これは良い学びになりました。以下がコードです。
#include <iostream> #include <string> using namespace std; bool isUppercase( char s) { if (s >= 'A' && s <= 'Z') return true; return false; } bool isNum( char s) { if (s >='0' && s <= '9') return true; return false; } bool isNumEx0( char s) { if (s >='1' && s <= '9') return true; return false; } int main() { string S; cin >> S; if (S.size() != 8) { cout << "No" << endl; return 0; } bool flag = true; for(auto st = S.begin(); st != S.end(); ++st) { if (st == S.begin() || st == S.end()-1) { if (!isUppercase(*st)) { flag = false; break; } } else { if (st == S.begin()+1) { if (!isNumEx0(*st)) { flag = false; break; } } else { if (!isNum(*st)) { flag = false; break; } } } } if (flag) cout << "Yes" << endl; else cout << "No" << endl; return 0; }
1週間のまとめ 2022/11/06
今週に書いた記事について振り返る。
この記事で最後に静的リンクに失敗して、次の記事では静的リンクに成功している。この二つの違いとしては、前者はprintf関数を標準ライブラリから借用して使おうとしているのに対して、後者は自前のライブラリを使っているという点である。そのため、前者のエラー内容としては、libcrt0.oというファイルが見つからないというエラーだが、実際は記事に書いた通りprintf関数を含んでいる静的ライブラリがない、もしくはそれが存在しているライブラリのパスを指定できていないからである気がする。
今週もお疲れ様でした！
ExpressのsendFile()とrender()の違い
家庭教師でExpressを用いてWebアプリ制作の指導をしているのだが、renderとredirectが出てきて、それらの違いが何かと聞かれると説明するのが難しいし、実際その二つで異なる挙動を示すので、今回まとめてみることにした。
まず以下のようなコードを想定する。説明用に簡単にして余計なコードは消したので、これだけだと動かないと思われる。
const express = require('express'); const session = require('express-session'); const app = express(); app.get('/login', (req, res) => { //下のどちらかを実行 // res.render('index'); // res.sendFile('index.html'); }); app.use((req, res, next) => { if (req.session.username) { next(); } else { res.redirect('/login'); } });
まず、app.useとはミドルウェア関数を定義するもので、このミドルウェア関数は引数にパスを指定しないと、アプリケーションにアクセスがあるたびにロードして実行される。例えば、以下のように書くと、/user/:idにアクセスされた時にだけ、実行されるミドルウェア関数である。next();という関数は、次のミドルウェア関数（定義された順に実行される）に実行権限を渡す関数で、基本的にはミドルウェア関数では最後に実行する必要がある。例外として、これ以降のミドルウェア関数を無視する場合、next('route')と書く。
app.use('/user/:id', (req, res, next) => { console.log('Request Type:', req.method); console.log('ID:', req.params.id); next(); })
またミドルウェア関数は定義された順番に実行されるので、コード内のどこに配置するかは重要となってくる。
話を戻すと、最初の例のapp.useで行っている処理としては、セッションにusernameの情報が入っていれば、next()関数を実行し、そうでないとlocalhost:3000/loginに対してredirectするという処理だ。つまりログインする前はサービスのページにはアクセスできないとするサービスを作る上では当たり前の処理だ。
ここで問題なのが、redirectした後だ。ここでredirectすると上のapp.getでGETメソッドが走る。静的なindex.htmlファイルを表示したいのだが、選択肢としてコメントアウトした二つが考えられる。
まず私自身res.sendFile('index.html');を書いた。これで実行できると思ったのだが、リダイレクトが繰り返されるというエラーが出た。res.send()を使って引数に直接htmlファイルを書くと正しく実行することができたのだが、sendFileにするとうまく実行できない。最初はなぜかよくわからなかったが、res.sendFileが実行されるたびにミドルウェア関数が実行されて、再びリダイレクトされるということが繰り返される原因ではないかと思った。
今度は、res.render('index');と書いて実行してみた。htmlファイルを想定して正しく実行させるために以下のコードを必要とした。
// view engine setup as html // https://stackoverflow.com/questions/17911228/how-do-i-use-html-as-the-view-engine-in-express app.set('views', path.join(__dirname, 'view')); // ここで静的ファイルの場所を指定している。 app.engine('html', require('ejs').renderFile); app.set('view engine', 'html'); // 静的ファイルが格納されているディレクトリを指定 app.use(express.static('view'));
これによって正しく実行された。どうやらミドルウェア関数がこの場合は実行されないっぽい。renderで行われていることとしては、テンプレートエンジンを使用してファイルをパースして、htmlファイルを出力しているようだ。node.js - Express.js sendfile() vs. render() - Stack Overflow によるとhtmlファイルを扱っている場合は、出力結果が同じになるようだが、sendFileではミドルウェア関数が実行され、renderではミドルウェア関数が実行されないという違いがあるように思われる。
しかし重要なことに気づいた。それはrender()を使用すると、画面の遷移の際にURLを変えることができないという点だ。これはだいぶ困るので、やはりsendFile()を使った無限にリダイレクトされない方法があるのだろうか。なんとなく定義する順番な気がするが真相はわからない。
