ABC232(M-SOLUTIONS) D - Weak Takahashi
大事故でした。。。
貰うDPと配るDP、久々に書いたので、両方混ざって、間に合わないという大失態。
今だとアルゴ式（貰う DP と配る DP | アルゴ式）を参照した方がいい気もするが、
新鮮なうちに両方のPython解を書いて載せておきます。
※問題そのものの考察については、いろんな解説が充実しているので、省略で！
配るDP
def resolve(): H,W=map(int,input().split()) C=[] for i in range(H): C.append(input()) dp=[[-1000000]*(W) for i in range((H))] if C[0][0]==".": dp[0][0]=1 for h in range(0,H): for w in range(0,W): if h<H-1: if C[h+1][w]==".": dp[h+1][w]=max(dp[h][w]+1,dp[h+1][w]) if w<W-1: if C[h][w+1]==".": dp[h][w+1]=max(dp[h][w]+1,dp[h][w+1]) Max=0 for h in range(H): for w in range(W): Max=max(Max,dp[h][w]) print(max(0,Max)) resolve()
貰うDP
def resolve(): H,W=map(int,input().split()) C=[] for i in range(H): C.append(input()) dp=[[-1000000]*(W) for i in range((H))] if C[0][0]==".": dp[0][0]=1 for h in range(0,H): for w in range(0,W): if C[h][w]==".": if h>=1: dp[h][w]=max(dp[h-1][w]+1,dp[h][w]) if w>=1: dp[h][w]=max(dp[h][w-1]+1,dp[h][w]) Max=0 for h in range(H): for w in range(W): Max=max(Max,dp[h][w]) print(max(0,Max)) resolve()
競プロでの自己肯定感の保ち方
この記事は
競技プログラミングを始めたばかりの人に伝えたいこと 17日目の記事です。
- コツとかノウハウ的な話は、他の方が沢山されてるので…
- 競プロでハマりやすい（？）、モチベや自己肯定感的にキツいアレの対策について
はじめに
自分は競プロを始めたのが、業プロ歴7年目くらいの頃でした。
仕事は人並みに忙しい程度、小さい子供が2人。
元々は音ゲーを中心に、隙あらばゲームしてましたが、段々できなくなってきたな・・・
元々オフでのお勉強は、気持ち程度にしかできてなかったけど、それはもっとできなくなってきたな・・・
とか思ってた頃に、機会あって競プロを知りました。
成長速度は、決して早い方ではなかったし、モチベというか自己肯定感が保てない時期（平たく言うと凹む）も、正直ありました。
それを振り替えって「どういう考え方をすると折れずに済むか（マイペースに楽しめるか）」的な話です。
なぜ凹むのか
始めたばかりの方は「みんな当たり前のように解き過ぎだろ！」とか、
少し続けていると「みんな成長早すぎでは？」とか、色々思うことがあると思います。
何らかの開発経験で自信を持って参戦すると、余計思いやすいかもしれません。
競プロは相対評価の成績であるレートの存在感が大きく、性質上、みんなと自分を比べやすいため、
気を付けないと自分が劣っている部分が目立って、凹みに繋がるような気がしています。
更に、競プロは、参加者の属性も広く、熱意も素質も立場も、本当にバラバラです。
何が有利不利かは置いといても、比べても仕方ない全然違うタイプの人と、つい比べてしまうこともあるかも。
なぜ成長速度の差が生まれるのか
その要因を少し考えてみると、以下があるような気がします。異論あるかも。
- 解いた問題数（最も支配的？）
- 数学の得意不得意
- あてられる時間
- プログラム開発経験
- 地頭の良さ的なやつ
- 熱意やら目的意識
- 身近な同レベルの仲間の存在
この辺って、改善が（短期間には）難しいもの、が結構多いと思います。
ふと競プロを始めた瞬間においては、ある意味、「たまたま自分が持っていたかどうか」みたいな、ガチャ的な面もあると思います。
それゆえ、成長速度が全然人によって違って、緑になるのが1か月の人、半年の人、1年の人、2年以上の人・・・いろいろいます。
この辺は、速い遅いの結果だけを眺めていると、見落としがちだと思います（大概、知りようもない）
見方を変えてみる
ということで、競プロの性質上、成長が早い部類ではない人が、うっかり他人との比較をし過ぎると、簡単に凹めてしまいます。
しかし、ここで忘れがちな事実がありまして。
この「自分は弱い」凹みの文脈には「競プロにコンスタントに取り組んでいる人間の中では」が隠れています。
「競プロにコンスタントに取り組んでいる人間の中では」というのは世間の平均値なのでしょうか？たぶん否です。
競プロをやるとは、こういうことだと思いますが
- アルゴリズムの勉強・習得
- 数学の復習
- 言語仕様や計算量の追求
- 開発環境や効率化ツールの整備
- とにかく精進する
- 関連書籍を読む
- 何より週末夜に何時間もコンテストに張り付く
こういったことは世間のみんなが当たり前にやっているか？というと、そうでもないと思います。
母集団にもよりますが、情報系学生、ソフト系開発部門、においても、コンスタントにこういった、何らかの技術の習得のために、オフの時間をたくさん費やしている人間、というのは、結構限られると思います。
（「いや、最低ラインだろ」という大学も企業もあるとは思いますし、実際の比率は分かりません。ただ、そういった努力ができる人間は、実は世間では、そこまで多くないんじゃないかと感じてます。私見です。）
肯定的にとらえてみる
だとすると、まず、「競プロにコンスタントに取り組んでいる人間」でいるだけで、一つ頑張っている自分を褒めてもいい、と思います。
もちろん、競プロでない何かでもいいのですが、何もなく漫然と過ごしていた頃と比べると、何かに取り組んでいる現状は、既にえらいような気がします。
また、成長が遅いのが事実だとしても、それは「競プロの成長に有利な要因が、競プロ参加者の中では少ない方である」でしかなくて、何か自分の人間性や頭脳全般が劣っている、ような捉え方はしなくてもいいはずです。
いろいろな要因がある中で、レートに表れにくい中ででも、継続できていること自体がすごいともいえそうです。
それから、これは根拠のない私見ですが「教材や情報も充実していき、参加者全体が成長していく中で、少なからず全体レベルが上がっていき、同じパフォーマンス・レートが意味する絶対的な強さが変動していく」という背景もありそうです。
そうだとすると、平均的にはみんなが精進していて、「平均強さ」が上がっているかもしれません。自分の成長が人並みだとすると、レート上は「停滞」に見えるかもしれません。
そう考えると、停滞とか、緩やかに減少くらいだと、自分の絶対的な能力は、下がっているわけではないかもしれません。
結論
こんな感じで凹む材料以上に、「実は自分だって結構頑張ってない？えらくない？」と自分を肯定する材料もあるので、マズいと思ったら視点を変えて褒めてみましょう、というお話でした。
おまけ：音ゲーと絡めた方が分かり易かったかも
ここで、完全に私見ですが、競プロにおける実力の捉え方が、音ゲーと似ているな、と常々思うので、ちょっと紹介。
ビーマニには絶対的な実力指標として、「段位認定」があります。詳細は端折ります。
この段位の内訳について、集計されてる方の記事を引用します。
7級～十段～中伝～皆伝と20クラスほどあるわけですが、有段者の内訳でいうと、なんと九段以上が40％以上を占めます。七段以上というと、70％に近くなります。
実際、ふらっとゲーセンに行くと、見かける人の割合って、割とこの感覚に近いです。
なお、難易度で言うと、当然ですが、本当に初めての人は、多くの場合7級も無理ですし、ちょっとやってれば毎日昇級するほど簡単なゲームでもないです。
音ゲーに無縁の人からすると、初段あたりで、すでに「だいぶ常軌を逸脱した動き」になってるようにも思います。（凡人の感想です）
音ゲーと競プロは、精進が本質、実力の数値化、みたいな部分で、まあまあ近いところがあって、音ゲーマーが競プロはまりやすい傾向があるように思います（私見です）
ただ、大きく違うのは、「音ゲーは一部を除いて、実力指標は絶対評価」「競プロは一部を除いて、実力評価は相対評価」というところです。
音ゲーを無理やり相対評価にすると「上から30％付近の人が集まる十段＝緑レート」とかになるかもしれません。
十段は、例えばこういうのがそれなりに捌けるレベルであり、かなりの長期間、熱心に修行して到達できるものです（凡人の感想です）
※引用して問題なさそうな動画なだけであって、この方は十段どころかビーマニ界のtouristさん的な方です
何が言いたかったかというと
「みんなが精進している環境の中で、相対評価で出てくる成績というのは、めちゃくちゃ厳しく出ている可能性があり、低くてもガッカリしなくてよい。そもそも修行の世界に立ち続けているだけで結構すごい」
ということです。
未経験の人（だったあの頃の自分）から見て、それなりに出来ることが増えた感覚がありながら、（何となくほしいイメージのある数値や色に対して/周囲の人の成長速度に比べて）「自分が弱い」とえぐってしまうのは、よろしくないです。
ぜひ、レートだけではなく、絶対的な指標だったり、過去の自分との相対評価だったり、そういった視点からも自分の成長や実力を眺めるようにすると、自己肯定感を保ちやすくなると思います。
ひいては長く続ける趣味に、持ち込みやすくなると思います。よき修行の旅を。。。
ABC131 D - Megalomania / インデントに注意
まだ埋めてない茶diffを埋めようとしてて（AGCと古すぎるものは除外している…）、サクっと解いたつもりが、なぜかTLEが出てハマる。
以下なんだけど、パッと見て分かるだろうか？？
def resolve(): N=int(input()) L=[] for i in range(N): a,b=map(int,input().split()) L.append([a,b]) L.sort(key = lambda x:x[1]) Time=0 for i in range(N): Time+=L[i][0] if Time > L[i][1]: print("No") return print("Yes")
自分は、何度読んでも原因が分からず、どっかに極端に遅い書き方しちゃってる？とか疑って、入力や配列の触り方など、延々と変えては実験を繰り返してしまった。当然、どれだけ改善を重ねてもTLE。
・・・
答えは、sortのインデントがおかしいので、sortしまくってました。
分かっていれば当たり前のミスなんだけど、焦っていると全然気づかない。本番でもやらかしそうだ。
下手に改行を入れない？タブ２つにする？入力系ブロックが終わったら、もっと極端に改行する？
何か習慣にした方がいいかもしれない。。。
AHC003でPythonでビジュアライザ動かせなかった人へ
AHC003に参加し、272...点で、上1/3ちょいでした。
AHC001もAHC002も一応参加したけど、下1/4にも及ばなかったので、自分としては健闘したかなと思います。
さて、その結果とはあまり関係ないのですが。
公式で提供されているRustのビジュアライザで「Pythonの自分のプログラムをどう動かしていいかわからない」という人はいませんか？（自分だけ？）
- 私のレベル感
結論としては、以下の微妙～～～な方法で、最低限、ビジュアライザを動かせたのと、最低限、効率化できました。
- 諦めてpyinstallerでexe化する
- ビジュアライザでテストする
- ビジュアライザで画像作る
- その画像開く
- ここまでをバッチ化する
具体的にはこんな感じのバッチです。このバッチを、ビジュアライザと同階層に配置し、叩いてます。
pyinstaller C:\Users\xxx\Desktop\AtCoder\test.py --onefile cargo run --release --bin tester in\0000.txt C:\Users\xxx\Desktop\ahc003\dist\test.exe > out.txt cargo run --release --bin vis in\0000.txt out.txt start out.svg pause
※ビジュアライザのビルド、および、pyinstallerのインストールは、何も詰まるところがなかったので省略します。
ということで、ビジュアライザ自体を改造したり、もっと効率化的にぶん回したり、する人が多いのだと思いますが・・・
「動かすことすらままならねえ！」という方は、こんな感じで、とりあえず特定ケースで動かすだけでも、やってみてはいかがでしょうか（自分だけ？？？）
ABC197 C - ORXOR
誤読抜きにしても、BIT全探索の理解が甘く、まるで解けなかった・・・
だいぶ時間かかって、やっと分かり易いコードに落ちた気がするので、メモ。
なお、PyPyじゃないと通らない（500msくらい）
def resolve(): N=int(input()) A=list(map(int,input().split())) Min=10**100 n=N #値0,1,2,3に対して0,1,2の区切りを入れる全パターン列挙 #区間内が空は許されないので、区切りは0の後、1の後...と捉える pattern=[] for i in range(2 ** (n-1)): tmp = [False] * (n-1) for j in range(n-1): if i >> j & 1: tmp[j] = True pattern.append(tmp) #各パターンに対し計算する for ptn in pattern: ORs=[]#区切り内でORした値集 XOR=0 ORtemp=A[0] for i in range(n-1): if ptn[i]: ORs.append(ORtemp) ORtemp=A[i+1] else: ORtemp|=A[i+1] ORs.append(ORtemp) #区切ったOR集が完成するので、それぞれXOR for ors in ORs: XOR^=ors Min=min(Min,XOR) print(Min)
ARC115 C - ℕ Coloring
解説に反して、愚直みある実装でも解けた。
以下では1-indexedの方が理解しやすいと思ったので、あやしい+1と、出力時に0番目の無視をしている。
また、値はA1は必ず1、A2以降は必ず2以上、が明らかなので、答えの配列の初期値を1,2,2,...とすることで、最も計算回数の多い、i=1のパターンを無視した。
それ以降は、i=2,3,...それぞれにて、2なら4,6,... 、3なら6,9,...と、倍数に該当するものの値を、Aiの値と被らない＝現在値+1して、ただただ更新し続ける。
倍数が存在しえなくなるので、半分チョイまでのループとした。（深く考えてないが、切り上げならええやろ、、、程度。）
def resolve(): N=int(input())+1 ans=[2]*N ans[1]-=1 for i in range(2,math.ceil(N/2)): val=ans[i]+1 for j in range(2*i,N,i): ans[j]=val for i in range(1,N): print(ans[i],end=" ")
追記。
計算量危ないと思い込んで、↑ではアレコレやってみたものの、一切の高速化を廃しても、所要時間変わらず。
こういうのの計算量の見積もりがまだまだヘタだ…
def resolve(): N=int(input())+1 ans=[0]*N for i in range(1,N): val=ans[i]+1 for j in range(i,N,i): ans[j]=val for i in range(1,N): print(ans[i],end=" ")
