第2回ドワンゴからの挑戦状予選(問題A,B)

タイトル通り2完でした。C問題の「最悪の時の最短時間」っていうのがゲームっぽいからアルファ・ベータ法か何かかな…とは思ったけど、ゲーム系はNimぐらいしか実装したこと無いのでさっぱりな人でした。

取り敢えずコンテスト終了と同時にBまでは解説を出そうと。

A - ニコニコ数

問題概要

1からNまでの整数で約数にニコニコ数を持つものがいくつあるか求めよ。
(ニコニコ数とは、25,2525,252525など2から始まり、2と5が交互になっている偶数桁の数字である)

http://dwango2016-prelims.contest.atcoder.jp/tasks/dwango2016qual_a

解法

そもそも2525は25で割り切れる。他ニコニコ数は全て25で割り切れます。

今回は「約数にニコニコ数を持つ数字の数」を求めるのだから、25で割り切れればOK。

ここで、1〜Nまでの数字で25を約数に持つ数字の数はN/25で求められるので、これを出力するだけ。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    ll n;   cin>>n;
    cout<<n/25<<endl;
    return 0;
}

B - 積み鉛筆

問題概要

平面ピラミッドの2段目をmax(左下の数字、右下の数字)で定義して作った。2段目が与えられるので1段目として考えられるものを1つ答えよ。

http://dwango2016-prelims.contest.atcoder.jp/tasks/dwango2016qual_b

解法

o o o o o

o o o o o o

とあった時、下の要素が影響を与えるのはその要素の右上と左上（これ最重要）。

ここで1段目を左から確定していく時、1番左は2段目の1番左と同じでも問題は無いはず。

左から2番目はあり得る候補として2段目の1番左と2番目。左から1番目と比較して、大きい方が2段目の1番左と一致している方を選ぶ。両方OKならより小さい方を採用。

以下同様に左から決めていき、右端は2段目の右端と一致させれば通ります。

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n; cin>>n;
    vector<int> a(n-1);
    for(int i=0;i<n-1;i++)  cin>>a[i];
    vector<int> ans; ans.push_back(a[0]);
    for(int i=1;i<n-1;i++){
        int s=a[i-1],t=a[i];
        if(s>t)    swap(s,t);
        if(max(ans[i-1],s)==a[i-1]) ans.push_back(s);
        else if(max(ans[i-1],t)==a[i-1])  ans.push_back(t);
        else ans.push_back(1);
    }
    ans.push_back(a[n-2]);
    for(int i=0;i<n;i++){
        cout<<(i?" ":"")<<ans[i];
    }
    cout<<endl;
    return 0;
}

感想

C問題がサッパリ分からない…全完者は3名でした。

解説が出たら残りも解きたいです（しかし前回のSRMのMedが解き終わっていない）