AtCoder Begginers Selection "Traveling"
なんとかクリアした。
問題としては、
時刻t に座標p = (x, y)にいてて、時刻t2に座標p2 = (x2, y2)にちょうどその場所に存在することができるかという問題。
時刻が1つ進むごとに、x軸、y軸のいずれかで必ず正負いずれかの方向に1進まないといけない（同じ場所にとどまることはできない）。
とりあえず、時間内にp2まで到達できるかを調べないといけないので、許容移動時間と最短到達距離を求めてみる
許容移動時間はt2 - t
最短到達距離は「(x2 - x)の絶対値」 ＋「(y2 - y)の絶対値」。マイナス方向にも１移動できるので、移動距離は絶対値で取らないといけない。
ここで移動時間のほうが、最短到達距離よりも大きい場合は、そもそも到達できないので、ダメということが分かる。時速1キロで歩いている人が5時間後に10キロ地点に到達しないのと同じことです。
それ以外の場合は、とりあえず目的地まではたどり着けるということ。ただし、問題はここからで、時刻が１つ進むたびに必ず1マス移動しないといけないので、到達できても時刻t2にその場所に居られるかはわからない。なので、それを調べる。
まず、残り時間の確認。目的地に到達してから、時刻t2までの残り時間は許容移動時間－最短到達距離で求められる。この残り時間で同じ場所にとどまることができるのか。ここから気づくまでが長かった…
時刻が1つ進むたびに、x軸、y軸いずれかで必ず正負の方向に１つ進まないといけない、ということは、偶数時間の場合は正の方向への移動距離と負の方向への移動距離を相殺させて同じ場所に帰ってくることができるけど、残り時間が奇数時間の場合は、相殺できず（正負の何れかの方向に１進んでしまう）同じ場所にとどまることができない。
なので、それをそのまま判定方法にもちいればOK。
提出したコードは次の通り
# シカのAtCoDeerくんは二次元平面上で旅行をしようとしています。 # AtCoDeerくんの旅行プランでは、時刻 0 に 点 (0,0) を出発し、 1 以上 N 以下の各 i に対し、時刻 ti に 点 (xi<200b>,yi) を訪れる予定です。 # AtCoDeerくんが時刻 t に 点 (x,y) にいる時、 時刻 t+1 には 点 (x+1,y), (x−1,y), (x,y+1), (x,y−1) のうちいずれかに存在することができます。 # その場にとどまることは出来ないことに注意してください。 AtCoDeerくんの旅行プランが実行可能かどうか判定してください。 def traveling(time1, x1, y1, time2, x2, y2): travelingTime = time2 - time1 xsum = abs(x2 - x1) ysum = abs(y2 - y1) totalDistance = xsum + ysum # 総移動距離 if travelingTime < totalDistance: # 最短距離で移動しても時間的に間に合わない ret = False elif (travelingTime - totalDistance) % 2 == 1: # 目的地に最短で移動して、奇数時間残っている # ⇒同じ場所にとどまれないためNG ret = False else: # 目的地について偶数時間残っている # ⇒右＋左、上＋下の繰り返しで同じ場所にとどまれる ret = True return ret ans = "Yes" timeMax = int(input()) time1 = 0 time2 = 0 x1, x2, y1, y2 = 0, 0, 0, 0 for i in range(timeMax): time2, x2, y2 = map(int, input().split()) if traveling(time1, x1, y1, time2, x2, y2) == False: #print("timw1: {} time2: {}",time1, time2) ans = "No" break time1 = time2 x1 = x2 y1 = y2 print(ans)
CTF(Capture The Flag) に初めて挑戦してみた
CTFというのがあるというのを最近知った。
よくわかってはいないけど、システムをクラッキングしたり、暗号を解析したりして、「フラッグ」という文字列を発見するゲームみたいなものらしい。
というので、少し試しにやってみた。
問題はこれ
CpawCTF - Main page
問題文で与えられている文字列からフラッグを探す。
与えられている文字列は、シーザー暗号で暗号化されているから、復号しないといけない。
シーザー暗号は、アルファベットの文字を3文字ずらすという手法なので、3文字前に戻してやればいい。たとえば、"a"という文字をシーザー暗号で暗号化すると、3文字ずらせばよいので、"d"となる。これを復号化するときは3文字前にもどせばよいので、c, b, aと数えていって、答えは"a"となる。
というわけで、復号するプログラムはこんな感じに書いてみた。
# https://ctf.cpaw.site/questions.php?qnum=6 # 暗号には大きく分けて、古典暗号と現代暗号の2種類があります。 # 特に古典暗号では、古代ローマの軍事的指導者ガイウス・ユリウス・カエサル（英語読みでシーザー）が初めて使ったことから、名称がついたシーザー暗号が有名です。 # これは3文字分アルファベットをずらすという単一換字式暗号の一つです。次の暗号文は、このシーザー暗号を用いて暗号化しました。暗号文を解読してフラグを手にいれましょう。 # 暗号文: fsdz{Fdhvdu_flskhu_lv_fodvvlfdo_flskhu} import re # 正規表現モジュール def alphabetShiftThree(cryptedString): targetString = list(cryptedString) decodeString = list() pattern = '[a-zA-Z]' for i in range(len(targetString)): if re.match(pattern, targetString[i]): # アルファベットの時だけ3文字ずらす decodeString.append(chr(ord(targetString[i])-3)) else: decodeString.append(targetString[i]) return "".join(decodeString) s = "fsdz{Fdhvdu_flskhu_lv_fodvvlfdo_flskhu}" print(alphabetShiftThree(s))
スクリプトを書いていて、少し気になったのは、シーザー暗号はアルファベットだけが対象っぽいってところ。なので、暗号化された文字列がアルファベットのときだけ復号処理をしないといけないので、正規表現で判定することにした。
「3文字ずらす」という方法は、文字をord関数に与えると、そのユニコード値を返してくれるので、それを-3した数値をchr()関数で再度文字化することで実現。
最後は、全部joinして、文字列化したものを返せばOK。
AtCoderBegginersSelection "白昼夢"
英小文字からなる文字列 S が与えられます。 Tが空文字列である状態から始め、以下の操作を好きな回数繰り返すことで S=T とすることができるか判定してください。
T の末尾に dream dreamer erase eraser のいずれかを追加する。
これは難しかった。
与えられた文字列Sが、条件の文字列の組み合わせから作ることができるかを判定しなさいという問題。
最初は、文字列Sを先頭から、条件の文字列と突合していけばいけるやん！と思ったのだが、先頭から見ていくと重複するように作られてるんですね。どういうことかというと、例えば、Sに"dreamer"という文字列が含まれている場合、本当は”dreamer"で判定OKにならないといけないのに、候補文字列の”dream"でも判定に引っ掛かり、残った"er"でどの候補文字列とも一致しなくなって、判定NGが出てくるようになってるんですよ。うーむ。。。困ったな。
先頭から見ていくのがダメなら、後ろから見ていくか？と気づいたのは、1時間以上考えてからでした（汗）。後ろからだと、重複部分がないんです！
それで提出したコードがつぎ。
# -*- coding: utf-8 -*- # 英小文字からなる文字列 S が与えられます。 Tが空文字列である状態から始め、以下の操作を好きな回数繰り返すことで S=T とすることができるか判定してください。 # T の末尾に dream dreamer erase eraser のいずれかを追加する。 def daydream(s): # 組合せ文字列→1文字ずつ判定に使えるようにリストで保持する dream = list("dream") dreamer = list("dreamer") erase = list("erase") eraser = list("eraser") # 組合せ文字列リスト stringList = [dream, dreamer, erase, eraser] # S == Tの判定結果 ret = "YES" # 被判定文字列の文字数を取得 i = len(s)-1 # ループ１：被判定文字列を後ろから1文字ずつ確認する while i >= 0: # ループカウンタを被判定文字列へのポインタとして扱うためfor 文は使えない # for i in range(len(s)-1, -1, -1): flg = False # ループ２：組合せ文字列リストに格納されている文字列を1つずつ取り出す for j in range(len(stringList)): l = 0 # 被判定文字列のポインタ操作用変数 # ループ３：組合せ文字列の後ろの文字から突合 for k in range(len(stringList[j]) - 1 ,-1, -1): if s[i - l] != stringList[j][k]: # 一致していない文字が出てきたら次の文字列へ break # ループ３ if k == 0: # 文字列と最後まで一致していれば flg = True i = i -len(stringList[j]) # 被判定文字のポインタを突合文字列の文字数分だけ前に進める l = l + 1 # 被判定文字列の次の文字を確認するため操作用変数を1つ前へ if flg: break # ループ２ if not flg: # どの組合せ文字列の文字とも一致しない場合は、S==T にならないのでNOを返す ret = "NO" break # ループ１ return ret s = list(input()) print(daydream(s))
後ろから1文字ずつ、Sと候補文字列を突合していって、どの文字とも一致しなければS==Tにはならないと判定できる。
これで実現しようとしたときに、すべての文字列をリストに入れて、1文字ずつカウンタ変数で処理していこうと考えてた。C言語で文字列を扱うときにポインタを使うみたいに。それで最初はfor文のカウンタ変数i をポインタ代わりに使おうとしたんですけど、どうもうまくいかない。それでよくよく調べてみると、Pythonのfor文で使うrange()関数というのは、range型のオブジェクト（リストみたいな感じのデータ型らしい）を返し、for文ではそのオブジェクトの要素を1つずつ順に取り出してループさせる仕様みたい*1
なので、forループの中でカウンタ変数をいじくって処理を飛ばしたりさせることはできない。ループ冒頭で次の要素を取得してカウンタ変数に代入させるため、ループ内で値を変えてもリセットされるから。
そういう使い方をしたければ、ループ外で変数を用意してWhileループにして、カウンタ処理を記述するしかなさそう。
処理自体は、文字列Sを後ろから1文字ずつ、候補文字列の後ろから突合していく。うしろから突合していって、候補文字列の文字数分前に進めることができたら、その候補文字列とは一致していたということなので、Sの突合開始位置を、一致していた文字数分だけ前に進める。最後まで一致していれば、i は自動的に-1になり、一番大きいwhileループを抜けることができる。というのは、リストの初めの要素は0番目の要素なので、例えば残り5文字を突合して、一致していた場合、4（突合開始位置となるリストの添え字）-5（一致していた文字数）＝-1なので。
*1:— like-9922 luke (@9922Like) 2022年3月23日
AtCoder Begginers Selection "Some Sums" と "Card Game for Two"
1 以上 N 以下の整数のうち、10 進法での各桁の和が A 以上 B 以下であるものの総和を求めてください。
これは割と簡単だった。
Nまでの整数を文字列に直して、1文字ずつ再度整数に変換
→条件に合致するかを調べる
理屈的には、上に書いたことで終わってるんだけど、「1文字ずつ整数に変換」をPythonでどうやるのかが分かんなくて、結構苦戦した。
それで調べると、Pythonでは文字列をリスト関数にぶち込むと、その文字列を1文字ずつ要素にしたリストが出来上がるらしい。それで、そのリストから1要素ずつ取り出して再度数値型に変換することで何とかクリアできた。
なんかC言語みたいな感じやなと思った。
それで、提出したコードが次。
# -*- coding: utf-8 -*- # 入力値の取得 n,a,b = map(int, input().split()) # 各桁の数値を格納する変数 placeNums = list() # 各桁の数値の和 sumPLaceNum = 0 # 各桁の数値の和がa以上 b以下の場合の整数のリスト sumNumList = list() # 答え someSum = 0 # 条件に合致する整数を探索 for i in range(n+1): # 変数を初期化 sumPLaceNum = 0 # 整数を文字列型に変換し、それぞれの文字を要素とするリストを作成 placeNums = list(str(i)) #print(placeNums) # 各文字を数値に再変換→合計 for j in range(len(placeNums)): sumPLaceNum += int(placeNums[j]) #条件に合致するときのみ整数をリストに追加 if sumPLaceNum >= a and sumPLaceNum <= b: sumNumList.append(i) # 探索した整数を合計する for k in range(len(sumNumList)): someSum += int(sumNumList[k]) print(someSum)
N枚の整数が書かれたカードがあり、2人がそのカード順番に引いていく。2人ともが、カードの合計が最大になるようにカードを引くとき、先行の合計と、高校の人の合計の差はいくらになるか
これも簡単やった。
「2人ともがカードの合計が最大になるように引く」⇔「カードを昇順に並べて上から順に交互に引いていく」
というだけ。
Pythonだと、リスト型にsort()メソッドというのがあるので、これを適用して、あとはループで交互に用意した変数に足しこんでいく。
これ、Pythonだとメソッドがすでに準備されているから簡単なんだけど、C言語とかC++とかだと、ソートのアルゴリズムも自分で記述しないといけないのかな。だったら難しいなぁ…
提出したコードが次。
# -*- coding: utf-8 -*- # 枚数の取得 n = int(input()) # カードリストの取得 cardList = list(map(int, input().split())) aliceSum = 0 bobSum = 0 # ターンフラグ aliceTurn = True # カードリストをソート cardList.sort() # カードを1枚ずつ交互に引いていく→ソートしてあるので山札の1番上が最大の点数 for i in range(n-1,-1,-1): # アリスのターン if aliceTurn: aliceSum += cardList[i] aliceTurn = False # ボブのターン else : bobSum += cardList[i] aliceTurn = True print(aliceSum - bobSum)
この3連休のうち、後半の2日は、AtCoderに登録して、問題を解いてみたら終わった。ハマりそうな予感がする。
AtCoder Begginers Selection "Coins"
500円玉、100円玉、50円玉の3種類の硬貨の枚数と合計金額が与えられ、合計金額ちょうどとなる枚数の選び方は何通りあるか
合計金額ちょうどになるときの判定の仕方と、そのカウントをどうしたらいいのか。
合計金額ちょうどの判定方法は、
[合計金額]
＝500 × [500円玉の枚数] + 100 × [100円玉の枚数] + 50 × [50円玉の枚数]
で判定できるので、このときに発見した判定方法の数を１つ増やすことができる。
そして、各硬貨の枚数は、標準入力で与えられるので、0枚からその枚数までカウントアップして、そのそれぞれの場合に上記の判定式に当てはまるかどうかを調べていけばいいので、
・500円玉が0枚から最大枚数まで
・・100円玉が0枚から最大枚数まで
・・・50円玉が0枚から最大枚数まで
の3重ループで実現できるから、提出したコードは次の通りになりました。
# -*- coding: utf-8 -*- def cntCoins(num500, num100, num50, sumPrice): ways = 0 # 500円玉を0枚から持っている枚数までループ for i in range(num500 + 1): # 100円玉を0枚から持っている枚数までループ for j in range(num100 + 1): # 50円玉を0枚から持っている枚数までループ for k in range(num50 + 1): if i * 500 + j * 100 + k * 50 == sumPrice: ways += 1 return ways ######### # 枚数の入力 num500 = int(input()) num100 = int(input()) num50 = int(input()) # 合計金額の入力 sumPrice = int(input()) print(cntCoins(num500, num100, num50, sumPrice))
最初、range()関数の引数に与えた数までカウントしてくれないことを知らず、そこ少し手こずってしまった。たとえば、range(5)を与えると、その戻り値は[0, 1, 2, 3, 4]となるんだね。引数に与えた数値はMAXではなく、0からのカウント数と覚えなくては。
AtCoderBegginersSelection "Shift only"
n個の整数 A1, ... , Anについて、次の操作を何回行えるか。
操作α：整数がすべて偶数であるときは、２で割ったものに置き換える
これなかなか難しかった。
2重ループにしないといけないということに気づくまでに時間がかかっちゃった。まず1つ目のループは、整数リストに対して、操作αを可能な限り繰り返すというループ。そして2つ目のループは、整数のリストの要素を１つずつとりだして、それが偶数であるかを確認し、2で割った商に置換するかどうかを行うという、操作αを具体化するループ。
２つ目のループ完了後に、中身が置き換わった新たな整数リストが出来上がっているので、それに対しても２つ目のループを再度行うという感じ。
import numpy as np # -*- coding: utf-8 -*- # 個数の入力 n = int(input()) # 黒板に書かれている整数リストの取得 numList = list(map(int, input().split())) # 何回除算ができるかのカウンタ divCnt = 0 # 整数リストをすべて２で割り切れることができたか divFlg = True #リストの要素がすべて2で割り切れる間は繰り返し while divFlg: # リストの要素分繰り返し for cnt in range(n): #取り出した要素が2で割り切れるか if numList[cnt] % 2 == 0: #割り切れた時は、その商をリストの要素に代入 numList[cnt] = numList[cnt] / 2 else : #割り切れなかったときはフラグをFalseにする divFlg = False #リストの要素をすべて２で割り切れた時だけ1回カウントする if divFlg: divCnt = divCnt + 1 print(divCnt)
２つ目のループが完了した後に、すべて２で割り切れたかを確認するために、論理値型のフラグを使いました。このフラグがTrueのときにのみ、操作αが一回完了したと解釈できるので、カウンタを１つインクリメントすることで実現しました。
AtCoderをはじめてみた
とりあえず登録はしてみたものの、何をどうやればいいのかよくわかってない。とりあえず「AtCoder Beginners Selection」というのがあったので、それを上から順に3問ほどやってみたけど。。。もう、恥ずかしいくらいテストをパスしないのね。
たとえば、次のような問題。
標準入力で、スペース文字区切りの２つの整数が与えられる。それら2つの整数の積が偶数か奇数か判定せよ。
標準入力だから、とりあえずはinput()関数ね。あれ？でもinput()関数で受け取った文字列をどうやって２つの整数に分割するんだ？みたいな感じ。
それでなんとか提出できたのが次のコード*2
# -*- coding: utf-8 -*- # スペース区切りの整数の入力 b, c = map(int, input().split()) if (b*c) % 2 == 0: print("Even") else : print("Odd")
標準入力で受け取った文字列をsplit()メソッドで分割。分割された文字列を要素とするリスト型になっているので、それぞれの要素を引数にint()関数を適用するmap()関数を使用して、ようやく２つの整数を手に入れることができた。
たったこれだけのことをするのに、たぶん20分はあれこれ調べたんじゃないかなぁ。
まぁ気長にゆっくりと勉強しながらやっていこう。 :-)
*2:ソースコードの埋め込み方は次の記事を参考にしました https://codelife.cafe/entry/2018/05/22/%E3%81%AF%E3%81%A6%E3%81%AA%E3%83%96%E3%83%AD%E3%82%B0%E3%81%A7%E6%9B%B8%E3%81%84%E3%81%9F%E3%82%B3%E3%83%BC%E3%83%89%E3%83%96%E3%83%AD%E3%83%83%E3%82%AF%E3%81%AB%E8%A1%8C%E7%95%AA%E5%8F%B7%E3%82%92 はてなブログでソースコードを表示させる方法 - コンサルでデータサイエンティスト
