00:03
AtCoder Beginner Contest 244回目、A問題ラストレター、問題文、A個文字からなる長さNの文字列Sが与えられます。
Sの末尾の文字を出力してください。
これはもう普通にやるだけですね。
Nイコール、インプットで済ましておいて、プリントでいきなりいけるかな、インプットのかぎ括弧マイナス1で出せたらやってみましょう、提出。
ダメだったらまた変数に入れ替えて、あ、いけましたね。A問題ACです。
B問題、ゴーストレート&ターンライト、問題文、XY平面を考えます。
X軸の正の向きを東向き、Y軸の正の向きを北向きとします。
高橋くんは初め点XY00にいて、東、X軸の正の向きを向いています。
SとRのみからなる長さNの文字列Tが与えられます。
高橋くんはI番目1、2からNまでの順番で書きを行います。
TiがSならば高橋くんは今向いている方向に距離1だけ進む。
TiイコールRならば高橋くんはその場で右に90度回転する。
その結果高橋くんの向いている方向が書きの通りに変わる。
回転前の向きが東ならば回転後の向きは南。
回転前の向きが南ならば西。
回転前の向きが西なら北。
北なら東になる。
上記の手順を終えた後に高橋くんがいる場所の座標を出力してください。
出力していきましょう。
Nイコールイントのインプット。
これももうやるだけ問題じゃないかな。Sイコールインプット。
制限が10の5乗なので4分でぐるぐる回していいと思うんですよね。
Xイコール0。
Yイコール0。
0,0スタートです。
NOWイコール。
NOWXにしとこうか。
NOWXイコール1。
西の方向に向いているので。
NOWYイコール0。
4YインレンジN。
03:04
IFSのI番目がイコールイコールSストレートだったら
Xプラスイコール。
NOWX。
Yプラスイコール。
NOWY。
エルス。
だからSIがRだった場合、右向く場合ですね。
どう処理しようかな。
普通にそのまま変数を変えましょうか。
NOWXイコール0。
あ、そうか。
困ったな。
そっか。じゃあ、
NOWっていうリストを作りましょう。
一番始めは
1,0。
リストの中にリストを作って
X1,Y0。
が一番初めです。東を向いているので。
そこからRを
右を向くと下に向くので、南に向くので
Xには進まない。
0。
Yのマイナス方面なのでマイナス1。
さらに右に向くと西方面なので
マイナス1,0。
最後、北を向くので
0,1ですね。
NOWどうしようかな。
DIRにしとこうか。
ダイレクション・方向
がこのリスト内の4方向。
NOWイコール0だ。
で、
4iインレンジNの
IFSIがストレートだったら
Xプラスイコール
あ、そうか。もうこの4iインレンジNの直後に
06:04
大文字Xイコール
DIRの
NOW番目の0。
で、大文字Yイコール
DIRの
NOW番目の2個目なので1
の数字を取ります。
で、IFSIイコールストレートだったら
Xプラスイコール大文字X
Yプラスイコール大文字Y。
エルス、そうでなければ
NOWをプラスイコール1します。
で、NOW
%イコール4
のプリント
X,Yでいいんじゃないかな。
テストケース。
出力例1は2とマイナス1が出たらOK。
2とマイナス1。出力例2は
0,1が出たらOK。
0,1OKですね。出力OKそうなので提出していきます。
大丈夫そうですね。はい。通ったのでC問題いきます。
C問題。山手ラインゲーム。
問題文。高橋くんと青木くんは2人で次の対戦ゲームをします。
高橋くんが先手でゲームを始め、
ゲームが終了するまでの間、
2人は交互に1以上、2Nプラス1以下の
整数を一つずつ宣言します。
どちらか一度でも宣言した整数は
それ以降どちらも二度と宣言することができません。
先に整数を宣言することができなくなった方の
プレイヤーの負けとなり、
負けなかった方のプレイヤーの勝ちとなります。
このゲームでは必ず高橋くんが勝ちます。
高橋くんの立場で実際にゲームを行い、
ゲームに勝ってください。
ほう。
入出力。この問題はインタラクティブな問題。
あなたの作成したプログラムとジャッジプログラムが
入出力を介して対話を行う形式の問題です。
あなたのプログラムが高橋くんの立場で、
ジャッジプログラムが青木くんの立場でゲームを行います。
まず、あなたのプログラムに標準入力から
整の整数Nが与えられます。
その後、ゲームが終了するまで下記の手順を繰り返します。
あなたのプログラムが高橋くんが宣言する整数として
1以上2Nプラス1以下の整数を標準出力に出力します。
どちらかのプレイヤーによって
すでに宣言されている整数を出力することはできません。
09:02
ジャッジプログラムによって青木くんが宣言する整数が
あなたのプログラムに標準入力から与えられます。
はいはいはい。
ただし、青木くんが宣言できる整数が残っていない場合、
代わりにゼロが与えられ、高橋くんの勝ちでゲームが終了します。
ほう。
高橋くんの勝ちでゲームが終了した後、
あなたのプログラムは直ちに終了しなければなりません。
ということは、ゼロが入力された時点で
エグジットしないといけないんですね。
ふんふんふんふん。
まず整数Nが与えられます。
で、渡しスタート。
次に青木くん。
次にまた渡し。
って感じですね。
ふーん。
ファイルにするか。
えー、テストケースがないので
ちょっといかんともしがたいとこなんですが、
まずN、intのインプットはさっきのB問題で取っているので
そのまま流用しましょう。
でだ。
んーと。
そうですね。
大文字Lのリストを作ってしまいましょう。
i in
いや、んー。
んーと、どうしようかな。
どうしようかな。
true
true for i in range n
待って、制約なんだったっけ。
制約っていうかルールなんだっけ。
2人は交互に1以上を
2nプラス1以下。
2nプラス1以下だから
nが10
ん?
nが10与えられたとして
1以上を
21以下か。
1以上を21以下。
だからレンジが
n
かける2
プラス1?
これでどうなる?
ちょっと標準入力10で試してみましょうか。
10の
プリント
l
21
ん?
んーと。
1以上2nプラス1以下。
12:05
0がないんですよね。だから
1、2、3、4、5、6、7、8、9、10
11、12、13、14、15、16、17、18、19、20、21
ん?
1、2、3、4、5、6、7、8、9、10、11、12、13、14、15、16、17、18、19、20
2個プラスされるな。
じゃあこれでいいか。これでいいか。
えーっとで
んーと。
んーと。
now
イコールインと
インプット
if
nowイコールイコール0だったら
exit
で、そうでなければ
んーと
now
マイナスイコール1して
ん?
そっか。先に高橋くんが宣言しないといけないのか。
じゃあ
んーと。
ファイル文作るか。
ファイル
プル
プリント
いや、えーっと
どうしようかな。
ホワインレンジ
レンエルをどっかで取っとくか。
えーっと
レングイコール
レンエル
で、ホワインレンジレング
if
l
i
だったら
プリント
iプラス1
の数字を言う。
で、
lのi番目をフォルスにしておく。
で、ブレイク。
いや、んーどうしようかな。
15:01
普通にインデックス数言った方が早いか。
あーでもそれだと、そうか、数字もあるからいらないね。
えーっとじゃあ
高橋くんと誰だっけ。
青木くんね。じゃあaにしとこうか。
お文字aイコールイントのインプット
で、lのi番目
マイナス1か。i-1番目イコールフォルス。
で、lのi-1番目をフォルスにする前にif
aイコールイコール0だったら
もうその時点で終わりなのでexitです。
例えばをやりましょうか。入力例が
唯一あるのが2ですね。2だったら
んー
あ、そうか、インプットが与えられないから、えーっとこっちでも作らないといけないんだ。
高橋くんが1、3、2
3、4、0。2、3、4、0。
3、4、0。
1、2、3。
3出しちゃダメなのよ。
高橋くん。
んーっと
プリントl
1番目
ん?なんで前、最後
あれ?
ここのフォルスなんだ?
3、1、2、3
お?なんか1番最後がフォルスになってる。
どこで?
あ、そうか。
1番最後の行
lのi-1番目にしてるわ。
a-1番目ですね。
1、2、5ですね。OK。
んー、いったん出してみようか。
インタラク
っとだっけ?なんかこの
入力例が与えられないタイプの問題苦手なんですよね。
18:01
和が出た。
あー、全部和だ。ダメだな。
サンプル和が出るんだ。
あ、違うわ。プリントlしてるからだ。
テヘペロ。
これはOKなのかな?このプリントはOKか?
どこのプリントが残し
あ、これで大丈夫そうですね。
再度ちょっと提出してみて
これでダメだったら解説を見てみますね。
トータACでした。
ではD問題いってみましょう。
多分コーディングするまでもなく
解説見ないといけないことになると思いますが
D問題
スワップ発
問題文
1、2、3の番号がついた3人の高橋くんがおり
3人の高橋くん
青
あ、違うもう。ぐちゃぐちゃだ。
1、2、3の番号がついた3人の高橋くんがおり
赤、緑、青の色がついた3種類の帽子が
それぞれ1つずつあります。
それぞれの高橋くんは帽子を1つかぶっており
高橋くんiが初めにかぶっている帽子の色は
文字SIで表されます。
ここでRは赤、Gは緑、Bは青に対応しています。
これから以下の操作をちょうど10の18畳回行います。
そんな回数やるな。
操作
3人の高橋くんのうち2人を選ぶ。
2人はお互いのかぶっている帽子を交換する。
10の18畳の操作の後、高橋くんiが
文字TIに対応する色の帽子をかぶっているように
することはできますか?
だから10の18畳回操作を行った後
Sの文字列分配されていた配色が
Tの配色に変えられるかどうかですね。
これでも奇数回できるかどうかでやればいいんじゃない?
行動を出すことなく考えようとしているけど。
1回、あるいは3回、あるいは5回っていう
奇数回状態じゃないと出せない
状態だともうNOにすればいいんですよね。
それ以外だったらYESでOKだから
奇数回状態じゃないとできないってなんだ?
1、2、だからどこか1つが揃っている。
1、1、これあれだな、メモ欲しいな。
21:12
コードテストに書くか。
コードテストを黒板代わりにしよう。
R、G、B。
例えば1回目にG、R、B。
2回目にG、B、R。
3回目にどこ変えようかな。
B、BGRにしようか。
BGRか
RBGか。
ちょっとわかったかも。
ちょっとわかったかもというか、
憶測なんですが、やってみるかせっかくなんで。
Sイコールインプットドットスプリット。
スプリットいるかな。
いいか、インプット。
Tイコールインプット。
はい、インレンジ。
なんて言ったらいいかな。
カウント、CNTイコール0にしといて。
IFSI番名とNOTイコールTのI番名。
SとIが違ったらCNTプラスイコール1。
DIFにしとこう。
ディフィカルトになるっけ。
ディフォレンスってなんだっけ。
DIFにしとこう。
難易度みたいになっちゃってる。
で、同じがSUMかな。
SUMだっけ。
セイムじゃなかった。
セイムイコール0。
IFSのI番名イコールイコールTのI番名だったら
セイム2プラスイコール1。
24:02
で、アンサーイコールイエスを用意しといて。
イエス用意するならいらないな。
セイムいらないな。
違うときだけでいいや。
IF全部一緒だったらOK。
あとはどっか一つだけ一緒なのと全部違うのがアウトだから多分ね。
プリントのIFCNTダイナリー1。
どっか違うのが1個なのはOK。
どっか違うのが1個なのがOKか?本当か?
1個でも違うのは1、2、1。
待って待って。
1、2。
全部違うのOKだな。
どっか1、2。
1つだけ合ってるんだとNO。
全部違うのもOKだな。
いやわかんねー。
1つだけにしておきましょうか。
CNTイコール1だったらNO。
そうでなければイエス。
そんなはずないと思うけど。
RGB、RGBだったらイエス。
他の入力例欲しい。
ちょっと提出してみましょうかせっかくなんで。
こんな単調なはずがないけど。
記念にね。
はい、わが出たので解説を見ていきます。
27:02
スワップ8つ。
Bイコール1、Gイコール2、Rイコール3と置き換えて
1、2、3の並べ替えの問題として解説します。
1、2、3の並べ替えは6種類あります。
1回の操作でどれからどれへ変換することができるかを図に表すと以下のようになります。
これを見ると並び替えを2つのグループに分けられることがわかります。
グループAの要素からは1回の操作でグループBの要素に。
グループBの要素からは1回の要素でグループAの操作に変更することができるので
SとTが同じグループであるかどうかを判定すればよいです。
偶数回でってことですね。
さて3要素の並べ替えでなくN要素であった場合はどうすればいいでしょうか。
ここで登場するのが点頭数です。
点頭数はN1からNまでの並べ替え、A1からANに対して
i小なりjかつAのi大なりAのjであるような整数の組、ijの数として定義されます。
そして点頭数が偶数であるような並び替えを偶値間、点頭数が奇数であるような並び替えを奇値間と呼びます。
これが先ほどの2つのグループと対応します。
偶値間に1回の操作を行うと必ず偶値間になるので、
どんなに大きい偶数回の操作を行っても違うグループに変換することはできないのです。
Python例がある。
Python例がある。
Python例がある。
なるほど。
2つある合計で6つのグループのうち、偶値間の方を出しているんですね。
ですとtがどっちも偶値間のグループだったらyes、そうでなければnoを出力するっていうあれなんだ。
これはもう数学的な考えになるのかな。
アルゴリズムの実装云々じゃなくて。
うーん、面白い。
d問題でこんなに短い文で解けるあれがあるんですね。
ちょっと勉強になったな。解けそうだったな、頑張って考えたら。
はい、では今回はここまでにしておきましょう。
お疲れ様です。