00:04
アットコーダービギナーコンテスト171回目 a 問題 アルファベット
問題文 a 大文字か a 小文字のいずれかひちょん
いずれか一文字 a が入力されます
アルファか
アルファが a 大文字なら大文字の a, a 小文字ならsmall a と出力してください
アルファは a 大文字の a から z または a 小文字の a から z であるですね
まあいいか a イコールインプット
プリント
ラージエイ
イフ
a ドット
えっと 大文字判定ってどうやるんだっけ
パイソン
大文字小文字
判定判定
is
is upper と is lower ですね だから
ドット is upper だよね
bool 型で true false で返してくるので
入力したものが is upper だったら大文字の a
else そうでなければプリント小文字 a
提出
はい c したので b 問題いきます b 問題 ミックスジュース
問題文 ある店で n 種類の果物 果物 1 から n が売られており
それらそれぞれの価格は 1 個あたり pi から pn 円です
この店で k 種類の果物を1個ずつ買うとき
それらの合計価格として考えられる最小の金額を求めてください
k 種類の果物
果物 1 円 はいはいはいはい えーっと だから
とりあえず入力しましょうか nk
nk n 個あって k 個買います map イントインプット
ドットスプリット で p
が価格帯ですねリストの
マップ
イントイント
ドットスプリでまあ愚直に行ったほうがいいですね for i in レンジ
警戒
やります
アンサーイコール0で定義しておいて4分の外に
フォアインレンジ経営
03:01
えっと
どうやらいいかな
アンサープラスイコール
民 min
カッコ p これで p の中の最小数が選択されますで
その最小数を取った後は
それを消したいので
p
のカッコ
p ドット インデックス
民 p
イコール
どうしようかな空の文字列とかにしておこうかな
制約は1000でしょ1000だから
1万とかにしておこうか10の
10の5畳とかを入れておきます
で最後プリント
アンサーで
どうでしょうかインデックス
関数の使い方が間違ってなければいけるはず
出力例1は210
が出ました出力例2は1000が出たら ok
一応リスト見ておきましょうか
プリント p
プリント p で確認
ok ですねちっちゃい奴から順番に
10万に変換されていっているので
で
扱い方は ok 提出します
はい ac したので c 問題に行きます c 問題
1
クアドリ
クアドリリオン&
ワン
ダルメシアンズ
問題文ロジャーは彼の元に突如現れた何これ何匹
1 10 100 千万 十万 百万 一千万 一億 十億
百千
一十百千万億兆
一千兆一匹
の犬をすべて飼うことを決意しました
犬たちにはもともと1から一千兆一までの番号が振られていましたが
ロジャーは彼らに以下のルールで名前を授けました
1234
06:01
26番の番号が付いた犬はその順に a b
z と命名されます
27から702番の番号が付いた犬はその順番に a a から z z と命名されます
703番から18,278番の番号が付いた犬はその順に a a a a a b から
z z z
18,279匹目から
475,254番の番号が付いた犬はその順に a a a a から z z z z
以下略
つまりロジャーが授けた名前を番号順に並べると a b c d
z a a a b a c
a z z z
違う番号順だから
a z b a b b b c b z
z a z b
ほう
ロジャーはあなたに問題を出しました番号 n の犬の名前を答えよ
えっと
26進数で考えちゃダメかこれ
いけそうな気がするな
これ26進数か27進数か
a b c d e f g h i j k l m n o p q r s t u v w x y z
26個あるから27個目で繰り上がるから27進数になるんじゃないですかこれ
アルファベット
27進数
日本語じゃないとダメか
アルファベット
27
進数
はいはい
大文字のアルファベットは26種類なので実質26進数なんじゃないのという感じがしますが
一般的な n 進数とは違った性質を持ちます
0に対応するものがないから
だから何 l 1 表記の列番号から10進数への変換
09:08
わかんなくなっちゃった
と
n イコール
インプットでだでだ
26進数
入力例1は2出力例は b 入力例には27出力例は a
入力例3
123456789出力例は j j d d j a
27をかけていきゃええのか
うっすらイメージはできているが
アルファベット
10進数変換
ああいやこれは
テキストと10進数の相互変換ができます
勝手に変換されるんじゃなくてその理屈を知りたいんだけどまぁ1回やってみましょうか
えっと
こっちか123456789
40 50 51 違うんだよなぁ j j d d j a は
はい
106 106 100 100 106 97 だからこれに27の何乗っていうのをかけてる
んだろうなぁ わかんないなぁ
解説見ますか
c いいものパイソンの実装例がありそう
まず10の15乗という数は現代の我々の計算機にとっても大きく
何らかの処理をこの程度の回数を行って実行時間を2秒以内に収めることは不可能です
あそうなんかコンテスト的に確か2秒以内に1問
回答できる
プログラムコードを書きなさいみたいな
あれがあるはずなんですよねだからあんまり処理が重くなると
オーバーしちゃってエラーというか間違いですよっていうのが返されてしまい
ます
素直な方針は問題文で括弧以下略となっている部分を計算し
12:02
まず番号 n の犬の名前の長さを求めることでしょう
以下番号 n の犬の名前を名前 n と書きます
i イコール1234のそれぞれに対し長さが愛であるような名前は26の愛情子存在します
よって名前1から26の長さは1
名前26たす1
26たす26の事情の長さは2
名前26たす26の事情たす1
26たす26の事情たす26の惨状の長さは3です
最終的に26たす26の事情たす26の惨状たす点点点点26の11条は
3817158266467286大なり10の15条プラス1より
長さ11での計算までに名前 n の長さが判明します
これにより名前 n の長さが l であると判明したとします
あーなるほどね26の何条っていうのを足していった結果
10の15条っていう制約よりも大きくなるところが
11条だと
だからマックスでも長さ11の名前
で収まるだろうってことですね
すると長さが l であるような26の l 上この名前の中で
名前 n が辞書順で n マイナス
括弧26たす26の事情たす点点点点点26の i マイナス1条
この値を k とします番目の名前であることもわかります
うん
残る問題は長さが l であるような文字列の中で辞書順で
定番目のものを求めようというものです
この問題の解き方がよくわからなければアルファベットが a b 点点点
j の10文字であったとして考えるとわかりやすいでしょう
例えばこの状況では長さ3の名前は a a a a a b から a a j
a b a から j j j の10の3乗1000個存在します
このうち例えば辞書順で
246番目のものは b d e です
このように k マイナス1の受信表記での1の位が辞書順で定番目の名前の最後の文字に
10の位が名前の最後から2番目の文字に
10の愛情の位が名前の最後から i プラス1番目の文字に対応します
アルファベットが26文字の場合も同様に k マイナス1の26振表記における26の愛情の位が名前の最後から
i 番目の文字に対応します
これらの位の位置の求め方の例は次の通りです
この手法に関しても動作原理がよくわからなければ受信表記の場合で考えるとわかりやすいでしょう
15:04
変数 x を k マイナス1で初期化し x が0となるまで以下の操作を繰り返す
あーそうそうそう なんか何とか真数の簡単な求め方というか
愚直な求め方ってこれって言いますね
x を26で割った小が9余りが r であるとする
この操作が相変え目に実行された時の r が k マイナス1の下から i 番目の桁である
x を9で置き換える
Python での実装例ありがとうございます
4i 連字
ans を空の文字列にしている n イコールイントインプット
4i インレンジ1から99
if n 小なりイコール26の i 乗
の場合 n マイナス1
4j インレンジ i
anser プラスイコールチャーのオーダーのアルファベット a プラス n% 26
あー何をやっているか分かるが
n 割る26でブレーク
何をやっているか分かるがなぁ
ここまでは追っつかないですね思考が
else n マイナスイコール26の i 以上でプリント ans の逆
かっこ付録より簡単な実装例
n イコールイントのインプットアンサーは空の文字列
while n 大なり 0 の場合 n マイナスイコール1
anser プラスイコール chr
ORD の小文字の a プラス n% 26
n 割る26
n が 0 以上の間ずっとやると
でプリント ans の逆
n マイナスイコール1
ans
プラスイコール
あ
はぁはぁはぁはぁはぁ
えっと n を減らしていきつつ
n% 26 っていうのが
だからその桁における
何番目ってことですね何乗みたいなのを考えなくて ok
で ORD っていうのは文字コードですっけ
小文字の a は例えば56だよみたいな
数字が当てはめられているんですけどそれに
18:01
プラスすることで
a から z のどこかっていうのが分かります
でそれをさらに chr でもう1回文字コードから
数字に
このアルファベット文字はこの数字に当てはめられているよっていうのを入れます
でアンサーにプラスイコールする
アンサー
あっ違うん
わかんないわかんないわかんなくなってきた chr ORD の chr
あれ
答えが
あそうか名前を答えなさいだから
えっと文字コードを数字にしてこの桁の
何番目のアルファベットかっていうのを定義した後数字に戻してアンサーにプラスしてるんだ
違うわ名前にプラスしてるんだあーもうややこしいな
解説を見てくださいややこしいと思った方は
なんとなく理解はできたけど
これをパッと実装に移せるっていうのはまだまだちょっと難しいです
ではまた次回お疲れ様です