コンテストの紹介
AtCoder Beginner Contest 230、A問題、AtCoderクイズ3、問題文。
AtCoderで定期的に開催されている国際的な権威があるコンテストである、AtCoder Grand Contest、以下、AGCは今までに54回開催されてきました。
皆さんがちょうど参加している230回目のABCである、ABC230と同様に、当初はN回目のAGCのコンテスト名には、Nを3桁になるように0埋めした数が割り振られていました。
1回目のAGCはAGC001、2回目は002。ところが、最新の54回目のAGCのコンテスト名はAGC055で、回数より1大きい数が割り振られています。
これは、AGC042が社会情勢の影響で中止されて結板となったため、42回目以降に開催されたコンテストでは、開催された回数より1大きい数が割り振られているからです。
さて、ここで問題です。整数Nが与えられるので、N回目に開催されたAGCのコンテスト名を、AGCXXXの形式で出力してください。
ここで、Xには0埋めがなされた3桁の数が入ります。
A問題なのに問題文めっちゃ長いですね。
入力例は、1から54までの数字が与えられます。
42回目が欠席・結板になったので、42以上のものは1つプラス指定ですね。
0埋めってどうやるんだっけ?
Python 0埋め
右寄せ0埋め
これですね。ZFILL
STR.ZFILLで数字、0埋めしたい数を入れる。
Nを入力で受け取って、もしNが42以上だったら、1プラスしてSTRに戻して、ZFILL3でプリントしたらOKですかね。
ちょっとコードテストしていきます。
Nイコールイントのインプット。
Nダイナリイコール42だったら、Nプラスイコール1でプリント、ダブルクオーテーション、AGCプラスSTRN.ZFILL3でいかがでしょうか。
入力例1は42、AGC043、入力例2は19、AGC019ですね。
入力例3は1、001、入力例4は50だから51が出たらOK。
大丈夫そうなので提出していきます。
はい、ACしましたのでB問題いきます。
B問題。トリプルメトロ?メーター?METRE?なんだ。
問題文。文字列Sが文字列Tの部分文字列であるとは、次の条件を満たすような整数IJ、1小なりイコールI小なりイコールJ小なりイコールTの文字数が存在することを言います。
TのI文字目からJ文字目までを順番を変えずに抜き出してできる文字列がSと一致する。
文字列TをO○×を10の五乗項結合した文字列として定めます。
OXXかな。文字列Sが与えられるので、SがTの部分文字列である場合はイエスを、そうでない場合はノーを出力してください。
Tの始めの方を抜き出すと、文字列Sが与えられるので、SがTの部分文字列である。
入力はSだけなんですね。文字列Tっていうのを想定しているってことかな。
OXXを10の五乗項結合した文字列だから、それをもう作っちゃって、inで入ってるかどうかを確定させればいいんじゃないの?
TイコールOXX×10の五乗。で、SイコールインプットプリントイエスイフSインティエルスノーでいいんじゃない?
入力例1はイエス。入力例2はノー。入力例3はイエス。
大丈夫そうですね。提出します。はい、ACしたのでC問題いきます。
C問題。Xドローイング。問題文。上下左右に広がるN×Nのマス目があり、最初全てのマスは白く塗られています。
このマス目の上からI行目、左からJ列目のマスをIJで表します。
高橋くんは1以上N以下の整数ABを持っており、次のような操作を行います。
マックス1-A1-B小なりイコールK小なりイコールminN-AN-Bを満たすすべての整数KについてA-KB-Kを黒く塗る。
マックス1-AB-N小なりイコールK小なりイコールminN-AB-1を満たすすべての整数KについてA-KB-Kを黒く塗る。
この操作を行った後のマス目についてP小なりイコールI小なりイコールQかつI小なりイコールJ小なりイコールSを満たす各マスIJがそれぞれ何色で塗られているか求めてください。
Nが10の18乗なので4分とかではできなさそうって感じですかね。
ちょっと何言ってるかわかんなかったな。
シャープとドットで出力白ってことですね。シャープが黒、ドットが白で、入力はNABが1行目、PQRSが2行目に与えられる。
とりあえずインプットしましょうか。
NABイコールマップイントインプットドットスプリット。
2行目もコピペで。
2行目の変数はPQRS。
N×Nのマス目があって1-A1-Bすべての整数KについてAプラスKBプラスKを黒く塗る。
N×Nのマス目があってNが10の18乗でってなると10の18乗って1回の方分も無理なのかな。
1回ちょっとやってみましょうか。
4iインレンジ10の18乗プリント。
ダメっぽいですね。
方分が使えないとなるとわからなくなってくるな。
マス目系ってだいたい方分でやってきたので。
そもそもだってマス目を作れないがこれだと。
1つ目の操作で2つ目の操作でこの4マスが黒く塗られます。
出力例見てもよくわかんないな。
操作自体は1つ目2つ目でいいのか。
入力例3すごいことになってるな。
問題文の説明
入力が32bit整数型に収まらないことがある。
ちょっと解説見ましょうかこれは。
C問題。
文字が多い。文字というか条件が多いな。
ちょっととびとびで読みますね。
これを愚直にシミュレーションしようとすると
塗られるマスが最大10の18乗個もあることになり時間制限に間に合いません。
この条件1つ目の条件を言い換えます。
これは。
1小なりイコールAプラスK小なりイコールNかつ
1小なりイコールBプラスK小なりイコールNを満たす全ての整数型について
AプラスKBプラスKを黒く塗ると言い換えられる。
AプラスKN。
なんでそうなる?
3×10の5乗以下。
実際はより厳しく√30万547回以下で操作できますって書いてる。
法文作ってるな。
Cプラプラの実装ばかりなのでユーザー解説。
問題文に数式がごちゃごちゃと登場してよくわからないときはとりあえず図を書いてみましょう。
以下の図は10、6、4、7、9、6、9という入力に対応するマスの塗り方です。
問題文からこの図をイメージすることができなかった方はこの図を見ながらもう一度考え直してみるといいかもしれません。
バッテンに黒く塗られているマスですね。
問題文をもう一回よく見ようかな。
max1-a 1-b
すべての整数kについて
そうか。一旦これちょっとコードテストで出すだけ出してみましょうか。
この条件に当てはまる範囲っていうのを。
printmaxなんだっけ?
これちょっとコピペ。
条件1がmax1-aと1-b。
で、min n-a, n-b。
条件2がprint1-a, b-nなんちゃらですね。
一回実行してみて。
あれ?デシマルリテラル。
で、マイナスじゃないこれ。ハイフになってる?
ハイフになってるね。
実行。-1と2。で、-2と1。
だから、-1から2まで、-2から1までっていうそれぞれのkについて
a++k, b++kを黒く塗るのと、a++k, b++kを黒く塗る。
なので、a++k, b++k。
3たす-1で2でしょ?
あ、ちゃうわ。-1, 0, 1, 2か。
kの範囲っていうのは。
あーめんどくせー。
ちょっと他の方のPythonの提出例を見ておきます。
こういうぐわーっと文章で出されると
アレルギーが出て
一気に考える力が落ちちゃうんですよね。
慣れていかないとですね。
では、また次回。お疲れ様です。