AtCoder ABC139-E を有向グラフ初心者がC++で解く

ABC139 - E に挑戦します。

最初は、n日目に出場する選手のリストを作って探索しようと思いましたがうまくいかず、解説を読む。

https://img.atcoder.jp/abc139/editorial.pdf

「$N(N-1)/2$試合のそれぞれを頂点に見立て、（略）有向グラフを考えます。」「閉路検出と最大パス長の算出」と書いてあったのでまずは閉路検出とやらを勉強することにした。

挑戦前の能力 : キューとスタックで無向グラフのBFSとDFSができる

用語など

とりあえずこの記事の内容がつかめる程度の説明

• グラフ, 頂点, 辺 : 下の図のようなものがグラフ。丸で囲ったところが頂点、頂点をつないでいるのが辺。今回は辺が矢印になっている（向きを持っている）ので有向グラフ。

• 入次数 : それぞれの頂点において、矢印が「刺さっている」数。例えば頂点1は入次数0。頂点4は入次数2（出る矢印は数えない）。

• 閉路 : 要するにループ。先ほどのグラフに、$7 \rightarrow 2$ の辺をつけると $2 \rightarrow 5 \rightarrow 7 \rightarrow 2$ というふうに閉路が形成される。

• 有向非巡回グラフ DAG : 閉路がないグラフ（図のまま）を「有向非巡回グラフ (Directed Acyclic Graph = DAG)」という。

• トポロジカルソート : 辺が繋がったままグラフの頂点を1列に並べた時、矢印がすべて右向きになるようにソートすること。下図参照。なお、これには何通りか並べ方がある可能性もある。

+ グラフの入力 : 基本となる、グラフの入力方法。頂点の数 $N$ 、辺の数 $ M $ を入力し、続けて $ M $ 回、矢印の根元と行き先の頂点を入力。以下の例参照。

//入力例（上の図を示す）
7 8
1 2
1 4
2 3
2 5
4 3
5 7
6 4
6 5

Automateで選択肢を出す [Dialog choice]

Automate で選択肢の提示をする方法についてまとめました。

環境 : Android 9.0, Automate Version 1.23.1

llamalab.com

選択ボタンを表示させる

今回扱うのは Interface - Dialog choice ブロックです。

選択肢を提示し、いずれかが選択されたらYESへ、CANSELが押されたらNOに分岐します。

まずは変数について見ていきます

Input arguments 入力引数

Title

ボタンウィンドウのタイトル。何も書かなければタイトルは出ない

Choices

選択肢。array型かdictionary型で与える

["first", "second", "third", "else"] //array
-> 選択肢は first second third else

{"first" : 1, "second" : "two", "third" : 3, "else" : "その他"} //dictionary
-> 選択肢は 1 two 3 その他

Multi-select

複数選択。デフォルト（チェックボックスが灰色の[-]）では false

• true - 複数選択できるようになり、ボタンウィンドウがチェックボックス式になる。ALL（全選択）が表示される。
• false - 複数選択は不可能。ボタンウィンドウは選択肢が並ぶだけになる。

No selection

何も選択せず次に進むことができるかどうか。デフォルトではfalse

• Multi-select = false（単一選択）のときは無効。チェックの有無にかかわらずfalse。何も選択しないならばCANSELを押すしかない
• true - チェックボックスに何もいれなくてもOKを押せる。
• false - チェックボックスがどれも選択されていないとOKが押せない。

Sort

選択肢のソート。デフォルトではtrue

• true - 選択肢が、array型なら各要素で、dictionary型なら各valueによって辞書順にソートされる。ソート順は 数字→アルファベット→日本語。
• false - 選択肢が、入力したChoicesの順序のまま表示される。

Choices = ["first", "second", "third", "else"] //array
Sort : true
->
選択肢は else first second third の順で表示

Coices = {"first" : 1, "second" : "two", "third" : 3, "else" : "その他"} //dictionary
Sort : true
->
選択肢は 1 3 two その他 の順で表示

Pre-selected

ユーザーが選択する前にあらかじめ選択しておく際入力。デフォルトは空白（none）。Multi-selectの真偽によって挙動が異なる

• Malti-select : true - チェックボックスで、指定された選択肢にあらかじめチェックがつく
• Malti-select : false - ボタンウィンドウがラジオボタン式になり、Pre-selectedの要素が選択された形で表示される。

Choicesの型によって入力方法が異なる

• Choicesがarray型 - Choicesに対するインデックスを1つ入力（ソートについては考えなくて良い）。もしarray型で列挙した場合はarr[0]が採用される。

Choices = ["first", "second", "third", "else"] //array
Pre-selected = 2
->
選択肢 third があらかじめ選択される

Pre-selected = [2, 1]
->
Pre-selected = 2と同値

• Choicesがdictionary型 - Choicesに対するkeyをarray型で列挙（一つなら変数のみでも良い）。

Choices = {"first" : 1, "second" : "two", "third" : 3, "else" : "その他"} //dictionary
Pre-selected = ["else", "fiest"]
->
選択肢 1, その他 があらかじめ選択される

Timeout

入力の制限時間。デフォルトでは空白（ずっと待機する）。

入力は 0h 5m 0s のような直感的入力のほか$fx$を有効にしてにて秒数で指定も可能。

指定時間以内に入力がなされなければNOへ分岐する

Notification channel

よくわからないけどデフォルトの空白のままで困らない

Show window

ボタンウィンドウを即時表示する。デフォルトはfalse。普通はtrueにすると良い

• true - Dialog choiceブロックに至ったら即座にボタンウィンドウが表示される
• false - Dialog choiceブロックに至ったら、通知がでて、その通知を押すとボタンウィンドウが表示される。

Requires the “appear atop of other apps or parts of the screen” privilege on Android 10+.

（documentationより）

Output variables 出力変数

Array of selected indices/keys

indicesはindexの複数形

選択したものはarray型で出力される。選択肢が単一だとしても出力はarray型なので、取り出すにはarr[0]のようにしなければならない

Choices = ["first", "second", "third", "else"] //array
Array of... : x
->
second を選択
->
x = [1] //インデックスは0始まりであることに注意

Choices = {"first" : 1, "second" : "two", "third" : 3, "else" : "その他"} //dictionary
Array of... : x
->
two その他 を選択
->
x = ["second", "else"]

使用例

以下の擬似プログラミングに沿って作ってみる。General::Variable setとは、Variable setブロックがGeneralカテゴリにあることを明示しています。

Flow beginning{}
General::Variable set{
  Variable : tenki
  Value = ["晴れ", "曇り", "雨", "雪"]
}
Interface::Dialog choice{
  Title : 今日の天気は？
  Choices = tenki //先に設定したarray型変数を使う
  Show_window : true
  Array_of... : selected
}
Interface::Dialog message{
  Title : 今日の天気は
  Message : {tenki[selected[0]]}です
  Show_window : true
}

順につなげてこのようになります

実行

曇り を選択

おしまい

Automateについてはこちらもご覧ください

o-treetree.hatenablog.com

AtCoder ABC168【ABCD=AC】

こんにちは。ABC168でした。

今回は48分でDまで解けました！しかもWA無し！

Eはまだ無理ですね、見当もつかない。

A

提出

AC

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
  int N;
  cin>>N;
  N %= 10;
  switch(N){
    case 2:
    case 4:
    case 5:
    case 7:
    case 9: cout<<"hon\n"; break;
    case 0:
    case 1:
    case 6:
    case 8: cout<<"pon\n"; break;
    case 3: cout<<"bon\n"; break;
  }
  return 0;
}

入力したNを、10での余りをとって1桁目だけにして分岐

if文だとめんどいのでswitch文で書きました。

B

提出

AC

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
  int K;
  cin>>K;
  string S;
  cin>>S;
  if(S.size()>K){
    for(int i=0; i<K; i++)cout<<S[i];
    cout<<"..."<<endl;
  }else{
    cout<<S<<endl;
  }
}

文字数の条件で分岐して、指定された通りに出力。

C

ミソは、時針の角度が、分の値によって微妙に進んでいることですね

2本の針がなす角度を $\theta$ として、求める長さ $C$ は余弦定理から

$$ C^{2} = A^{2} + B^{2} - 2AB \cos \theta $$

として求められます。

提出

AC提出からちょっとコメント手直し

#include <bits/stdc++.h>
using namespace std;

int main(){
  cout<<fixed<<setprecision(10);
  double A,B;
  double H,M;
  cin>>A>>B>>H>>M;

  double h, m; //0時0分から時計回りの角度（ラジアン）
  
  m=2*M_PI*M/60; //分針の角度

  H += M/60; //分によって時を調整。30分だったら0.5時。そんな感じに進める
  h = 2*M_PI*H/12; //時針の角度

  double theta = min(abs(h-m), 2*M_PI-abs(h-m)); //針のなす角度。小さい方を取る

  //この2行で余弦定理を計算
  double c = A*A + B*B - 2*A*B*cos(theta);
  c = sqrt(c);

  cout<<c<<endl;
}

$\cos \theta = \cos (2\pi - \theta)$ なので途中で針のなす角度の「小さい方を取る」のはいらん操作でしたね。まあええわ

追記 : メイン関数冒頭のcout<<fixed<<setprecision(10);で小数点以下10桁まで吐き出すようにしてます。

D

方針 : 図を書いてみたら、

• 1から行ける部屋 $i$ には1への道しるべを置く
  そうすることで $i$ にたどり着いたあと最短で1に行ける（基本発想）
• 例えば入力例2では最初に 5,6 の部屋に 道しるべto1 を置く
• 5,6の部屋から行ける部屋 $j$ には それぞれ5,6への道しるべを置く
  そうすることで $j$ にたどり着いたあと最短で1に行ける（5,6からは1への最短が示されているので）
• 入力例2では、2->6と行ける。また3->5と行ける。4は、5,6のどちらにもつながってるので、とりあえずどちらかへの道しるべがあればいい

こんな感じで「幅優先探索」をすると、「1に最短で道1本で行ける部屋」「1に最短で道2本で行ける部屋」……がわかり、どの部屋でも「1に最短で道n本で行ける部屋」として分類できる。

出力としてNoはあり得ない。

1から、階層を降りていくイメージ

入力例2では

• 地上階 … 部屋1
• 地下1階 … 部屋5,6
• 地下2階 … 部屋2,3,4

というイメージで、どの部屋にも1つ上の階層に上がる道しるべを置けば良い。

深さ優先探索をしてしまうとその名の通り深くまで潜ってしまう。例えば部屋が山手線みたいに輪っかになってたら、と考えると良いと思う。

提出

AC

#include <bits/stdc++.h>
using namespace std;

/* vector */
using vi = vector<int>;
using vvi = vector<vi>;
#define pb push_back

int main(){
  int N,M;
  cin>>N>>M;

  vvi cango(N);//それぞれの部屋からいける部屋のリスト
  int a,b;
  for(int i=0; i<M; i++){
    cin>>a>>b;
    a--;b--;
    cango[a].pb(b);
    cango[b].pb(a);
  }

  vi sirube(N, -1);//それぞれの置く道しるべ -1は無記入で初期化
  sirube[0] = 0;//最初の部屋にはなんかかいとけ <- 別に-1のままで良かったのでは

  queue<int> unchecked;//調査したい部屋を入れるキュー
  unchecked.push(0); //初期は部屋1（添字は0）の調査

  while(!unchecked.empty()){
    int current = unchecked.front();
    unchecked.pop();

    for(int next: cango[current]){
      //行ける部屋を調べてみる
      if(sirube[next]==-1){
        //道しるべなし
        sirube[next] = current+1;//道しるべは1始まりに注意
        
        unchecked.push(next);
      }
      //道しるべがあったらその部屋は無視する
    }
  }

  cout<<"Yes\n";
  for(int i=1; i<N; i++){
    cout<<sirube[i]<<endl;
  }
}

おしまい

グラフ問題が解けてえらい！

Eについてはちゃんと勉強しておこうと思います。おしまい。

AtCoder ABC165-Cをスタック利用DFSで解く

概要

atcoder.jp

これをc++で解く。

この問題を解くには、生成しうる数列を全て作って各々数列の得点を求め、最大値を見つける。（制約より、数列の数はそれほど多くない）

得点を求めるのは難しくないので後回しにして、条件を満たす数列を作ることを考える。

改めて数列に関する条件を確認すると

• 長さ $2 \le N \le 10$
• $1 \le A_1 \le A_2 \le \cdots \le A_N \le M \le 10$

要は、例えば $N=3, M=4$ のとき

\begin{align} &(1,1,1), (1,1,2), (1,1,3), (1,1,4), (1,2,2), (1,2,3), (1,2,4), \cdots , \cr &(2,2,2), (2,2,3), (2,2,4), \cdots ,\cr &(3,3,3), (3,3,4), (3,4,4), \cr &(4,4,4) \end{align}

と、こんな具合の数列を生成すれば良い。

さて、こういう時に「深さ優先探索（DFS）」を使うと良いとのこと。

DFSの概念自体は難しくない、と思うので解説は省略。いわゆる「樹木図」を辿っていくようなもの。

ただ、検索すると、この問題に関しては再帰関数を用いた回答ばかり見つかった。まあやってることは結構わかりやすいのでそれでも良いのだが、あえてDFSでやりたい理由がある。

先日ABC151-D

atcoder.jp

をやっているときに「幅優先探索（BFS）」に触れており（参考スタックとキューを極める！ 〜 考え方と使い所を特集 〜 - Qiita）、『BFSのアルゴリズムで使っているキューを、スタックにすることでDFSになる』という話を聞いたので、スタックを使う方法で実装してみようと思った。

結論から言えば、成功したので、その考え方や途中でミスった点を記録する。

cとc++で最大公約数、最小公倍数を求める

gcdとlcmの実装

最大公約数（GCD : Greatest Common Divisor）と最小公倍数（LCM : Least Common Multiple）を求めるプログラムをc言語で書いてました。競プロ（AtCoder）で使うためです。最近使用言語をc++に乗り換えたのでcからc++に書き換えていたら色々と発見があったので記録しておきます。

最大公約数 gcd

まずは2つの数で。

これは、ユークリッドの互除法を用いて求めます。詳しくはユークリッドの互除法 - Wikipedia参照。

//cでもc++でも
int gcd(int a, int b){
  if(a%b == 0){
    return b;
  }else{
    return gcd(b, a%b);
  }
}

ときどき、$a > b$ が必要だとして関数の冒頭でif(a < b)swap(a, b)みたいなことをやっているのを見ますが、これは必要ないです。

$a < b$ のときa % b == aなので結局gcd(b, a)に帰結します。

競プロABC問題風記事の解説

これの解説記事です。先に↑を見てください。ちなみに「ABC問題」は数学の難問「ABC予想」のことではありません。競技プログラミングの「AtCoder Beginner Contest」の略称です。

なお、この解説が正しいかどうかは（全文に渡って）保証しかねます。多分あってる。知らんけど（無責任）。

ABC（AtCoderBeginnerContest）問題風のぼやき

C - Great Person

実行制限時間: 4 sec/ メモリ制限: 1024 MB

配点: $300$ 点

問題文

とある界隈には $ N $ 人の人がいます。界隈の人の趣味は $ M $ 種類であり、それぞれ趣味$ 1 $、趣味$ 2 $、……趣味$ M $ と呼びます。界隈の $ i $ 番目の人は趣味 $ j $ に対して $E_{i,j}$ という経験値を持っています。

ここで、ある人の持っている趣味の中で一つでも、その経験値が界隈の他の誰よりも高いとき、その人は「すごい人」であるとします。

界隈の人全員について、「すごい人」であるかを判定してください。

注：$ M $ 種類のうちに含まれない、認知されていない趣味については、こっそり嗜んでいたとしても考えないものとします。

制約

• $1 \le N \le 1000$
• $1 \le M \le 1000$
• $0 \le E_{i,j} \le 10^{7}$
• 入力中の値はすべて整数である。