11回目のratedコンテストで3回目の全完をしました。
次回はAGCなので不安です。

A問題

A - ABC333
$A, B$ が与えられるので、 $A\cdot B\cdot C$ が奇数となるような $C$ が存在するか判定する問題です。

解法

$A\cdot B$ が偶数の場合、 $C$ が何であっても $A\cdot B\cdot C$ は偶数となり、
$A\cdot B$ が奇数の場合、 $C$ が奇数の時 $A\cdot B\cdot C$ は奇数となるので、 $A\cdot B$ の偶奇を判定すればよいです。

#include "bits/stdc++.h"
using namespace std;
int main(){
    int a,b;cin>>a>>b;
    cout<<(a*b%2?"Yes":"No");
}

B問題

B - Shiritori
与えられた文字列の列がしりとりになっているか判定する問題です。

解法

やるだけです。せっかくなので少し前に([ABC105] 解法、unordered_mapの使いどころ - tqkoh's diary)使ったunordered_mapを使った実装にしてみました。
下のサンプルコードでは、使われた文字列をkeyとして、何回つかわれたかをvalueとしています。足した後に2になる、または、しりとりになっていない場合"No"を出力し、最後まで行ったら"Yes"を出力しています。

#include "bits/stdc++.h"
using namespace std;
int main(){
    int n;cin>>n;
    unordered_map<string, int> ma;
    vector<string> s(110);cin>>s[0];++ma[s[0]];
    for (int i=1;i<n;++i){
        cin>>s[i]; ++ma[s[i]];
        if(ma[s[i]]==2 || s[i][0]!=s[i-1][s[i-1].size()-1]){cout<<"No";return 0;}
    }
    cout<<"Yes";
}

C問題

C - Skip

数直線上に $N$ 個の都市があり、 $i$ 番目の都市は座標 $x_i$ にあります。
あなたの目的は、これら全ての都市を $1$ 度以上訪れることです。
あなたは、はじめに正整数 $D$ を設定します。
その後、あなたは座標 $X$ から出発し、以下の移動 $1$ 、移動 $2$ を好きなだけ行います。
- 移動 $1:$ 座標 $y$ から座標 $y+D$ に移動する
- 移動 $2:$ 座標 $y$ から座標 $y-D$ に移動する
全ての都市を $1$ 度以上訪れることのできる $D$ の最大値を求めてください。という問題です。

解法

まず $X$ から始めるという変な設定なのですべての $i$ について $x_i$ から $X$ を引きます。
すると、何個か例を見るとすべての都市の座標に行くにはその公約数の時に行けることがわかります。(6, 8, 10)など？
なので最大公約数を求めます。

#include "bits/stdc++.h"
using namespace std;
int gcd(int a, int b) {
    if (!b)return a;
    return gcd(b, a%b);
}
int main(){
    int n,X,x,ans;cin>>n>>X;
    cin>>x;ans=abs(x-X);
    for (int i=1;i<n;++i){
        cin>>x;ans=gcd(abs(x-X),ans);
    }cout<<ans;
}

D問題

縦H行横W列に区切られたマス目があり、上から i番目、左から j列目のマスをマス(i, j)と呼びます。マス(i, j)には $a_{ij}$ 枚のコインが置かれています。あなたは以下の操作を何度でも行うことができます。操作: まだ選んだことのないマスのうち1枚以上のコインが置かれているマスを1 つ選び、そのマスに置かれているコインのうち1枚を上下左右に隣接するいずれかのマスに移動する
偶数枚のコインが置かれたマスの数を最大化してください。

出力: 偶数枚のコインが置かれたマスの数が最大となるような操作の列を次の形式で出力せよ。

$N$
$y_1$ $x_1$ $y_1\prime$ $x_1\prime$
$y_2$ $x_2$ $y_2\prime$ $x_2\prime$
$\cdots$
$y_N$ $x_N$ $y_N\prime$ $x_N\prime$

という問題です。最小の手数とは言ってない

解法

これはやり方さえわかれば後は実装するだけです。
まず、操作のすべてのパターンを見てみると、

操作するマス	操作後のマス	考察
A.奇数マスから奇数マス	偶数マス、偶数マス	奇数マス2個が消えた！
B.奇数マスから偶数マス	偶数マス、奇数マス	奇数マスを（1貰うほうのマス）に移動できた。
C.偶数マスから奇数マス	奇数マス、偶数マス	奇数マスを(1あげるほうのマス)に移動した。
D.偶数マスから偶数マス	奇数マス、奇数マス	ゴミ

奇数か偶数か、だけで後の状態が決まるので、重要なのは奇数か偶数かだけだとわかります。

また、いま奇数をなるべく消して偶数だけにしたいので、何らかの移動をして奇数マスから奇数マスに1を運んでいけばいいとわかります。
なので、この問題は「奇数と奇数をつなぐ道を出力する」という問題と言い換えられます。
ここから先の図では、マスの値をmod 2で表します。つまり奇数が1という事です。
つなげ方はいくつかあります。自分は本番中には「じゃばら状に見て行って、奇数が来たら、矢印を置くかおかないかのフラグを反転させ、フラグがたっているときのみ矢印を出力する」（以下図）

をしましたが、twitterで「右下に寄せる」という天才的発想を見たので、そちらを紹介します。

どういうことかというと、

f:id:tako0608:20180909113518p:plain

はじめ見たときは「こっちのほうが実装難しそう（どこまで1を運んでいるかを覚えておくなどがどうやればいいかわからない）」と思いましたが、なんとこのやり方、「1マスずつ見て行って、奇数が来たら右に移動する（端っこでは下）」だけでできるんです。
なぜかはこの図か上の表を少し見ればわかると思いますが、奇数を奇数に移動(A.の操作)したら消えるので、1をどこまで運んで置いたかなど覚えておく必要がないんです。
この解法を見て気づきましたが、自分のじゃばら状の解法（？）も、奇数が来たら次のマスに移動するだけでよかったようです。
どっちにしろじゃばら状に移動させるのは少し難しかったので、右下に寄せる解法のサンプルコードを載せておきます。

#include "bits/stdc++.h"
using namespace std;
char ans[250010][256]={""};
int main(){
    int h,w,in;cin>>h>>w;
    bool mp[550][550];int ansc=-1;
    //奇数を1として入力します。
    for (int j=0;j<h;++j)for (int i=0;i<w;++i)cin>>in,mp[j][i]=in%2;
    for (int j=0;j<h;++j){
        for (int i=0; i<w-1; ++i)
            if (mp[j][i]){
                //そのマスが奇数の時のみ、右向きに移動A.またはB.をします。
                mp[j][i]=0; mp[j][i+1]=!mp[j][i+1];
                //答えを保存しておき、数を数えます。
                sprintf(ans[++ansc],"%d %d %d %d\n",j+1,i+1,j+1,i+2);
            }
        if(j!=h-1&&mp[j][w-1]){
            //一番右かつ右下以外の時は、下向きに移動A.またはB.をします。
            mp[j][w-1]=0; mp[j+1][w-1]=!mp[j+1][w-1];
            sprintf(ans[++ansc],"%d %d %d %d\n",j+1,w,j+2,w);
        }
    }
    cout<<ansc+1<<endl;
    for (int i=0;i<=ansc;++i)cout<<ans[i];
}

tqk's diary

競プロとか

ABC109 A B C D問題

A問題

解法

B問題

解法

C問題

解法

D問題

解法