読者です 読者をやめる 読者になる 読者になる

buyoh.hateblo.jp

競プロ参加記録.開設したばかりなので暫くお待ちください.

Python3の勉強をyukicoderでやる

pythonは正直あまり好きな言語ではなかったのですが,numpyが魅力的すぎるため,競技プログラミングで少し勉強してみました.

大学の講義内容がさっと手元で動かせないんですよね.octaveは重すぎるし.

記事を書いている人の前提知識度

昔に少しだけ書いたことがあります.簡単なゲームを作りました.

notepad.exe [WP]no.014 python独習

『なんかブロックをインデントで判定してる』『タプルとかリストとかの概念がある』という雰囲気は覚えてますが, 実用面は全く忘れました.

solve

No.268 ラッピング(Easy) - yukicoder

  • http://yukicoder.me/submissions/174424
  • 昇順,降順ソートしたい問題.
  • Python2とPython3でかなり違うらしい.input()ですら違いがある.
  • aa.sort()でリストをソートできる.reverse=Trueと指定すれば逆順になる.
    • 辞書っぽい引数の指定面白い
    • 破壊的.破壊出来ないリスト(例:10行目)に対してソートしたい場合,sorted(arr)をやる.
  • range(N)は,Rubyでいう(0...N)みたいなもの
  • print aという記法はPython3では使えない.

No.136 Yet Another GCD Problem - yukicoder

  • http://yukicoder.me/submissions/174503
  • Kは2に固定して良い.あとは全ての組み合わせを全探索する.
  • PyPy3がRuntimeError.math.gcdを使うにはバージョンが足りないらしい.
    • Python3は通った.
    • import mathすると使える.
  • 割り算をすると,例え整数同士でもFloat型になる.
    • int(nm)でキャストできる.
  • maxは普通に関数として使える.Rubyみたいなインスタンスメソッドではない.

No.80 四角形を描こう - yukicoder

  • http://yukicoder.me/submissions/174509
  • 思考停止全探索.xとyを適当に全部回す.
  • if x*2+y*2>l : continueみたいな書き方ができる.HSP*1っぽい.
  • 提出コードからは消したけれども,プログラムを中断させたいときは,import sysしたうえでsys.exit()する.
    • うっかりsys.exitと書くと終了しない.

No.204 ゴールデン・ウィーク(2) - yukicoder

  • http://yukicoder.me/submissions/174566
    • 途中で実装方針を変えたため無駄な記述がある.
  • D日すべて使う必要があるかどうかが問題文・テストケースから分からない・・・と思ってたら『最大』って書いてあった.
    • test13.txtを見れば分かるように,D日すべて使う必要は無い.
  • 有給休暇を挿入する始点xを全探索する.
  • input()は改行文字を含まない.
  • ++var+ + varとして解釈される.もちろんvar++はエラー.
  • strのi番目の文字はstr[i]として取り出せるが,書き換えは出来ない.
    • 文字列の部分書き換えをするには,str[:i]+'o'+str[i+1:]と書く必要がある.
  • Ruby同様,文字列の掛け算ができる.
  • 文字列の範囲に-1を指定すると,末尾を指定したことになる.Rubyと同じ.

No.77 レンガのピラミッド - yukicoder

  • http://yukicoder.me/submissions/174570
  • 理想のピラミッド△を作っておいて,差分を求めることでコストを得ることができる.あとは全探索.
    • 予めブロックが足りるかどうか判定したうえで,『ブロックを除去する』を1コスト,『ブロックを積む』を0コストとして計算.
  • sample5.txtのように,フィールドは無限大に広いものとして考える必要がある.しかし,制約から199で抑えて良い.
    • 提出コードではaa+=[0]*100という感じで無理やり増やしてる.
  • sum(aa)で総和が取れる.
  • 0Falseとして解釈される.

No.290 1010 - yukicoder

  • http://yukicoder.me/submissions/174571
  • http://yukicoder.me/submissions/174573
  • 00,11,0101,1010が存在するかどうか調べる.
  • 存在するかどうか調べるために,正規表現を使う.
    • import reをしておく.正規表現リテラルなんてものは無い.
    • r'str'と書くと,\エスケープしなくなる.
    • re.match(r,s)を使うと,先頭からのマッチしか判定しない..*を加えるか,re.search(r,s)を使う.
      • re.search(r,s)なら場所が分かる.ただし,先頭マッチ時は0が返ってFalse扱いになるので,Noneと比較する.

*1:HotSoupProcessor

4ACした(21ACする:その2)

次の未だ解いていない問題をターゲットに13AC(21-8)する.

  • yukicoder☆2(コンテスト中を除く)
  • yukicoder☆3,4
  • AtCoder ARC C(コンテスト中に解けなかったものだけカウント)
  • AtCoder ARC D,E,F
  • AtCoder AGC B,C,D
  • codeforces 不問(A問題でもカウント.英語補正)
  • codeIQ ☆3以上

問題名はリンクになっており,クリックすると問題ページに飛べます.

No.41 貯金箱の溜息(EASY) - yukicoder

  • http://yukicoder.me/submissions/174158
  • 1円以外の通貨は111111の倍数なので,111111で割っても同じ問題で考えることができる.
  • 割った後の値は105ぐらいまで落ちるので,普通の動的計画法が使える.
  • …はずだが,その部分がうまくできず,解説見た.
    • (111円を1個,222円を1個,111円を1個.という数え上げも含めてしまう…で悩んでた)

Problem - C - Codeforces

No.102 トランプを奪え - yukicoder

  • http://yukicoder.me/submissions/174234
  • nim
  • 愚直に出来ず工夫がいる.カードの枚数を4で割った余りとしても良いことに気づく必要がある.
    • 弱体化デバフを掛けてメモ化再帰して解く問題は少なくないっぽい

C: Chocolate Bar - AtCoder Regular Contest 074 | AtCoder (ノーカウント)

F: Lotus Leaves - AtCoder Regular Contest 074 | AtCoder

  • http://arc074.contest.atcoder.jp/submissions/1299054
  • 最大流問題.初めてF解いた.
  • 解説と若干異なって見えたので,詳しく書く.
  • 『今乗っている葉と同じ行または同じ列に浮かんでいる葉へジャンプする』を『今乗っている葉と同じ行,列に移動できる廊下がある』と読み替えたい.
  • Mを足場の数とする.頂点数2HW+H+W,辺の数5M
  • 全てのセルのそれぞれ(y,x)に2つの頂点U_{(y,x)}V_{(y,x)}を割り当てる.
  • 各行に頂点R_{y},列に頂点C_{x}を割り当てる.
  • もしtex:(y,x)]に足場があるなら,
    • U_{(y,x)}からV_{(y,x)}へ流量1の辺をつなぐ.
    • V_{(y,x)}からR_{y}V_{(y,x)}からC_{y}へ流量infの辺をつなぐ.
    • R_{y}からU_{(y,x)}C_{y}からU_{(y,x)}へ流量infの辺をつなぐ.
  • V_{S}からU_{T}への最大流量を解く.

8ACしました(21ACする:その1)

次の未だ解いていない問題をターゲットに21ACする.

  • yukicoder☆2(コンテスト中を除く)
  • yukicoder☆3,4
  • AtCoder ARC C(コンテスト中を除く)
  • AtCoder ARC D,E
  • AtCoder AGC B,C,D
  • codeforces 不問(A問題でもカウント.英語補正)
  • codeIQ ☆3以上

問題名はリンクになっており,クリックすると問題ページに飛べます.

No.111 あばばばば - yukicoder

No.254 文字列の構成 - yukicoder

  • http://yukicoder.me/submissions/173772
  • abababacdcdcdefefefefexyzみたいな感じの文字列を作りたい.
  • abababaの回文の出現回数はno111で作った関数を基に簡単に作れる(一致しない).
  • 二分探索を使って,どこまで減らせるかを求めて,求めた度にアウトプットする.
  • 適当に書いても文字は足りるらしい.
  • クソみたいなWAした

Problem - A - Codeforces

Problem - B - Codeforces

No.324 落ちてた閉路グラフ - yukicoder

No.2 素因数ゲーム - yukicoder

No.17 2つの地点に泊まりたい - yukicoder

No.59 鉄道の旅 - yukicoder

  • http://yukicoder.me/submissions/174015
  • RMQを使う.
  • Wの範囲が広いので,セグメントツリーを使うとMLE,TLEする可能性がある.
  • 座標圧縮して,Wの範囲を縮めておくと,Nぐらいで抑えられるので,セグメントツリーが使える.

yukicoder No.7 プライムナンバーゲーム / No.11 カードマッチ / No.43 野球の試合

☆2でも引っかかるところがあるのでメモ記事.

続きを読む

yukicoder No.476 No.477 No.478 No.479

No.476 No.478 No.479のwriter,No.477のtesterをしました.

人との繋がりがないのでtester集まりませんでした

yukicoder contest 155 - yukicoder

解説はyukicoderの方を参照してください.本記事では問題に絡むネタを紹介します.

もちろん,ネタバレを含みます.

続きを読む

No.459 C-VS for yukicoder

Advent Calendar Contest 2016の10日目の問題のwriterをしました.

No.459 C-VS for yukicoder - yukicoder

問題文・想定解法はリンク先の通りです.

本記事ではフローを用いた別解について書きます.結局年明けになってしまった.

続きを読む

yukicoder ☆1埋め

8つほど埋めていなかったので,今日埋めました.

ほぼ全部rubyで埋めました.inject最強.

☆1なのでやるだけ,といったところでしょうか.

No.296に関して,Ruby関連で気になった所があるので,別ブログに記事書きます