Toy と帽子と ADP BE

主にプログラミングに関わる話をゆるくエモくやっていきます

AtCoder Beginner Contest 169

4完3WA。落ち着け。

各問題

A - Multiplication 1

掛け算を、します。

B - Multiplication 2

まず、0が一つでもあるときは絶対0なので0を出力します。サンプルにもあるで大丈夫でしょう。(優しい・・・)

で、順次掛けていくわけですが、10^18を超えてはいけないのでチェックする必要があります。

ここで、そこまでの積にさらにAを掛けたものでチェックしようとすると、(64ビット整数だと)オーバーフローの可能性があるので、式変形して、例えば10^18 / Aがそこまでの積を超えていないか?のように気を使う必要があります。

一箇所returnを忘れて1WA・・・。方針は間違ってないのにWAをだして、誤差死しちゃった?とテンパってしまいました。

C - Multiplication 3

誤差死しないためにはBを100倍してから答えを100でわります。方針自体はそれで終わりなんですが、単純にB * 100では誤差が出るっぽいので注意が必要です。

自分は2WA出しました・・・。で、開き直って文字列で取って小数点を消しました。(おい(←あ、ちょくだいさんのツイートによれば、別にそれでいいらしいです。

(2020-06-02 追記)

コンテスト後、Pythonだと楽ちんという話が出ていましたが、我らがJavaでもこの程度はBigDecimalを使えば誤差死することなく簡単に計算が可能です。

import java.math.BigDecimal;
import java.math.RoundingMode;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        BigDecimal x = new BigDecimal(in.next());
        BigDecimal y = new BigDecimal(in.next());
        System.out.println(x.multiply(y).setScale(0, RoundingMode.DOWN));
    }
}

これからこういう系統の問題が出たら迷わずJavaで解こうかしら?

D - Div Game

Nを素因数分解して、因数毎に使える数を確定してきます。

例えば24なら2^3 * 3^1なのでそこから2^12^23^1が取り出せます。

997764507000の場合は2^3 * 3^3 * 5^3 * 6079^2なので、2^1, 2^2, 3^1, 3^2, 5^1, 5^2, 6079^1の7つが取り出せます。

BとCでちょっとハマったので、今日のオアシス問題でした。

E - Count Median

偶数のときが全然わかりませんでした・・・。奇数のときがあっているのかもまだわかりませんが。

F - Knapsack for All Subsets

見てません。

まとめ

いやー、BとCがひどかった・・・。しかもBは単なるreturn忘れで落としてますけど、問題が問題なのでてっきり何か誤差周りのあれかと思ってそこでテンパってしまいました。

修行が足りません・・・。

結局レートは今日も微増ですか。まあかろうじてだけど水パフォなのでよしということで。

f:id:mdstoy:20200531233011p:plain

NOMURA プログラミングコンテスト 2020

2完。6:01。

いや、そんなに失敗してないと思うけど、パフォ渋い・・・。

各問題

A - Study Scheduling

起床時間と就寝時間を分に換算し、それらの差からKを引けばよいです。

ただし、マイナスになったら0を出すことを忘れないように。

(2020-05-30 23:38 追記)

なんと、「高橋君が起きている時間の長さはK分以上である」という制約があったので、答えがマイナスになることはないのでした。優しすぎませんか???

B - Postdocs

"PD"と"DD"はともに指数2というのがミソです。

"P?"や"D?"ならもちろん"D"を入れるほうがよいです。"?D"なら前述の通りなのでどちらを入れても構いません。"?P"なら当然"D"を入れるほうがよいです。"??"なら前述の通り"PD"としても"DD"としてもよいです。"?"が長く続いている場合でも"D"を連続させて損しません。

結局、いかなる状況に置いても"D"を入れるのが最適となります。こどふぉのギャグかよ!

C - Folia

後ろから見たり前から見たりしてましたけど、持ちうる最大値をどう抑えるのかがわからず・・・。110分以上椅子を温め続ける結果に・・・。

まとめ

最近の配点が100-???-600のARC級はAB早解きで水パフォ以上あったので、今回も期待していたのですが、Cの難易度のせいか全然伸びず・・・。

まあそんなことよりCを通せという話ですよね、はい。

でもまあAのマイナスのケースを正しく対処できたので今回はよしとしましょう。(ポジティブ

↑いや、マイナスのケースなんてなかった。制約はすみずみまで読みましょう・・・。on_

f:id:mdstoy:20200530231334p:plain

C. Similar Pairs (Codeforces Round #644 Div. 3)

問題

https://codeforces.com/contest/1360/problem/C

問題概要

項数が偶数の整数列が与えられる。この列の項で偶数と偶数、奇数と奇数、または差が1の項どうしでペアを作る時、あまりなしですべての項をペアにすることが可能か答えよ。

考察

まず列の中の偶数の個数を数えます。これが偶数個である場合、列の項数が偶数個であることから奇数も偶数個です。よって、この場合偶数同士のペアと奇数同士のペアをあまりなく作ることができて、答えは"YES"です。

偶数が奇数個だった場合、奇数も奇数個です。この場合は元の列をソートして、隣り合う項の差を確認していきます。

差が1のペアがあればそれをペアにすることで、偶数と奇数を一つずつ消費することができ(差が1ということはどちらかが偶数でもう一方が奇数です)、残った偶数と奇数はともに偶数個になるため、全てペアにすることができ、答えは"YES"です。

差が1のペアがない場合、どうしても偶数も奇数も1つ余ってしまうため答えは"NO"です。

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> a(n);
        int even = 0;
        for (int i = 0; i < n; i++) {
            cin >> a[i];
            if (a[i] % 2 == 0) even++;
        }
        if (even % 2 == 0) {
            cout << "YES" << endl;
            continue;
        }
        sort(a.begin(), a.end());
        bool ok = false;
        for (int i = 0; i < n - 1; i++) {
            if (a[i] + 1 == a[i + 1]) {
                cout << "YES" << endl;
                ok = true;
                break;
            }
        }
        if (!ok) cout << "NO" << endl;
    }
}

どうでもいい話

この文章を書いていて、偶数が偶数で奇数が偶数で・・・、あーややこしい!!ってなってました。

なので「偶数」と「偶数個」というように表現を変えてみましたが、どんなもんでしょう・・・。

B. Honest Coach (Codeforces Round #644 Div. 3)

問題

https://codeforces.com/contest/1360/problem/B

問題概要

整数列が与えられる。これを数列AとBに過不足なく分けたとき、Aの最大値とBの最小値の差の絶対値が最小になるようにしたい。

実現可能な差の絶対値の最小値を答えよ。

考察

例えば数列[4, 1, 9, 14, 6]が与えられたとします。この列をソートします。[1, 4, 6, 9, 14]となります。

ここで隣り合う項の差の絶対値をすべて確認します。[3, 2, 3, 5]です。この列は既にソート済みであるため、隣り合う以外の二項の組み合わせの差が、ここに現れた差の最小値を下回ることはありえません。

ここで、差が最小の2となる部分、4と6の間で区切って二つの列に分けます。[1, 4][6, 9, 14]です。

元の列はソート済みなので、前者の最大値は最も右にある4ですし、後者の最小値は最も左にある6です。区切った位置は元の数列の二項で作りうる差の最小値であるため、以上で題意を満たしています。

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (int i = 0; i < n; i++) cin >> a[i];
        sort(a.begin(), a.end());
        int ans = 1001001001;
        for (int i = 0; i < n - 1; i++) ans = min(ans, a[i + 1] - a[i]);
        cout << ans << endl;
    }
}

A. Minimal Square (Codeforces Round #644 Div. 3)

問題

https://codeforces.com/contest/1360/problem/A

問題概要

2つの辺がaとbの長方形2つを、はみ出さずに敷き詰めることができる正方形の面積を求めよ。

考察

わざわざはみ出させても得をしませんから、2つの長方形は同じ長さの辺が揃うように並べて2倍の面積の長方形を作るが最適です。またこのとき、長い方の辺を揃えて短い方の辺が2倍になる方が明らかに得です。

そして、長くなる方の辺が正方形の一辺となります。

実装的には、aとbの大小で長さの計算を場合分けする、必要ならswapしてa<bとして計算する、両方計算して小さい方を取る、など色んな方法で辺の長さを算出することができます。

答えるのは面積なので、掛け合わせるのを忘れないようにしましょう。

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int t;
    cin >> t;
    while (t--) {
        int a, b;
        cin >> a >> b;
        if (a > b) swap(a, b);
        int x = max(a * 2, b);
        cout << x * x << endl;
    }
}

B. Two Arrays And Swaps (Codeforces Round #642 Div. 3)

問題

https://codeforces.com/contest/1353/problem/B

問題概要

長さnの正の整数で構成された配列aとbが与えられる。また、正の整数kも与えられる。(ただしk<=n

aとbの項目をk回以下入れ替えて作れる配列aのうち、各項の合計が最大になるときの最大値を答えよ。

考察

まず、aの項のうち大きいものからn-k個については動かす必要がありません。

また、k回「以下」というのがポイントで、マイナスになるような操作はしなくてもいいということになります。なので、aの残りk個と、bのn個のうちから大きいものをk個取る、としてよいです。

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, k;
        cin >> n >> k;
        vector<int> a(n);
        vector<int> b(n);
        for (int i = 0; i < n; i++) cin >> a[i];
        for (int i = 0; i < n; i++) cin >> b[i];
        sort(a.rbegin(), a.rend());
        int ans = 0;
        for (int i = 0; i < n - k; i++) ans += a[i];
        for (int i = n - k; i < n; i++) b.emplace_back(a[i]);
        sort(b.rbegin(), b.rend());
        for (int i = 0; i < k; i++) ans += b[i];
        cout << ans << endl;
    }
}

反省など

他の人の実装を見てみると、もっと効率よく書けるようです。自分の実装は、第一印象で浮かんだものをそのまま書き下したような感じなので、あまり煮詰まっているとは言えませんね。

このレベルの問題だとそれでもすぐ通せるのでよいのですが、もう少し難易度が上がってくると破綻しがちです。なので、考察をもう少し詰めるとか実装に対する設計をちゃんとするとかしたほうがよいです。

A. Most Unstable Array (Codeforces Round #62 Div. 3)

問題

https://codeforces.com/contest/1353/problem/A

問題概要

2つの整数n, mが与えられる。

負でない整数から構成された長さn、かつ隣接する各項の差の絶対値の合計が最大になるように配列aを作成した場合の、隣接する各項の差の絶対値の合計を答えよ。

コンテスト中の考察

サンブルの3番目で解答例で挙げられている[0,2,0,3,0]という配列のように、mを均等に割り振って周りに0を配置するのでよさそうに思いました。nが偶数の時は特に最後の一つの項は自動的に0としてしまって大丈夫そうです。(<-ここでもうちょっと考えると、より真実に近づけるのだが、本番ではそれができませんでした。)

なお、nが1のときは、[m]という配列しか作りようがなく、もちろん隣り合う項目がそもそも存在しませんので、答えは0となります。

また、nが2のときは、[m, 0]という配列がもっとも効率がよく、答えはmです。mを分割してしまうと差が減るのは明らかです。

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, m;
        cin >> n >> m;
        if (n == 1) {
            cout << 0 << endl;
            continue;
        } else if (n == 2) {
            cout << m << endl;
            continue;
        }
        if (n % 2 == 0) n--;
        int l = n / 2;
        int r = m % l;
        int p = m / l;
        cout << p * l * 2 + r * 2 << endl;
    }
}

真実

実は、mを分割する必要がそもそもなく、[0,m,0,0,...,0]と、してしまっていいのでした。

なので、答えは、n=1のとき0、n=2のときm、n>2のとき2mとなります。

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, m;
        cin >> n >> m;
        if (n == 1) {
            cout << 0 << endl;
            continue;
        } else if (n == 2) {
            cout << m << endl;
            continue;
        }
        cout << m * 2 << endl;
    }
}