00:04
AtCoder Beginner Contest 109回目、A問題、ABC333。問題文、1以上3以下の整数ABが与えられます。
A×B×Cが奇数となるような1以上3以下の整数Cが存在するか判定してください。
AとBを受け取ります。
アップイントインプットドットスプリットで、for i in range 1から4にして、
if A×B×i%2 !==0 だったら、exit print yes。
何もなく、法文が終わったら、print no で提出。
B問題、しりとり。問題文、高橋くんは、今日も一人でしりとりの練習をしています。
しりとりとは、以下のルールで遊ばれるゲームです。
はじめ、好きな単語を発言する。
以降、次の条件を満たす単語を発言することを繰り返す。
1、その単語はまだ発言していない単語である。
2、その単語の先頭の文字は、直前に発言した単語の末尾の文字と一致する。
高橋くんは、10秒間にできるだけ多くの単語を発言する練習をしています。
高橋くんが発言した単語の個数、nと、i番目に発言した単語、wiが与えられるので、
どの発言もしりとりのルールを守っていたかを判定してください。
高橋くんのどの発言もしりとりのルールを守っていたなら、yes、そうでなければnoを出力せよということで、
これも一回コードテストなしでやってみようかな。
nイコールイントのインプット。
で、どうしようかな。
for i in range n。
で、その前に空のリストLを用意しておいて、
tmpイコールインプット。
どうしようかな。
1文字目は入れとくか。
空の文字列の中にインプットを入れといて、
03:07
first、firstイコールLの0番目の最後、-1。
で、for i in range n-1のtmpイコールインプット。
if tmp not in L and tmpの0番目イコールイコールファーストだったらOK。
そのときはL.append tmpして、
firstを入れ替える。firstイコールtmpの-1番目。
else、そうでなければexitのプリントの、
で、何事もなく4文が終わればプリントyes。
ちょっと不安なのでコードテストしましょうか。
入力例1はnoが出たらOK。
no。
入力例2はyesが出たらOK。
yes。
入力例3はnoが出たらOK。
no。
最後入力例4もnoが出たらOK。
はい、noが出ましたので提出してみます。
はい、ACしましたのでC問題いきます。
C問題、スキップ。
問題文。
数直線上にn個の都市があり、i番目の都市は座標Xiにあります。
あなたの目的はこれらすべての都市を一度以上訪れることです。
あなたははじめに生成数Dを設定します。
その後、あなたは座標Xから出発し、以下の移動1、移動2を好きなだけ行います。
移動1は座標Yから座標YプラスDに移動する。
移動2は座標Yから座標YマイナスDに移動する。
すべての都市を一度以上訪れることのできるDの最大値を求めてください。
06:01
ここで都市を訪れるとはその都市のある座標に移動することです。
nは10の5乗、xは10の9乗、xyも10の9乗が最大ですね。
入力例1、nが3、xも3、xyは1、7、11。
xyはそれぞれの都市の座標。
nが都市の数。
xはスタート地点ですね。
出力例は2。
Dイコール2と設定すれば次のように移動を行うことですべての都市を訪れることができ、これが最大です。
移動2を行いマイナス2して座標1。
あとは足したしたしでいけるよね。
すべての都市を一度以上訪れることのできるDの最大値を求めてください。
だから極論1でDを1にすれば全部追っ付けるのをマックスだと何もですかっていう話ですね。
これどういう考え方したらいいんだ。
いや、出てこんな。
初め都市とか座標とか言ってたから幅優先探索とか深さ優先探索とかそっち系のアルゴリズムかと思ったんですが。
解説見ます。
C問題。
Dがすべてのiについてx-xyの絶対値の約数であるときすべての都市を訪れることができます。
x-xyの約数であるとき。
逆にDが約数でないようなiが存在するとき。
そうさによって現在いる座標をDで割った余りが変化しないことからx-xyの絶対値をDで割った余りがx-xyの絶対値またはD-x-xyの絶対値となりゼロになることがないため座標xiを訪れることができません。
したがってすべての約数であって最大の生成数Dを求めればいいことになります。
このようなDは最大公約数と定義され、ユークリッドの誤除法により高速に計算できることが知られています。
はぁユークリッドね。
大噂はカネカネ聞いてますね。
ユークリッドの誤除法とはGCDのAB。
09:01
GCDB-A-B。
もしBが0だったらAを返すが成り立ち、これに従って計算するアルゴリズムのことです。
ここでGCDABはAとBの最大公約数を表し、A-BはAをBで割った余りを表します。
ユークリッドの誤除法はA小なりイコールBのとき1回の反復でAもどB小なり2分のAとなることからオーダーログMAXABで求まります。
ちなみにABがフィボナッチ数のときに遅くなりますがログで求まることには変わりありません。
ちょっとやってみるか。
NXの小文字Xが与えられるから
NとXマップインとインプットドットスプリットで小文字Xのリストマップインとインプットドットスプリットでユークリッドの誤除法を実装するには
GCDのAとBの最大公約数を表します。
FBが0より大きかったらリターンGCDBかBとAもどB。
FBが0より大きかったらリターンGCDBかBもどB。
FBが0より大きかったらリターンGCDBかBもどB。
12:42
Dは最大公約数と定義されます。
Dはどこから作り出したらいいんだ?
ユーザー解説。
Dを固定すると行ける座標と行けない座標が定まる。
細かく言うとXイコールYもどDであるYしか行けなくなる。
X%DイコールXのリストXの0%DイコールリストXの1番目%Dを満たす最大のDであることが求められる。
変形して0イコールリストXの0番目マイナス大文字XをDで割った余りイコール…
よってリストXマイナス大文字Xが全てDの倍数である必要がある。
共通の約数で最大のものを求めたい。最大公約数。GCDは効率の良い求め方があるのでそれで求めると。
C++ですがわかりそうな漢字なのでちょっと見とこうか。
REP I0N CIN XI 4文じゃない?
REPってリピートか4文か。
GCD ANS…やっぱりANS0で入れてるな。
ってことはコードテストのGCDは…
GCD ANS Xの5番目?
15:05
フォワインレンジNの大文字Xがあるんだ。
いやーわかんねー。
あ、絶対値になるのか?
ANSとABS…ABS XI番目マイナスXが入れてるな。
フォワインレンジN、GCD ANSとXのI番目マイナス大文字Xの絶対値。
ABS。プリント。
ANS?だよね。ANS0になるよね。
ANSイコールか。ANSイコールGCD0だな。
他の方の提出例を見ておきます。
では今回はここまでにしておきましょう。また次回お疲れ様です。