学祭前最後の定例勉強会でした。
ということで、これまで扱った問題の復習の意味を込めてバーチャルコンテストを開催しました。
初心者組とバーチャルコンテスト組に分かれていたのでコンテストに参加したのは3人でした。
既に解いたことのある問題ということもあり、最終的にはConnected?を協力して考える形になりましたが…
端を考えたらいいんだろうなぁ程度の考察でTIME UPとなってしまいました。
初見の問題にも対応できるようにもっと実力をつけなきゃなっていうのが個人的な感想ですね。
ということで報告はここまでにして、バーチャルコンテストの解説に入っていきます。
やるだけって言うような問題ですね。入力が二桁の整数なのでn%10で一桁目、n/10で二桁目の数字が分かるので9かどうかをチェックしたあと出力をして終了です。出力はcoutではなくputs()を使っているのですが、これは文字列を渡してそれを出力する関数です。最後には自動的に\nが付くので書く必要はないです。この関数を利用するには#include<cstdio>をする必要があります。以下がコード例となります。
#include<iostream>
#include<cstdio>
using namespace std;
int main(){
int n;
cin >> n;
if(n/10==9){
puts("Yes");
return 0;
}
if(n%10==9){
puts("Yes");
return 0;
}
puts("No");
return 0;
}
同じ文字が入っているかを調べる問題ですね。for文を26文字分回してそれぞれの英小文字の数を調べて２つ以上あればyesを表示するというプログラムでもいいのですが、今回はfind()を使って求めようと思います。find()は一番最初のその文字の場所を返すので、２つ以上同じ文字がある場合その文字の場所とfind()から返ってくる数字がずれます。これをチェックして答えを出力して終了です。以下はコード例になります。
#include<iostream>
#include<cstdio>
using namespace std;
int main (){
string s;
cin >> s;
for(int i=0;i<s.length();i++){
if(s.find(s[i])!=i){
puts("no");
return 0;
}
}
puts("yes");
return 0;
}
また、キャスト変換をしないで英小文字を数字で扱う方法としてこういったものがあります。
(英小文字)%26の様にすることで英小文字にそれぞれ０〜２５までの数字を割り振ることができます（どの英小文字がどの数字かというのを扱うには向かない）
これは英小文字の文字コードが連続しているので%26をしてあげることで区別することができるというものです。
これを利用して各配列の数をインクリメントして２以上のものがあるかをチェックしてあげれば通ります。以下は別解になります。
#include<iostream>
#include<cstdio>
using namespace std;
int main (){
string s;
cin >> s;
int count[26];
fill(count,count+26,0);
for(int i=0;i<s.length();i++){
count[s[i]%26]++;
}
for(int i=0;i<26;i++){
if(count[i]>1){
puts("no");
return 0;
}
}
puts("yes");
return 0;
}
座圧 AtColorの解説は過去の記事にありますのでそちらを参照ください。
これは子供の頃にやったようなパズルゲームで線を引けるかを判定する問題になります。ある程度考察を進めていくと端にないペアは無視していいことがわかります。あとは、端と端にあるペアと端と端以外にあるペアの２つになります。ここでは、証明は省きますが線の引き方を工夫すれば端と端以外のペアも無視しても大丈夫です。
ここまで考察することができれば残りの端と端のペアのみに焦点を当てて、どのような配置の時に線を引くことができるのかについて考えます。同じペアを線で結んだ時に重なり合わないようにすれば良いので、ある頂点から時計回り、もしくは半時計回りに辺を見ていき例えばi,j,sがijssjiの様な真ん中で折り返した順番で出てくれば良いです。
これをどう実装するかですがstackを使います。ある頂点から辺を辿っていき、数字が出てきたらtop()をして一番上に積まれている数字を確認して、違う数字だったらpush()でその数字を積み、同じだったらpop()で取り除くというのを繰り返していって最終的にstackのサイズを確認して出力を行います。stackの使い方は過去の記事を参照してください。
時計回りもしくは半時計回り（コードは左下の頂点から半時計回り）の辺の見方は、ある頂点からの距離をキーにし、その時の数字を値にしてmapを使って実装します。コード例にあるdist関数は左下の頂点からの距離を返す関数です。以下はコード例になります。
#include<iostream>
#include<cstdio>
#include<map>
#include<stack>
using namespace std;
typedef long long LL;
LL R,C;
LL dist(LL x,LL y){
if(x!=0&&x!=R&&y!=0&&y!=C) return -1;
if(y==0) return x;
if(x==R) return R+y;
if(y==C) return 2*R+C-x;
if(x==0) return 2*(R+C)-y;
return -1;
}
int main(){
map<LL,int> mp;
stack<int> s;
int N;
cin >> R >> C >> N;
for(int i=0;i<N;i++){
LL x1,y1,x2,y2;
cin >> x1 >> y1 >> x2 >> y2;
if(dist(x1,y1)!=-1&&dist(x2,y2)!=-1){
mp[dist(x1,y1)]=i;
mp[dist(x2,y2)]=i;
}
}
s.push(-1); //s.top()を使うために-1を入れておく
for(auto p : mp){
if(p.second!=s.top()) s.push(p.second);
else s.pop();
}
if(s.size()==1) puts("YES"); //-1の分を考えてサイズが１ならOK
else puts("NO");
return 0;
}
以上で解説は終わりになります。バーチャルコンテストはこれからも開催していくと思うのでその時は是非参加してくださいね！
by ゆきのん