京都大学プログラミングコンテスト(KUPC)参加記
8月6日に行われたKUPCにオンラインから参加してました。
結果は以下の通り。
順位 | ユーザ名 | A | B | C | D | E |
---|---|---|---|---|---|---|
73 | shirokurostone2 | 00:05 | 00:12 | 00:51 | - | (2) |
A - KUPC
文字列の中に'K','U','P','C'が何回現れるか数える問題。
素直に数えて最小値を出力しました。
stringをincludeし忘れてます。
#include <iostream> using namespace std; int main(void){ string str; int k, u, p, c; cin >> str; k = u = p = c = 0; for(int i=0; i<str.size(); i++){ if (str[i] == 'K') k++; else if (str[i] == 'U') u++; else if (str[i] == 'P') p++; else if (str[i] == 'C') c++; } cout << min(k, min(u, min(p, c))) << endl; return 0; }
B - 蝉
学校に行くまでに遭遇する蝉の最小値を求める問題。
動的計画法で蝉の最小値を更新していく方法で解きました。
後から見直すと、入力格納用とDP用で配列を2つ使っていたりして効率が悪いですね。
#include <iostream> #include <cstring> using namespace std; int main(void){ int h, w; cin >> h >> w; int semi[w][h]; int dp[w][h]; memset(dp, 0, sizeof(dp)); char c; for(int i=0; i<h; i++){ for(int j=0; j<w; j++){ cin >> c; semi[j][i] = c-'0'; } } for(int y=0; y<h; y++){ for(int x=0; x<w; x++){ if (x == 0 && y == 0){ dp[x][y] = semi[x][y]; } else if (y == 0){ dp[x][y] = dp[x-1][y] + semi[x][y]; } else if (x == 0){ dp[x][y] = dp[x][y-1] + semi[x][y]; } else{ dp[x][y] = min(dp[x][y-1], dp[x-1][y]) + semi[x][y]; } } } cout << dp[w-1][h-1] << endl; return 0;
C - しりとり
2文字までしか話せないAIとしりとりをしてAIを負かせる問題。
このような対話型の問題は初めてだったのですが面白いですね。
方針は末尾が同じ文字列を返答し続け、AIの自滅を待つ感じになっています。
#include <cstdio> #include <string> #include <cstring> #include <vector> #include <algorithm> using namespace std; int main(void){ vector<string> talked(100); char ai[11]; int al = 0; for(int i=0; i<50; i++){ if (i == 0){ printf("?a\n"); talked.push_back(string("a")); fflush(stdout); } else{ string ai = talked.back(); while(1){ al = (al+1)%(26*26); string next(" a"); next = next.replace(0, 1, 1, ai[ai.length()-1]); next = next.replace(1, 1, 1, (char)('a' + al/26)); next = next.replace(2, 1, 1, (char)('a' + al%26)); if (count(talked.begin(), talked.end(), next) == 0){ talked.push_back(next); printf("?%s\n", next.c_str()); fflush(stdout); break; } } } scanf("%s", ai); string last = talked.back(); if (count(talked.begin(), talked.end(), string(ai)) != 0 || last[last.size()-1] != ai[0] ){ break; } talked.push_back(string(ai)); } printf("!OUT\n"); fflush(stdout); return 0; }
algorithmをincludeするのを忘れコンパイルエラーを出したのはご愛嬌。
D - 列の構成
問題の条件に合うような数列を出力する問題。
A-Cを約1時間で解き、残りの時間をDとFに半分ずつ使いました。
Dは貪欲に先頭から求めていこうと考えていましたが、全問通る気がせず結局断念しました。
乱数で条件に合う数列を探し続ければ解けたそうです。なんてこった。
E - Fox Number
指定された範囲の中から条件に合う数字を数え上げる問題。
これも解法が浮かばずに馬鹿正直に素因数分解してみるソースを書いてみて、TLE出してました。
ちょっと難しい問題になると、どうしようもなくなるのはなんとかしたいですね。
まとめ
C問題が解けてから、残りの4時間ほとんど手が出ていない状態だったのでもう少し解きたかったです。
また、STLのメソッドについて忘れていたり、includeするのを忘れているヘッダがあったりとミスも目立ったので
解法だけではなくミス/不注意を減らせるように練習していきたいと思います。