kakecoder Tea Break 001参加記

kakecoderのtea001 - TOPに参加しました。

解答例ソースコードが公開されてないので一応置いておこうかと。

A:Happiness Number

互いに素なのでa×bで終わりです。
ただ、a*bがintには収まらないのでlong longを使いましょう。
殴れる人はlcm(最小公倍数)で殴れます。
C++の例

#include<iostream>
using namespace std;
int main(){
    long long a,b;cin>>a>>b;
    cout << a*b << endl;
    return 0;
}

Pythonの例

a,b=map(int,input().split())
print(a*b)

LCMを使う例

#include<iostream>
using namespace std;
typedef long long ll;
ll gcd(ll m, ll n) {//最大公約数
    if ((0 == m) || (0 == n)) return 0;
    // ユークリッドの方法
    while (m != n){
        if (m > n) m = m - n;
        else         n = n - m;
    }
    return m;
}
ll lcm(ll m, ll n) { //最小公倍数
    if ((0 == m) || (0 == n)) return 0;
    return (m * n / gcd(m, n));
}
int main(){
    ll a,b;cin>>a>>b;
    cout << lcm(a,b) << endl;
    return 0;
}

B:Happiness function

多項式関数がx軸を通るか判定する。
実はx軸の情報はいらないので、y軸の情報だけ持ってy[i]>0,y[i+1]<0 、
または y[i]<0,y[i+1]>0 を見ていく。
楽な計算方法として、y[i]*y[i+1]が負の場合を計算すると、上記と同じ条件分岐になる。
解答ソースコードはそちらを書いてます。

C++の例

#include<bits/stdc++.h>
using namespace std;
int main(){
    int T,P,Q;cin>>T>>P>>Q;
    vector<int> y(Q-P+1);
    for(int i=0;i<Q-P+1;i++){
        int x;cin>>x>>y[i];
    }
    int ans=0;
    for(int i=0;i<Q-P;i++){
        if(y[i]*y[i+1]<0) ans++;
    }
    if(ans>=T) puts("Yes");
    else puts("No");
    return 0;
}

Pythonの例

t,p,q=map(int,input().split())
y=[]
for _ in range(q-p+1):
  a,b=map(int,input().split())
  y.append(b)
ans=0
for i in range(len(y)-1):
  if y[i]*y[i+1] < 0:
    ans+=1
print('Yes' if ans>=t else 'No')

C:Happiness Festival

H×Wマスを(0,0)から(H,W)まで移動する。
移動先には、移動するのにコストがかかる場所があり、通るコストを最小化する必要がある。

こちらは、動的計画法(DP)初心者講座第1回のような内容で、貰うDPの一種です。
図(5分クオリティ)を使いながら考えてみましょう。
最初の行と列は番号です(0-indexed)。
各要素に入っている数字はこの場所まで到達するのに必要なコストをとりあえず 決めたものです。
これまでに求まったコストを用いて新しい(1,1)に到達するのに必要なコストを計算してみましょう。

貰うDPの図

図のように、(1,1)に移動する方法は(0,1)からと(1,0)からの2通りあります。
判断基準として、(0,1),(1,0)まで到達するのに必要なコストがあります。
勿論、コストの小さい方を取る方がよいので(0,1)から移動する方がいいでしょう。
この時、(1,1)に移動するときにコストがかかるかの計算を忘れないようにしましょう。
さて、今回は(1,1)の計算をしましたが、これをもっとさかのぼれば(0,0)から計算できそうですよね?ですよね?

具体的な方針を決めます。

1. 現在地から右方向、下方向に行けるか確認。
   
2. 行けるなら現在地まで行くのにかかったコスト+次の方向に行くために必要なコストを計算し、小さければ更新。
   
3. 次のマスに移動。1に戻る。
   これは、すべてのマスを探索するのでO(N²)で制約上十分高速です。(ビッグO記法についての解説は無しとします)
   

では実装してみましょう。
今回、計算用の配列dpは、要素の中身をすべてINF(とても大きい数字)を入れて初期化することで必ず1回は更新されるようにします。
C++の場合

#include<bits/stdc++.h>
using namespace std;
int main(){
    int h,w, c;
    cin >> h >> w >> c;
    vector<vector<int>> cost(h, vector<int>(w));
    for(int i=0;i<h;i++)for(int j=0;j<w;j++) cin >> cost[i][j];
    vector<vector<int>> dp(h, vector<int>(w,1e9));//配列の要素を10^9で初期化
    dp[0][0] = 0;
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
        if (i == 0 && j == 0)continue;//何もしない
        else if (i == 0) dp[i][j] = min(dp[i][j], dp[i][j - 1]) + cost[i][j];//上からしか貰えない
        else if(j==0) dp[i][j] = min(dp[i][j], dp[i-1][j]) + cost[i][j];//左からしか貰えない
        else dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + cost[i][j];
        }
    }
    cout << dp[h - 1][w - 1] * c << endl;//最後にcをかけ忘れないように!
    return 0
}

Pythonの場合

h,w,c=map(int,input().split())
cost = [list(map(int,input().split())) for i in range(h)]
dp = [[10**9] * w] * h
dp[0][0] = 0
for i in range(h):
  for j in range(w):
    if i == 0 and j == 0:
      continue;#何もしない
    elif i == 0:
      dp[i][j] = min(dp[i][j], dp[i][j - 1]) + cost[i][j];#上からしか貰えない
    elif j==0:
      dp[i][j] = min(dp[i][j], dp[i-1][j]) + cost[i][j];#左からしか貰えない
    else:
      dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + cost[i][j];
print(dp[h-1][w-1] * c)

感想

問題の難易度がお茶の種類でオシャレだった。
問題も茶色付近でいい感じの難易度だったので第2回以降も時間が合えば参加したいなぁと思った。
@earlgray283_Cさん運営ありがとうございました!


追記:何とは言いませんが貴音のPをしてます。

持ってません。助けて

(フェス限は4凸してます)