blog主に競プロ問題の解説を載せてますこの広告は、90日以上更新していないブログに表示しています。コンテスト最近プロコン界隈で話題のyukicoderがコンテストを開くとTwitterで知り、とくにすることもなかったので参戦してみました。これが初めてのyukicoderでした。計算量に苦しめられ、2度pythonコードをC++に書き直したりもしましたが、結果としては10問中6問(A,B,C,D,E,G)正解と、今の自分の実力を考えると満足のいく結果でした。問題セットのバランスがすごくよく、楽しいコンテストだったのでぜひ定期的にコンテストを開いてほしいですね。コンテスト結果と問題へのリンクページはこちら。本番に正解できた解答は続きから。次はどっちだ先手の名前と、オセロの盤面情報が与えられる。どちらもパスをしていないとして次の手番の人を答える問題。最初全然わからなくて結構焦った。石の総数(または空きの総数)に注目すれば答えられる。ドーナツどーんといこう!トーラスの内半径と外半径が与えらるので、その体積に係数をかけて答える問題。トーラスの体積ついてはWikipediaなどを参照のこと。品物の並び替え2以上9以下の品物と、その順番による得点リストが与えられる。得ることができることを意味している。品物を適当に並べたときの総得点の最大値を答える問題。単純に順列を作成すれば答えられるが、pythonだとぎりぎり間に合わなかった。pythonで通していた人はいたのでちょっと悔しい。赤、青、緑の石がいくつかずつ与えられる。魔法のネックレスは各石1つずつを消費して作られる。ある石2つで別の石1つに交換できるとしたとき、魔法のネックレスは最大いくつ作れるか答える問題。最初に3つのなかで最低個数の石の分だけ減じておけば、あとは2つの石の個数の場合分けをしながらで答えが求められる。逃走経路N個の街があり、そのなかのある街と街を結ぶ合計M本の道路がある。それぞれの道路には交通料がかかり、ある街と街を結ぶ道路は複数本ある場合がある。指名手配中の犯人の交通料支払い記録が時間順に与えられるので、犯人が潜伏している可能性のある街をすべて答える問題。ある街から支払い記録の逆順に交通料をたどれるかどうかを調べていけば答えが求められる。効率的なやり方ではないのでpythonだと制限時間ぎりぎりだった。圏外です(EASY)無線を持った二人が通信しようとしている。無線機はそのままでは半径1kmにある無線機としか通信できないが、中継機を経由することで、通信距離を伸ばすことができる。中継機は半径10kmにある中継機と通信することができる。無線機と中継機は1km以上離れると通信できない。機の中継機の座標が与えられるので、二人は直線距離で最大どれだけ離れて通信することができるかを答える問題。最大1000、EASYである。自分は次のように解答した。各中継機間の距離が10km以下かどうかを調べて、直接通信可能な中継機のグラフを作る。あとはワーシャル・フロイド法を用いて各中継器の距離を調べる。距離が有限だとそれらの中継器は通信可能である。最大値を答えれば正解となる。Nが最大1000で、ワーシャル・フロイド法はO(N3)なので、pythonだとまったく間に合わないと思う。読者になるリンクTopCoderCodeforcestwitterGitHubQiitaはてなブログをはじめよう!roiti46さんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。