ABDの3完！Cは気合の10ペナ！
ひさしぶりにめっちゃしっかり復習したから書く〜
A問題
問題概要
8個の整数たち（配列S）が
- 昇順
- ぜんぶ100〜675
- ぜんぶ25の倍数
この3つの条件に全て当てはまっていたらYes、一つでも違ったらNoと出力してね
考察
条件がいくつかあって、ひとつでもちがうよ…なら速攻No系は、コードもおなじおきもちで書いてあげると速く解けます。
どういうことかというと「全部あってたらYes」ではなく「ひとつでも間違ったらNo」で、式もnotやFalseベースで書いてあげます。
やり方に関しては、即効No吐いておわりにしてもよいし、フラグ管理してもよい。告白だったらとてもかなしい考え方だ…
各条件の判定について
- 神目線で、配列全体を上から見下ろし、全体で判定した方が楽か
- ダンゴムシ目線で、要素ひとつひとつみていかないと、わからないことなのか
を、整理していきます。
①昇順（広義単調増加 S1 ≦S2≦S3...）か
・SをソートしたTという配列を新たに作り、一致するか確かめる
②ぜんぶ100〜675か
・ひとつずつ確かめる。しかたない。人生そういう時の方が多い
③ぜんぶ25の倍数か
・ひとつずつ25で割ったあまりが0か確かめる
・sum(S) % 25 == 0 か確かめる
コード 即座にNo
#入力 s = list(map(int, input().split())) # sを昇順ソートしたtをつくる t = sorted(s) # sと、sを昇順ソートしたtが不一致ならNo if s != t: exit(print('No')) for i in s: # 25で割り切れないならNo if i % 25 != 0: exit(print('No')) # 100未満だったり、675より上ならNo elif 100 > i or i > 675: exit(print('No')) # No条件にひっかからなかったらYes print('Yes')
コード フラグで管理
#入力 s = list(map(int, input().split())) # sを昇順ソートしたtをつくる t = sorted(s) # 条件にすべて合ってると仮定してはじめる（性善説！） flg = True # sと、sを昇順ソートしたtが不一致、または全体が25の倍数でなければNo は 嘘解法ですが通ります… if s != t or sum(s) % 25 != 0: flg = False for i in s: # 100未満だったり、675より上ならNo if 100 > i or i > 675: flg = False # No条件にひっかからずflgがTrueのままならYes そうでなければNo print('Yes' if flg else 'No')
感想
自己肯定感が高く、他人に対しても全肯定癖があるため、反対にするのに時間がかかった。生き方も含め反省。
B問題
問題概要
お寿司やさんお会計問題です。
- N皿食べました
- 配列Cに、N皿分のお皿の色が書いてあります
- 配列Dに、M種類のお皿の色が書いてあります
- 配列Pに、M + 1 種類のお皿の値段が書いてあります。配列Cには、配列Dにない色のお皿も含まれていそうで、そういう時はP[0]で統一価格とします
合計いくら食べたかな…やべえ……
考察
こういう現実にありそうな設定のものは、問題文はさくっと読み、サンプルの方を熟読すると速いです。
実際、問題文読んでると「なんでDとPともにM種類なのにPの長さが + 1、おん？？？」となりがち…
せっかく順番対応してくれているので
- 色と値段を辞書にして、値段表みたいにする作戦
を先に考えましたが、実装がパッと出てこなかったので、本番は
- インデックスをとる作戦
にしました。
Dの長さがM、Pの長さがM + 1、Pの0項目が邪魔だなあ…ならば 取って仕舞えばいいのです
コード インデックスとる
# 入力コーナー n, m = map(int, input().split()) c = list(input().split()) d = list(input().split()) p = list(map(int, input().split())) # 合計出す用ans ans = 0 # 配列pの最初の要素（その他の値段） z = p.pop(0) # 食べた皿たちを順番に見ていく for i in c: # 皿色リストdに存在していたら、値段表配列pから同じ位置の値段をansに足す if i in d: ans += p[d.index(i)] # 皿色リストdに存在してなかったら、zを足す else: ans += z print(ans)
コード 値段表
# 入力コーナー n, m = map(int, input().split()) c = list(input().split()) d = list(input().split()) p = list(map(int, input().split())) # 合計出す用ans ans = 0 # 配列pの最初の要素（その他の値段） z = p.pop(0) # 値段表作成 dとpをzipして辞書を作成 price_list = {i: j for i, j in zip(d, p)} # 食べた皿たちを順番に見ていく for i in c: # 値段表に存在していれば、ansに足す if i in d: ans += price_list[i] # 存在してなかったら、zを足す else: ans += z print(ans)
感想
既存の2配列から1つの辞書を作るの、こうやって書くんだ！へえ！
zipすごい！！
C問題
問題概要
- N人がコイントスをしました。コイントスとは、何回かコインを投げ、表が出た確率を競うゲームだよ
- コインの表が出た回数がA、裏が出た回数がBだよ
- 表が出た確率は、表が出た回数 A ➗ 総回数（A + B）で求められるよ
- 確率が高い順に人1〜Nの番号を出力してね。ただし、同点の人がいたら、番号が小さい順に出力してね。
考察
こういうのがCに出た場合、愚直にA / (A + B)をすると絶対に死にます。戒めえ〜！！！！（本番解けなかったので）
どうして死ぬか、というと 小数同士の比較は、小数にする時点で0.1以降が壊れるので正しくない （理由について、詳しくは浮動小数点でググってね）からです。
解決策としては3つ
式変形をする
もちろん、まず式変形を考えました。
しかし、わたしはまだ算数1年生で、不等式の式変形をする公式解説のような発想など出るわけもなく…ちーん。詳しくは、おしゃれいけめんnok0さんの公式解説を読んでください。A / (A + B) の分子Aにすっげーでっけー数（10100）をかけておき、intのまま比較できるようにする（きりさん解説） 例えば、0.3を30%という表記に直すとき100をかけるように、とにかくでっかい数字にしておくと、Pythonはintの有効桁数がでっかいから大丈夫だよ！というおはなしです。
decimalを使用し、壊れない小数として扱う
ちなみに、今回は分母になる(A + B)が1以上になる制約のため気にしないで良いですが、0を分母に持ってくる（0でわる）とREとなります。
ちなみにちなみに「片方は大きい順で、もう片方は小さい順で」という、一筋縄のソートでいけないやつは 小さい順にしたい方に、-1をかける という脳筋技をすると、ただのソートでいけるようになります👍
※逆でも良いです。つまり、大きい順にしたい方にマイナスをかける。こちらの方が、本問題では出力時に再びマイナスをかける手間と、降順ソートする手間が省けます。が、「小さい順にしたい方にマイナスをかけ、降順にする」の方がパッと感覚的に使いやすいので、わたしはそうしています。
例えば
[1, 2], [2, 5], [1, 3]を[2, 5], [1, 2], [1, 3]にしたい- 普通にソートすると
[1, 2], [1, 3], [2, 5]になってしまう - ので、2項目に-1をかけて
[1, -2], [2, -5], [1, -3]にしてから降順ソートすると [2, -5], [1, -2], [1, -3]🎉
あと…「何人め」の情報を入れてあげたい時は、入力forで使うiを利用してあげるとよきよきです！
コード int状態作戦
# 入力 n = int(input()) # 答え格納用配列 ans = [] # abの入力 for i in range(n): a, b = map(int, input().split()) # ans配列にint状態の確率と、何人めかの情報を入れる。何人めか？は昇順にしたいのでマイナスにしている ans.append([a * 10 ** 100 // (a + b), -(i + 1)]) # ans配列全体を降順ソート ans.sort(reverse=True) # ansの2項目にマイナスをかけて正に戻しながら出力 print(*[-d for _, d in ans])
コード decimal作戦
# Decimalを使えるようにimport from decimal import Decimal # 入力 n = int(input()) ans = [] for i in range(n): # Decimalで受け取ると、壊れないで愚直のままいける a, b = map(Decimal, input().split()) ans.append([a / (a + b), -(i + 1)]) ans.sort(reverse=True) print(*[-d for _, d in ans])
感想
「コイントスにおける成功ってなんだ」というのを調べるのに10分くらいかかった。ゲーム、もっと知っておくべきだ…を何回か思っている。真っ暗な青春を送るとこうなるよ！ぜひいっぱいあそんでね！！
小数について、めちゃくちゃ勉強と教訓になりました。ありがとうnok0さん！
D問題
問題概要
H行W列のグリッドに書いてある文字たちを、スタート(0, 0)から「s⇨n⇨u⇨k⇨e⇨s⇨u...」という順番で辿って、ゴール(h - 1, w - 1)に辿り着けるのか判定してね
考察
- DFSまたはBFSして、h - 1とw - 1にたどり着いてたらOK、あとはぜんぶNoにしよう
- snukeの判定は、剰余使って管理しよう
DFSとBFSについては、よい解説記事がたくさんあるので置いておき…そのうち自分でも書いてみようかな！
で、剰余（%）はとっても便利です。 たとえば、24時間表記を12時間表記にすることを考えてみませう。
- 13 ⇨ 1
- 24 ⇨ 0
- 3 ⇨ 3
このとき、左側の数字に % 12 をしてあげることを考えると、数が0〜12の間で循環してくれるので、うれしくなれます！
これを利用して、5文字のsnukeをぐるぐる循環させてあげます。
コード DFS
import sys sys.setrecursionlimit(10 ** 7) # 入力 h, w = map(int,input().split()) g = [list(input()) for _ in range(h)] s = 'snuke' # xは0 ~ hの列番号, yは 0 ~ w の行番号, zはsnukeカウント用 def dfs(x, y, z): if not(0 <= x < h) or not(0 <= y < w) or g[x][y] != s[z % 5]: return if x == h - 1 and y == w - 1: exit(print("Yes")) dfs(x + 1, y, z + 1) dfs(x - 1, y, z + 1) dfs(x, y + 1, z + 1) dfs(x, y - 1, z + 1) dfs(0, 0, 0) print("No")
コード BFS
from collections import deque h, w = map(int, input().split()) g = [input() for _ in range(h)] s = 'snuke' # 上下左右を調べるための距離配列 dx = [0, 1, 0, -1] dy = [1, 0, -1, 0] def bfs(): que = deque() # 1項目は0 ~ hの列番号, 2項目は 0 ~ w の行番号, 3項目はsnukeカウント用 que.append([0, 0, 1]) # すでに行ったところを入れていく用 gone = set() while que: v = que.popleft() x, y, z = v[0], v[1], v[2] if x == h - 1 and y == w - 1: exit(print('Yes')) elif (x, y) in gone: continue gone.add((x, y)) for i in range(4): ny = x + dy[i] nx = y + dx[i] if 0 <= ny < h and 0 <= nx < w and g[ny][nx] == s[z % 5]: que.append([ny, nx, z + 1]) bfs() print('No')
感想
BFSわかんねえ！なってたらainemさんとるかごんくんとぷせうどさんが助けてくれた…ありがとうございます！！
そして、もしや？となり、1文字めがsじゃなくても通ることを確認。ふええ
来週のburiodenは
静かな渓谷で神と釣りしてからABCにでます！自然ぱわあ！！
