読者です 読者をやめる 読者になる 読者になる

夢追い人

"It takes a dreamer to make a dream come true."―Vincent Willem van Gogh

明日はPCK本選(僕はもうひとつの)

プログラミング

さすがにまともに問題解いたのが文化祭のライブコーディング以来とかそんな状態で3冠かかったPCKのもうひとつの本選出るのは、本選いってる先輩たちにも申し訳ないので少し練習。

0201

錬金マスターとかいうやつ。
メモ化再帰で余裕やん~とかいって管理簡単になるように自作ハッシュつくってTLE。
mapで素直にやったら0.00sの超時短でAC。
戒めのコメントアウト(ただ単に修正がめんどかっただけw)

// #include <cstdio>
// #include <iostream>
// #include <vector>
// #include <map>
// #include <algorithm>
// using namespace std;
// typedef long long ll;
// typedef pair<ll, int> P;
// map<string, int> hash;
// int key;
// int findkey(string str) {
//   if (hash.find(str) != hash.end()) return hash[str];
//   return hash[str]=key;
// }

// int n, m, k;
// P p[100];
// ll dp[100];
// vector<int> rec[100];
// string ins;

// ll dfs(int ks) {
//   if (rec[ks].size()==0) return dp[ks];
//   ll sum = 0;
//   for (int i=0; i<rec[ks].size(); i++) {
//     sum += dfs(rec[ks][i]);
//   }
//   if (sum < dp[ks]) dp[ks] = sum;
//   return dp[ks];
// }

// int main() {
//   while (scanf("%d",&n)) {
//     if (!n) break;
//     key=0;
//     for (int i=0; i<n; i++) {
//       cin>>ins>>p[i].first;
//       dp[i]=p[i].first;
//       p[i].second=findkey(ins);
//       key++;
//     }
//     scanf("%d",&m);
//     for (int i=0; i<m; i++) {
//       cin>>ins>>k;
//       int o = findkey(ins);
//       for (int j=0; j<k; j++) {
//         cin>>ins;
//         rec[o].push_back(findkey(ins));
//       }
//     }
//     cin>>ins;
//     int need = findkey(ins);
//     // sort(p, p+n);
//     ll ans = dfs(need);
//     printf("%lld\n",ans);
//   }
// }
#include <cstdio>
#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;
map<string, int> it;
map<string, vector<string> > rec;
int n, m, p, k;
string str;
int dfs(string s) {
  if (rec[s].size()==0) return it[s];
  int sum = 0;
  for (int i=0; i<rec[s].size(); i++) {
    sum+=dfs(rec[s][i]);
  }
  return it[s]=min(it[s], sum);
}
int main() {
  while (scanf("%d",&n)) {
    if (!n) break;
    it.clear(); rec.clear();
    for (int i=0; i<n; i++) {
      cin>>str>>p;
      it[str] = p;
    }
    scanf("%d",&m);
    for (int i=0; i<m; i++) {
      cin>>str>>k;
      string need = str;
      for (int j=0; j<k; j++) {
        cin>>str;
        rec[need].push_back(str);
      }
    }
    cin>>str;
    cout<<dfs(str)<<endl;
  }
}

0203

超単純だったのに全然ジャンプ台の先が障害物パターン考慮してないことにきづかず…
反省。でもパソコンを以前ほど使わなくなったおかげかよくわからないけど思考力が向上している気がする(気のせい)

#include <cstdio>
#include <cstring>
typedef long long ll;
int x, y;
ll dp[20][20];
int mp[20][20];
int main() {
  while (scanf("%d%d",&x,&y)) {
    if (!x&&!y) break;
    memset(dp, 0, sizeof(dp));
    memset(mp, 0, sizeof(mp));
    for (int i=0; i<y; i++) {
      for (int j=0; j<x; j++) scanf("%d",&mp[i][j]);
    }
    for (int i=0; i<x; i++) if (mp[0][i]!=1) dp[0][i]=1;
    ll res = 0;
    for (int i=0; i<y-1; i++) {
      for (int j=0; j<x; j++) {
        if (mp[i][j]==2&&mp[i+2][j]!=1) {
          dp[i+2][j]+=dp[i][j];
        } else if (mp[i][j]==0) {
          if (j-1>=0&&mp[i+1][j-1]==0) dp[i+1][j-1]+=dp[i][j];
          if (mp[i+1][j]!=1) dp[i+1][j]+=dp[i][j];
          if (j+1<x&&mp[i+1][j+1]==0) dp[i+1][j+1]+=dp[i][j];
        }
      }
    }
    for (int i=0; i<x; i++) res+=dp[y][i]+dp[y-1][i];
    printf("%lld\n",res);
  }
}

0204は初等幾何でできなかったので断念(ベクトル面倒w)

まぁ…明日がんばりませう。目指せ一位w

広告を非表示にする