0529

ダーツの問題です、面白かったですねえ、4本同時に投げるのを2本同時に投げるのを二回にすることで二部探索できる的な感じのアプローチで解けました。オーダーの計算がめんどかったとおもいきや意外と単純でした(枝刈りした再帰に比べれば計算できるよね)ってことでソースコード


#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

int main(void)
{
vector<int> twoThrow;
int n;
int m;
int point[1000];
int ans;

while (1){
twoThrow.clear();

scanf("%d%d", &n, &m);

if (n == 0){
break;
}

for (int i = 0; i < n; i++){
scanf("%d", &point[i]);
}


twoThrow.push_back(0);
for (int i = 0; i < n; i++){
twoThrow.push_back(point[i]);
for (int j = i; j < n; j++){
twoThrow.push_back(point[i] + point[j]);
}
}
sort(twoThrow.begin(), twoThrow.end());

int t;
ans = 0;
for (int i = 0; i < twoThrow.size(); i++){
vector<int>::iterator it = upper_bound(twoThrow.begin(), twoThrow.end(), m - twoThrow[i]);
if (it == twoThrow.begin()){
continue;
}
it--;
t = *it;
if (ans < t + twoThrow[i]){
ans = t + twoThrow[i];
}
}

printf("%d\n", ans);
}

return (0);
}

0220

なんか、小数点の2進数変換するだけ、２年の頃に崎ねえに習った固定小数点の二進数変換が初めて役に立った。ありがとう崎ねえ

#include <stdio.h>
#include <stdlib.h>

bool itob(int b, char res[])
{

for (int i = 0; i < 8; i++){
if ((b & (1 << (8 - i - 1))) != 0){
res[i] = '1';
}
else res[i] = '0';
}
res[8] = '\0';

return ((b & (~0xff)) == 0);
}

bool ftob(double f, char res[])
{

for (int i = 0; i < 4; i++){
f *= 2;

if (f >= 1.0){
res[i] = '1';
f -= 1;
}
else {
res[i] = '0';
}
}
res[4] = '\0';

return (f == 0);
}

int main(void)
{
double n;
int b;
double m;
bool flag;
char bans[100];
char mans[100];
char ans[200];

while (1){
scanf("%lf", &n);

if (n < 0){
break;
}

flag = true;

b = (int)n;
m = n - b;

flag &= itob(b, bans);
flag &= ftob(m, mans);

sprintf(ans, "%s.%s", bans, mans);

puts(flag ? ans : "NA");
}

return (0);
}

0221

なんか後輩が悩んでいた問題、実装だるかった、でもstd::list使ってすっきりかけたと思う、うん、すっきりかけた。追記：人の書いたコードの落ちるテストケース作るのは楽しいです(笑)

#include <stdio.h>
#include <list>
#include <stdlib.h>
#include <string.h>

using namespace std;

int main(void)
{
list<int> lst;
int n, m;
char say[10000][20];
list<int>::iterator it;
list<int>::iterator pit;

while (1){
scanf("%d%d", &n, &m);

if (n == 0) break;

lst.clear();

for (int i = 0; i < n; i++){
lst.push_back(i + 1);
}

for (int i = 0; i < m; i++){
scanf("%s", say[i]);
}

it = lst.begin();
for (int i = 1; i <= m; i++){
int cm;

if (lst.size() == 1){
break;
}

pit = it;
it++;

cm = 0;
if (i % 3 == 0){
cm--;
}
if (i % 5 == 0){
cm -= 2;
}

if (cm == 0){
if (i != atoi(say[i - 1])){
lst.erase(pit);
}
}
else if (cm == -1){
if (strcmp(say[i - 1], "Fizz") != 0){
lst.erase(pit);
}
}
else if (cm == -2){
if (strcmp(say[i - 1], "Buzz") != 0){
lst.erase(pit);
}
}
else if (cm == -3){
if (strcmp(say[i - 1], "FizzBuzz") != 0){
lst.erase(pit);
}
}
if (it == lst.end()){
it = lst.begin();
}
}


it = lst.begin();
printf("%d", *it++);
for (; it != lst.end(); it++){
printf(" %d", *it);
}
puts("");
}

return (0);
}

0200

駅の数が高々100なのでワーシャルフロイド法(ここ参照)で解いてみました。

#include 
#include 
#include 

#define min(x, y) ((x) < (y) ? (x) : (y))

int main(void)
{
    int cost[100][100];
    int time[100][100];
    int n, m;
    int k;
    
    while (1){
        for (int i = 0; i < 100; i++){
            for (int j = 0; j < 100; j++){
                cost[i][j] = time[i][j] = 100000000;
            }
        }
        
        scanf("%d %d", &n, &m);
        
        if (n == 0){
            break;
        }
        
        for (int i = 0; i < n; i++){
            int a, b, c, t;
            
            scanf("%d%d%d%d", &a, &b, &c, &t);
            a--;
            b--;
            cost[a][b] = cost[b][a] = min(cost[a][b], c);
            time[a][b] = time[b][a] = min(time[a][b], t);
        }
        
        for (int k = 0; k < m; k++){
            for (int i = 0; i < m; i++){
                for (int j = 0; j < m; j++){
                    cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j]);
                    time[i][j] = min(time[i][j], time[i][k] + time[k][j]);
                }
            }
        }
        
        
        scanf("%d", &k);
        for (int i = 0; i < k; i++){
            int a, b, r;
            
            
            scanf("%d%d%d", &a, &b, &r);
            
            a--;
            b--;
            
            if (r == 0){
                printf("%d\n", cost[a][b]);
            }
            else {
                printf("%d\n", time[a][b]);
            }
        }
    }
    
    return (0);
}

0557

なんか頻度を保存していく感じ

#include 
#include 
#include 

using namespace std;

int main(void)
{
    long long hist[100][21];
    int n;
    int form[100];
    
    scanf("%d", &n);
    for (int i = 0; i < n; i++){
        scanf("%d", &form[i]);
    }
    
    memset(hist, 0, sizeof(hist));
    
    hist[0][form[0]] = 1;
    for (int i = 1; i < n - 1; i++){
        for (int j = 0; j < 21; j++){
            if (hist[i - 1][j] > 0){
                if (j - form[i] >= 0 && j - form[i] <= 20) 
                    hist[i][j - form[i]] += hist[i - 1][j];
                if (j + form[i] >= 0 && j + form[i] <= 20)
                    hist[i][j + form[i]] += hist[i - 1][j];
            }
        }
    }
    
    cout << hist[n - 2][form[n - 1]] << endl;
    
    return (0);
}