はじめに
お茶の水女子大学競技プログラミングサークルO-tips所属の立田です。
学園祭に出展しよう！と思い申し込んだはいいものの何して良いかわからず、気がついたらコンテストを開いていました。
解説と作問小噺をこちらのnoteにてご紹介させていただこうと思います。
お茶大の小ネタをたくさん仕込んだので、興味のある方は背景セクションをご覧ください。
徽音祭に来てくださった方々、コンテストに参加してくださった方々に感謝を申し上げます。至らぬ点も多かったですが、楽しんで頂けたようであれば幸いです。
また、今回のコンテストはMOFE ( https://mofecoder.com ) さんのご協力のおかげで開催することができました。この場をお借りしてお礼を申し上げます。
コンテストはこちらからご覧ください。
A - 418
背景
問題の元ネタはステータスコードの418です。お茶大生はお茶にちなんだ命名をしがちです。
解法
if文で入力によって分岐することで正答できます。
解答例(C++)
#include<bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
if(n==200){
cout << "OK" << endl;
}else if(n==202){
cout << "Accepted" << endl;
}else if(n==418){
cout << "I\'m a teapot" << endl;
}else{
cout << "unknown" << endl;
}
}
B - K-chan
背景
語尾の"なの〜"が特徴的な架空のマスコットキャラクター・Kちゃんについての問題です。
ここで、本問とは関係ないですが、こちらのX(Twitter)アカウントを紹介しておきます。
https://twitter.com/kichan_kiinsai
偽Kちゃん「キーッキッキッキ！徽音祭が楽しみキイね〜！」
解法
語尾、つまり入力の後ろから5文字を調べると良いです。
1文字ずつ調べてもいいですが、C++なら部分文字列、Pythonならスライスを活用すると簡単に書くことができます。
解答例(C++)
#include<bits/stdc++.h>
using namespace std;
int main(){
string S;
cin >> S;
/* 部分文字列を作成 */
int l = S.length();
string ends = S.substr(l-5, 5);
/* 語尾を調べる*/
if(ends!="nano~"){
cout << "Fake" << endl;
}else{
cout << "Real" << endl;
}
}
C - Don
背景
情報科学科の一部の層からコンスタントな支持を得ている海鮮丼店をイメージしました。
https://sasafune.co.jp/shop/?_id=1277
Yes か No かで答えるのではなく o か x かで答える問題なのは店名を意識してのことです。
解法
大きく2パターンの方針があります。
- $X$ 円でいくつ買えるか
- $Y$ 個買うのに何円必要か
今回は後者で解いてみます。
以下のような流れで計算をすることで、必要な金額を求めることができます。最後にそれが $X$ 円以下になるか判定すると良いです。
解答例(C++)
#include<bits/stdc++.h>
using namespace std;
int main() {
/* 入力を受け取る */
long long X, Y, A, B, C;
cin >> X >> Y;
cin >> A >> B >> C;
// Y個以上買った時の金額
long long cost = 0;
/* 必要な金額を調べる */
// 1つずつ買った方がまとめて買うより安い場合
if(A*B<=C){
// Y個買う
cost = A*Y;
}else{
// Y個を越さない様にセットを買うと何セットになるか？
int bought = Y/B;
cost += C*bought;
// セットから個数に直す
bought *= B;
// 不足分を1つずつ買うのと
// B個セットを1つ買うのではどちらが安いか
if(A*(Y-bought)<C){
// 足りない数だけ買う
cost += A*(Y-bought);
}else if(bought<Y){
// 不足している時のみもう1セット買う
cost += C;
}
}
// Y個買うのに必要な金額がX円以下の場合にはoを出力
if(cost<=X){
cout << "o" << endl;
}else{
cout << "x" << endl;
}
}
D - Tea Party 1
背景
こちらはお茶を絡めた以外で元ネタは特にないです。
強いて言えば同じコンテストで1, 2とナンバリングされてる問題があるのに少し憧れがあったからです。
解法
C++でいう map 、Pythonでいう辞書型のように、文字列から対応する数字が取り出せるデータ構造を使用すると集計できます。
解答例(C++)
#include<bits/stdc++.h>
using namespace std;
int main() {
int N;
cin >> N;
/* mapを作る */
map<string, int> mp;
/* 集計 */
for(int i=0; i<N; i++){
string s;
cin >> s;
// anythingの場合は集計しないで次へ
if(s=="Anything") continue;
mp[s]++;
}
/* 一番多かったものを表示 */
string max_key;
int max_count = 0;
// map内の全ての要素について、second(個数)が最大のものを探す
for(const auto& pair : mp) {
if(pair.second > max_count) {
max_key = pair.first;
max_count = pair.second;
}
}
cout << max_key << endl;
}
E - Diligent Student
背景
お茶大のでっけー建物・徽音堂をモチーフにした問題です。
もしかしたら本館と呼ぶ方が正しいのかもしれませんが、建物の名前がかっこいいので徽音堂のままです。
1日の滞在時間という文言にすると大きなケースで日付が変わってしまうことを思い出たので、とりあえず一日を ${10^{18}}$ 分にしまいました。
解法
$B_i$ 階から $B_{i+1}$ 階へと移動する際に、例えば $B_i<B_{i+1}$ の時に $A_{B_i}+A_{B_{i+1}}+\cdots +A_{B_{i+1}}$ のように、毎回足し合わせを行うと計算量が増えてしまいます。
これは累積和を取ることで解決できます。事前に1からK階について、1階からかかる時間を求めておきます。
この時、$B_i$ 階から $B_{i+1}$ 階へと移動するのにかかる時間、もしくは$B_{i+1}$ 階から $B_{i}$ 階へと移動するのにかかる時間は、
(1階から $B_{i+1}$ 階までにかかる時間)-(1階から $B_{i}$ 階までにかかる時間)の絶対値
のように表すことができます。
解答例(C++)
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
/* 階の情報を受け取る */
ll K;
cin >> K;
vector<ll> A(K+1);
// from1[i]: 1階からi階までにかかる時間
vector<ll> from1(K+2);
for(int i=1; i<K; i++){
cin >> A[i];
from1[i+1]=from1[i]+A[i];
}
/* 授業にかかる時間を計算する */
ll Q;
cin >> Q;
ll ans = 0; // 答え
ll now = 1; // 今いる階
for(int i=0; i<Q; i++){
ll B, T;
cin >> B >> T;
// now階からB階までにかかる時間
// = (1階からB階までにかかる時間)-(1階からnow階までにかかる時間)の絶対値
ans += abs(from1[B]-from1[now]);
// B階に移動
now = B;
// 授業にかかる時間
ans += T;
}
// 1階まで戻る
ans += from1[now];
cout << ans << endl;
}
F - Yakitate
背景
生協で定期的に売られている焼き立てクッキーをモチーフにした問題です。
発売当初よりは手に入りやすくなりましたが、いまだに大人気です。ほんとに $10^{12}$ 枚焼いて欲しい。
余談ですが、徽音祭前日準備の日には私の目の前で売り切れました。
解法
典型問題からのオマージュです。値を決め打つタイプの二分探索です。
詳しくは以下の問題を参考にしてください。
冷めた枚数が $X$ 枚以下で食べられるか？についての二分探索になっています。
地点 $i$ では、最初に $Si$ 枚、一分で $Ti$ 枚冷めることを利用すると、$X$ 枚冷めるのは何分後か？という制限時間が求められます。
$N$ までの全ての地点の制限時間を求め、短い順に巡って全ての生協に制限時間内でたどり着けるかを調べることで、冷めた枚数が $X$ 枚以下で食べられるか？という判定が可能になっています。
解答例(C++)
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
ll N; // グローバル変数にする
// 一度に食べる焼き立てでないクッキーの枚数がn枚以下にできるか
bool check(ll n, vector<ll>&S, vector<ll>&T){
// それぞれの生協でのタイムリミットを求める
vector<ll> time_limit(N);
rep(i,N){
// 今S[i]枚が冷めている
// tが1増えるとT[i]枚増える
// → (n-S[i])/T[i]+1分にn枚を超える
// e.g.) S=5, T=3だとすると
// 5 8 11 ...
// 5枚だとすると、超えるのはi=1の時
// 7枚だとすると、超えるのはi=1の時
// 8枚だとすると、超えるのはi=2の時
// 最初からn枚より多く冷めている時は不可
if(n<S[i]) return false;
time_limit[i] = (ll)(n-S[i])/T[i]+1;
}
// 時間が短い順に巡り、全てを制限時間内に回れるか
sort(all(time_limit));
rep(i,N){
// i個目の生協にtime_limit[i]を過ぎてしまった場合
if(time_limit[i]<=i) return false;
}
return true;
}
int main() {
cin >> N;
vector<ll> S(N);
vector<ll> T(N);
rep(i,N){
cin >> S[i] >> T[i];
}
ll left = -1, right = LLONG_MAX-1;
// (left, right]で候補が1つより多い場合
while(right-left>1){
ll mid = (left+right)/2;
if(check(mid, S, T)){
// 答えはmid枚以下にできる
right = mid;
}else{
// 答えはmid枚より多い
left = mid;
}
}
cout << right << endl;
}
G - Tea Party 2
背景
こちらも元ネタは特にないです。
これは個人的に好きな解法なので入れました。以下の問題なども近いと思います。
解法
DP（動的計画法）です。
$i$ 個目が運ばれてきた時に、最後に口にしたものが紅茶の場合とマカロンの場合、それぞれの最大値を保持して行きます。
手順を詳しく書くと、以下のようになります。
まず、二次元配列 $dp$を用意します。このdpは、2要素が $N+1$ 個並んでいるようなイメージで、
- dp[0][i]: i個目に紅茶を飲んだ時の美味しさの最大値
- dp[1][i]: i個目にマカロンを食べた時の美味しさの最大値
のような値を格納していくことにします。
${i+1}$ 回目について、最後に食べたものが紅茶であるときの美味しさの取りうる最大値は、以下のいずれかとなります。
- ${i+1}$ 回目で何も食べない時の、${i}$ 回目で最後に口にしたものが紅茶であるときの美味しさの取りうる最大値
- ${i}$ 回目で最後に口にしたものがマカロンであるときの美味しさの取りうる最大値に、${i+1}$ 回目で紅茶を飲んだ時
これを、以下のような式で書くことができます。
$${dp[0][i+1]=max(dp[0][i],dp[1][i]+s[i])}$$
マカロンについても同様な式を書くことができます。
$${dp[1][i+1]=max(dp[1][i],dp[0][i]+s[i])}$$
こうすることで、最終的な答えは
$${max(dp[0][N], dp[1][N])}$$となります。
解答例(C++)
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ll N;
cin >> N;
vector<ll> tea(N+1);
vector<ll> macaron(N+1);
for(int i=1;i<=N;i++){
cin >> tea[i] >> macaron[i];
}
vector<vector<ll>> dp(2, vector<ll>(N+1));
// dp[0][i]: i個目に紅茶を飲んだ時の美味しさの最大値
// dp[1][i]: i個目にマカロンを食べた時の美味しさの最大値
for(int i=1; i<=N; i++){
// i回目に紅茶を飲む時の最大値
dp[0][i] = max(dp[0][i-1], dp[1][i-1]+tea[i]);
// i回目にマカロンを食べる時
dp[1][i] = max(dp[1][i-1], dp[0][i-1]+macaron[i]);
}
cout << max(dp[0][N], dp[1][N]) << endl;
}
H - Caretaker
背景
お茶大にはお茶猫と呼ばれる猫がいます。人懐っこくて可愛いです。
あとは順列が好きなので。
解法
$N\leq 11$ という条件より、2から $N$ についての全ての巡り方を試しても制限時間に間に合います。
これは、順列を使うと簡単に全要素が列挙できます。
具体的には、2から $N$ までの順列について、何文字目かと何番目に行くかを対応させることで全ての巡回を求められます。
C++なら next_permutation を利用すると簡単に順列が作成できます。
解答例(C++)
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ll N;
cin >> N;
vector<vector<ll>> V(N+1, vector<ll>(N+1));
for(int i=1; i<=N; i++){
for(int j=1; j<=N; j++){
cin >> V[i][j];
}
}
vector<ll> order(N-1);
for(int i=0;i<N-1;i++){
order[i]=i+2; // 2以降
}
// order = [2, 3, ..., N]のN-1個
ll ans = LLONG_MAX; // 十分大きな値にしておく
do {
ll dist = 0; // 距離
ll now = 1; // 現在地点
for(int i=0;i<N-1;i++){
// 地点now → 地点order[i]へ
ll next = order[i];
dist += V[now][next];
now = next;
}
ans = min(dist, ans); // より短いスコアが得られたら更新
} while (next_permutation(order.begin(), order.end()));
cout << ans << endl;
}