https://atcoder.jp/contests/past202109-open/tasks/past202109_a
https://atcoder.jp/contests/past202109-open/submissions/26585144
指定されていることを実装する問題。
取れる選択肢は、
「A + B - C」円（それぞれ頼んで割引する）
「D」円（セットを頼む）
の2択なので、この2択の小さい方を答えとすればいい。
C++ではmin関数というのがあり、引数のうち小さい方を返してくれるので、これを使うとスムーズ。
int A, B, C, D; //--------------------------------------------------------------------------------------------------- void _main() { cin >> A >> B >> C >> D; int ans = min(A + B - C, D); cout << ans << endl; }
https://atcoder.jp/contests/joi2022yo1a/tasks/joi2022_yo1a_d
https://atcoder.jp/contests/joi2022yo1a/submissions/26486427
宝箱を中心に考えてみよう。
とある宝箱を開錠するためには書かれている番号と同じ番号が書かれた鍵が存在する必要がある。
よって、すべての宝箱についてループを書いて、その中で対応する鍵があるかどうかを確認しよう。
これも同様にすべての鍵についてループを書いて、存在するものがあるかどうかを探せばいい。
今回は宝箱のループで100回のループ、鍵のループで100回のループを行ったので、全体で最大10000回のループを
行っていることになる。
鍵のループの部分はsetなどのデータ構造を使うことで、ループの回数を減らしてより高速に計算することが可能になる。
他にもソートを使ってうまくやる方法などもあるので、高速化の方法も考えてみるといいと思う。
より詳しく書くと今回の解法は計算量O(N2)であるが、O(NlogN)、O(N)まで改善ができる。
考えてみるといい。
int N, M, A[101], B[101]; //--------------------------------------------------------------------------------------------------- void _main() { cin >> N >> M; for (int i = 0; i < N; i++) cin >> A[i]; for (int i = 0; i < M; i++) cin >> B[i]; int ans = 0; for (int i = 0; i < N; i++) { bool ok = false; for (int j = 0; j < M; j++) { if (A[i] == B[j]) ok = true; } if (ok) ans++; } cout << ans << endl; }
https://atcoder.jp/contests/joi2022yo1a/tasks/joi2022_yo1a_c
https://atcoder.jp/contests/joi2022yo1a/submissions/26485238
文字種を数える問題なので、C++であればsetを使うのがオススメ。
setは同じ要素が入った場合でも1つにまとめてくれるので、全要素を入れても最終的には重複を除いた状態で格納してくれる。
なので、すべての文字をsetに入れて、中身の個数を持ってくると種類数が得られる。
これを3以上とそれ以外で答え分けをすればACできる。
int N; string S; //--------------------------------------------------------------------------------------------------- void _main() { cin >> N >> S; set<char> chars; for (auto c : S) { chars.insert(c); } if (3 <= chars.size()) cout << "Yes" << endl; else cout << "No" << endl; }
https://atcoder.jp/contests/joi2022yo1a/tasks/joi2022_yo1a_b
https://atcoder.jp/contests/joi2022yo1a/submissions/26485022
A地点からB地点を経由してC地点に移動するにはX+Y時間だけかかる。
判定したいのはZ時間30分以内に移動できるかということである。
ここで注意点があり、問題文をより正確に判定するのであれば、気持ちとしては「X+Y≦Z + 1/2」を判定したくなる。
コンピュータ上では小数を正確に扱うというのはやや難しく、条件判定をする際にもなるべく小数をなくす方がいい。
今回はX,Yはどちらも整数なので、X+Yも同様に整数となる。
よって、小数の1/2を考える必要はなく、「X+Y≦Z」と判定してしまって問題ない。
int X, Y, Z; //--------------------------------------------------------------------------------------------------- void _main() { cin >> X >> Y >> Z; if (X + Y <= Z) cout << 1 << endl; else cout << 0 << endl; }
https://atcoder.jp/contests/joi2022yo1a/tasks/joi2022_yo1a_a
https://atcoder.jp/contests/joi2022yo1a/submissions/26484859
C++では何かで割った余りを計算する場合に%という演算子を使う。
21で割った余りを求めたいなら% 21だし、10で割った余りなら% 10である。
C++以外でもこのような演算子はあるはずだ。「剰余」と言語名でgoogle検索してみよう。
もしこの問題が難しい場合は入門問題を一通りこなすのがいいと思う。
https://qiita.com/drken/items/fd4e5e3630d0f5859067#3-hello-world-----practice-contest-a-%E5%95%8F%E9%A1%8C%E3%81%AE%E3%81%BF
もし使っている言語が違う場合はこっちを参照してみよう。
https://qiita.com/drken/items/fd4e5e3630d0f5859067#c-%E4%BB%A5%E5%A4%96%E3%81%AE%E8%A8%80%E8%AA%9E%E3%81%A7
int X; //--------------------------------------------------------------------------------------------------- void _main() { cin >> X; int ans = X % 21; cout << ans << endl; }
https://atcoder.jp/contests/abc219/tasks/abc219_d
https://atcoder.jp/contests/abc219/submissions/26483767
あまりピンとこないかもしれないがDPで解ける。
初手でDPが思いついて試すとできたので、DPに至る過程は説明できない…
dp[i][tako][tai] := i番目の弁当まで買うかが確定していて、これまでのたい焼きの個数がtaiで、たこ焼きの個数がtakoである最小弁当個数
これで解く。重要な部分が、X,Y≦300であるという部分である。
状態として、たい焼き・たこ焼きの個数はX,Yより大きくなりうるが、X以上である個数は条件としてはすべて同一視しても問題ない。
よって、Xより大きい個数はすべてXであると丸めてしまうことにすると、たい焼き、たこ焼きの個数は0～X/Yということになる。
この前提を考えると、DPの状態数は300×300×300通りくらいになるので、状態数的にはメモリ/計算量に収まる。
これは、上限を適切に指定して丸めることで間に合うというテクであり、DPを行う上で状態を丸める良い手法である。
後は頑張って実装するだけ。
上限を指定する場合は更新時にminを使って超えたら最大値に置き換えるという感じにすると分岐が減って見栄えがいい。
int N, X, Y; int A[301], B[301]; int dp[301][301][301]; //--------------------------------------------------------------------------------------------------- void _main() { cin >> N >> X >> Y; rep(i, 0, N) cin >> A[i] >> B[i]; rep(i, 0, N + 1) rep(tako, 0, 301) rep(tai, 0, 301) dp[i][tako][tai] = inf; dp[0][0][0] = 0; rep(i, 0, N) rep(tako, 0, X + 1) rep(tai, 0, Y + 1) if (dp[i][tako][tai] < inf) { chmin(dp[i + 1][tako][tai], dp[i][tako][tai]); chmin(dp[i + 1][min(tako + A[i], X)][min(tai + B[i], Y)], dp[i][tako][tai] + 1); } int ans = dp[N][X][Y] < inf ? dp[N][X][Y] : -1; cout << ans << endl; }
https://atcoder.jp/contests/abc219/tasks/abc219_c
https://atcoder.jp/contests/abc219/submissions/26483284
実装問題。
C++であれば、特殊なソートは、比較関数を独自に作ることで実装が可能である。
2つの文字列が与えられたときに大小関係を判定するような比較関数を用意しよう。
通常であれば、charのまま大小比較すればそれがそのまま使えるのだが、今回は文字（文字コード）の順番と実際の順番が一致しないので、
文字を実際の順番に変換する必要がある。
自分はこれにはmapをつかって、mapping配列というのを用意した。
charを入れるとそれに対応した実際の順番が出てくるようになっている。
これを使って文字の先頭から大小比較をしていこう。
文字列のprefixがどちらも同じだった場合は文字数が少ない方が辞書順では早くなるので、
決まらなかったら文字数の昇順を条件として返してやればいい。
string X; int N; string S[50101]; //--------------------------------------------------------------------------------------------------- void _main() { cin >> X >> N; rep(i, 0, N) cin >> S[i]; map<char, int> mapping; rep(i, 0, 26) mapping[X[i]] = i; sort(S, S + N, [&](string a, string b) { int len = min(a.length(), b.length()); rep(i, 0, len) { int x = mapping[a[i]]; int y = mapping[b[i]]; if (x != y) return x < y; } return a.length() < b.length(); }); rep(i, 0, N) printf("%s\n", S[i].c_str()); }
