masuTomo’s blog

競技プログラミングの勉強メモです.主にPythonを使用します.数学の記事も書くかもしれません.

【誰得】Google Forms からGoogle Documentを生成

はじめに

暇つぶしにGoogleAppsScriptでいろいろ調べて遊んでいます.そこで作ってみたスクリプトを公開したいと思います.

作ったもの

  • Google Formsで作成したアンケート等をGoogle Document形式に変換します.

    機能詳細

  • GoogleFormsのタイトル,質問,選択肢,セクションを取得して,それらしいGoogleDocumentを生成する.

使いどころ

  • GoogleFormsでアンケートを作成したが,社内が未だに書面による決済のため,作成したGoogleFormsを印刷したい.(Formsでも印刷できるが,編集ができない)
  • GoogleFormsでアンケートを実施したいが,スマホ等を所持していない可能性も考慮して,紙面でのアンケートも準備したい.
  • GoogleFormsで印刷したら選択肢のプルダウンが多すぎて見るに堪えないので,プルダウンの選択肢は削除して印刷したい(どれだけニッチな場面なのか)

注意点

作成したFormsに編集権限がないと使えません.

使い方

  • 自分のGoogleDriveのフォルダ内でGoogle Apps Scriptを新規作成して,以下のスクリプトをコピペ(Google Apps Scriptの配布の仕方がわかりませんでした).

  • スクリプト内の保存先フォルダーのIDを書き換える

生成したDocumentを保存したいフォルダをマイドライブ内のどこかに作成し,そこのフォルダに移動する.アドレスバーの以下の画像のようにアドレスの末尾がフォルダーIDなので,それをコピーして貼り付けてください.f:id:masuTomo:20210226232144p:plain

  • 読み込むフォームのIDを書き換える

読み込みたいフォームを開いて,フォルダーIDと同じような文字列がアドレスのところに表示されているので,それをコピーして貼り付け.

  • 関数がmainになっていることを確認して実行 f:id:masuTomo:20210226230618p:plain

スクリプト

//保存先フォルダーのID
const saveFolderId = 'ここに保存先フォルダーのID';
//読み込むフォームのID
const formId = 'ここに読み込みたいフォームのID';

//各質問の先頭に付与するためのNumber
var qNo = 1;

//ファイルの保存
function saveDoc(doc,titleText){
  var file = DriveApp.getFileById(doc.getId());
  // 出力フォルダ
  var OutputFolder = DriveApp.getFolderById(saveFolderId);  
  file.moveTo(OutputFolder);
}

//Docの最上部に表示する文字列を設定
//見出し,センタリング
function setDocTitle(body, str){
  var par = body.appendParagraph(str);
  par.setHeading(DocumentApp.ParagraphHeading.HEADING1);
  par.setAlignment(DocumentApp.HorizontalAlignment.CENTER);
  return body;
}

//追加されたセクションの処理
function setSectionTitle(body,str){
    var par = body.appendParagraph(str);
  par.setHeading(DocumentApp.ParagraphHeading.HEADING2);
  par.setAlignment(DocumentApp.HorizontalAlignment.CENTER);
  return body;
}

function setContents(body, item){
  const indent = '    ';
  var type = item.getType();
  switch(type){

    //チェックボックスの処理
    case FormApp.ItemType.CHECKBOX:
      var res = String(qNo) + '.' + item.getTitle() +'\n\n';
      qNo++;
      console.log('CHCECKBOX開始-' + item.getTitle());
      var choices = item.asCheckboxItem().getChoices();
      for( var i = 0; i < choices.length; i++)  {
        res += indent + '□'+choices[i].getValue() + '\n';
      }
      res += '\n';
      body.appendParagraph(res);
      console.log('CHCECKBOX終了');
    break;

    //複数選択方式のグリッドの処理
    case FormApp.ItemType.CHECKBOX_GRID:
      console.log('CHCECKBOX_GRID開始-'+item.getTitle());
      var res = String(qNo) + '.' + item.getTitle() +'\n\n';
      qNo++;
      body.appendParagraph(res)
      var cols = item.asCheckboxGridItem().getColumns();
      var rows = item.asCheckboxGridItem().getRows();
      var cells = Array(rows.length+1);
      cols = [''].concat(cols);
      cells[0] = cols;
      for( var i = 1; i < rows.length+1; i++){
        cells[i] = Array(rows[i-1]).concat(Array(cols.length-1).fill('□'));
      }
      body.appendTable(cells);
      console.log('CHCECKBOX_GRID終了');
    break;

    //日付型の処理
    case FormApp.ItemType.DATE:
      var res = String(qNo) + '.' + item.getTitle() + '\n';
      qNo++;
      console.log('DATE開始-' + item.getTitle());
      console.log('DATE終了');
    break;

    case FormApp.ItemType.DATETIME:
      var res = String(qNo) + '.' + item.getTitle() + '\n';
      qNo++;
      console.log('DATETIME開始-' + item.getTitle());
      console.log('DATETIME終了');
    break;

    case FormApp.ItemType.DURATION:
      console.log('DURATION開始-' + item.getTitle());
      console.log('DURATION終了');
    break;

    //単一選択形式のグリッドの処理
    case FormApp.ItemType.GRID:
      console.log('GRID開始-'+item.getTitle());
      var res = String(qNo) + '.' + item.getTitle() +'\n\n';
      qNo++;
      body.appendParagraph(res)
      var cols = item.asGridItem().getColumns();
      var rows = item.asGridItem().getRows();
      var cells = Array(rows.length+1);
      cols = [''].concat(cols);
      cells[0] = cols;
      for( var i = 1; i < rows.length+1; i++){
        cells[i] = Array(rows[i-1]).concat(Array(cols.length-1).fill('〇'));
      }
      body.appendTable(cells);
      console.log('GRID終了');

    break;
    case FormApp.ItemType.IMAGE:
      console.log('IMAGE開始-' + item.getTitle());
      console.log('IMAGE終了');
    break;

    //プルダウンの処理
    case FormApp.ItemType.LIST:
      var res = String(qNo) + '.' + item.getTitle() + '\n\n';
      qNo++;
      console.log('LIST開始-' + res);
      var choices = item.asListItem().getChoices();
      for( var i = 0; i < choices.length; i++)  {
        res += indent + '・'+choices[i].getValue() + '\n';
      }
      res += '\n';
      body.appendParagraph(res);
      console.log('LIST終了');

    break;

    //ラジオボタンの処理
    case FormApp.ItemType.MULTIPLE_CHOICE:
      var res = String(qNo) + '.' + item.getTitle() + '\n\n';
      qNo++;
      console.log('MULTIPLE_CHOICE開始-' + res);
      var choices = item.asMultipleChoiceItem().getChoices();
      for( var i = 0; i < choices.length; i++)  {
        res += indent + '・'+choices[i].getValue() + '\n';
      }
      res += '\n';
      body.appendParagraph(res);
      console.log('MULTIPLE_CHOICE終了');
    break;

    //段落型の処理
    case FormApp.ItemType.PARAGRAPH_TEXT:
      var res = String(qNo) + '.' + item.getTitle() + '\n\n';
      qNo++;
      console.log('PARAGRAPH_TEXT開始-' + item.getTitle());
      res += '(自由記述)';
      res += '\n';
      body.appendParagraph(res);
      console.log('PARAGRAPH_TEXT終了');
    break;

    //均等目盛型の処理
    case FormApp.ItemType.SCALE:
      var res = String(qNo) + '.' + item.getTitle() + '\n\n';
      qNo++;
      console.log('SCALE開始-' + res);
      var llabel = item.asScaleItem().getLeftLabel();
      var rlabel = item.asScaleItem().getRightLabel();
      var lbound = item.asScaleItem().getLowerBound();
      var rbound = item.asScaleItem().getUpperBound();
      var line = '';
      for(var i = 0; i < rbound-lbound; i++){
        line += '----' + String(lbound + i + 1);
      }
      res += indent + llabel + ' | ' + String(lbound) + line + ' | ' + rlabel + '\n';
      body.appendParagraph(res);
      console.log('SCALE終了');
    break;

    case FormApp.ItemType.SECTION_HEADER:
      console.log('SECTION_HEADER開始-' + item.getTitle());
      console.log('SECTION_HEADER終了');
    break;

    //記述式の処理
    case FormApp.ItemType.TEXT:
      var res = String(qNo) + '.' + item.getTitle() + '\n\n';
      qNo++;
      console.log('TEXT開始-' + item.getTitle());
      res += '(自由記述)';
      res += '\n';
      body.appendParagraph(res);
      console.log('TEXT終了');
    break;

    //時刻の処理
    case FormApp.ItemType.TIME:
      console.log('TIME開始-' + item.getTitle());
      console.log('TIME終了');    
    break;

    case FormApp.ItemType.VIDEO:
      console.log('VIDEO開始-' + item.getTitle());
      console.log('VIDEO終了');
    break;

    //追加されたセクションの処理
    case FormApp.ItemType.PAGE_BREAK:
      body = setSectionTitle(body,item.getTitle() + '\n');
      console.log('PAGE_BREAK開始-' + item.getTitle());
      console.log('PAGE_BREAK終了');
    break;

  }
}

function main() {
  //読み込み先のFormsを指定
  var f = FormApp.openById(formId);
  //フォームの上部にある説明文
  var des = f.getDescription();
  var formTitle = f.getTitle();
  //フォームと同じタイトルでGoogle Docsを作成する
  var date = new Date();
  const doc = DocumentApp.create(formTitle + '_'+Utilities.formatDate(new Date(), 'JST', 'yyyyMMdd'));
  var body = doc.getBody();
  body = setDocTitle(body,formTitle + '\n');
  body.appendParagraph(des + '\n\n\n');

  //質問項目を取得
  var itemList = f.getItems();
  for(let i = 0; i < itemList.length; i++) {
    setContents(body,itemList[i]);    
  }
  saveDoc(doc,formTitle);
}

注意点

  • フォーム内の画像は取り込めません
  • 回答によるセクション移動には対応していません
  • テスト機能は反映しません
  • 必須回答は反映しません(これはそのうち対応するかも)
  • 入力チェックも反映しません
  • バグがあると思います.お気づきのことがあればお知らせいただけるとありがたいです.
  • その他,私が思い至らず考慮漏れしれいる事項があると思います.

参考

ここに全部書いてある. developers.google.com

ABC162 解説(D)

ABC162 D - RGB Triplets

(ABC162 D - RGB Triplets) https://atcoder.jp/contests/abc162/tasks/abc162_d

TLEした解法

とりあえず何も気にせずに3重ループを書いて提出した.

N = int(input())
S = input()

ans = 0
for i in range(N):
    for j in range(i,N):
        for k in range(j,N):
            if j -i == k-j : continue
            if S[i] != S[j] and S[j] != S[k] and S[k] != S[i]: ans += 1
print(ans)

結果:7TLE

制約はN<=4000なので,まぁそれはそうかと思っていましたが一応提出しました.

やり直し

3重ループをなんとかして2重ループにすれば通るだろうなと考えたので,その方法を考察します.

なんとなく頭の片隅にあったのは蟻本のp.8「あみだくじ」やp.25「ハードルがあがった『くじびき』」でした.これは最初4重ループで記載していたコードを3重ループに減らすというものです.

おおよそのところを説明すると,整数Kが与えられたときに a+b+c+d = Kとなるa,b,c,dの組み合わせを求めよという問に対し,最初の4重ループはa,b,c,dをそれぞれforでまわして解を得るものでした.

でも,最後のdについてはKが決まっているのだから,a,b,cが決まった段階でdをループさせる必要はなくなるので3重ループに落とせるという考え方です.

これを真似します. 今の問題では左から順に調べていき,R,Gが使わていれば最後に探す文字はBになります.そこでGを使用した場所よりも右にあるBの個数がわかればそれで(i,j,k)の個数が確定します.

そのために,左からi番目までにR,G,Bの出現した個数を累積和としてあらかじめ計算しておくことにしました. あとはR,Gについて,2重ループをして,最後のBについては累積和から個数を求めました. コードが冗長になりましたが,ACしたものはこちら(PyPyで提出)

N = int(input())
S = input()
#i番目までに何個のR,G,Bが出てくるか
countR = [0 for _ in range(N)]
countG = [0 for _ in range(N)]
countB = [0 for _ in range(N)]

for i in range(N):
    if S[i] == 'R':
        countR[i] = 1
    if S[i] == 'G':
        countG[i] = 1
    if S[i] == 'B':
        countB[i] = 1
for i in range(N-1):
    countR[i+1] += countR[i]
    countG[i+1] += countG[i]
    countB[i+1] += countB[i]

ans = 0
#フラグ
R = False
G = False
B = False
for i in range(N):
    if S[i] == 'R':
        R = True
    if S[i] == 'G':
        G = True
    if S[i] == 'B':
        B = True
    for j in range(i,N):
        if S[i] == S[j]: continue

        if S[j] == 'R':
            if G:
                ans += countB[N-1] - countB[j]
                if 2*j-i < N and S[2*j-i] == 'B':ans -=1
            if B:
                ans += countG[N-1] - countG[j]
                if 2*j-i < N and S[2*j-i] == 'G':ans -=1

        if S[j] == 'G':
            if R:
                ans += countB[N-1] - countB[j]
                if 2*j-i < N and S[2*j-i] == 'B':ans -=1
            if B:
                ans += countR[N-1] - countR[j]
                if 2*j-i < N and S[2*j-i] == 'R':ans -=1

        if S[j] == 'B':
            if R:
                ans += countG[N-1] - countG[j]
                if 2*j-i < N and S[2*j-i] == 'G':ans -=1    
            if G:
                ans += countR[N-1] - countR[j]
                if 2*j-i < N and S[2*j-i] == 'R':ans -=1
    R = False
    G = False
    B = False
print(ans)

ARC013 B - 引越しできるかな? 解説

はじめに

書くつもりはなかったが,公式解説がないようなのでメモ程度に書いてみることにした.

問題

ARC013 B - 引越しできるかな?

解法

各荷物の3辺において必ず

1番長い辺 2番目に長い辺 3番目に長い辺

が存在する(同じ長さがあれば,それらの順位付けは勝手に決めてよい).

荷物 iについて

 l_{i} : 1番長い辺

 m_{i} :2番目に長い辺

 n_{i} :3番目に長い辺

として, [ tex: l_ {i} , m_ {i} , n_ {i} ]の最大値をそれぞれ求めて,それらを3辺の長さとする箱が必要である. (数式表示がうまくいきません,ごめんなさい)

実装

C = int(input())
l_max = 0
m_max = 0
n_max = 0
for _ in range(C):
    size = list(map(int,input().split()))
    size.sort()
    l_max = max(size[0],l_max)
    m_max = max(size[1],m_max)
    n_max = max(size[2],n_max)

print(l_max*m_max*n_max)

ABC129 C - Typical Stairs 解説

はじめに

Pythonで実装しました.そんなところで差が出るなんて,,,という学びがあったので記事にします.

問題

ABC123 C - Typical Stairs

考え方

いわゆるDPの基本的な問題なのだとおもいます.フィボナッチ数列と同じです.

1歩または2歩進めるとうことは,N段目に到達する方法はN-1段目から来る,またはN-2段目から来るの2通りです.したがってdp[N]をN段目に到達する方法とすれば,

dp[N] = dp[N-1] + dp[N-2]

と表すことができ,これはフィボナッチ数列の一般項と同じです.ここに壊れている床は使えないという条件を加えてやればACとなります.

TLEした実装

mod = 1e+9+7
 
# 入力の受け取り
N, M = map(int,input().split())
#壊れて使えない床をリストAに格納
A = [int(input()) for _ in range(M)]
 
dp = [0 for _ in range(N+1)]
dp[0] = 1
dp[1] = 1 if 1 not in A else 0
#DP遷移を計算
for i in range(2,N+1):
 #i段目が使えない床の場合はdp[i]=0とする
    if i in A:
        dp[i] = 0
    else:
        dp[i] = (dp[i-1] + dp[i-2])%mod
    
print(int(dp[N]))

ACした実装

mod = 1e+9+7

N, M = map(int,input().split())

#壊れた床の格納方法を変更
#床iが使えるときはA[i]=True
#床iが使えないときはA[i]=False
A = [ True for _ in range(N+1)]
for i in range(M):
    A[int(input())] = False

dp = [0 for _ in range(N+1)]
dp[0] = 1
dp[1] = 1 if A[1] == True else 0
for i in range(2,N+1):
    #dpを計算するときのifの条件式もAに合わせて変更
    if A[i]: dp[i] = (dp[i-1] + dp[i-2])%mod
   
print(int(dp[N]))

これでTLEが解消されてACとなりました.

大学入試

1歩で1段または2段のいずれかで階段を昇るとき,1歩で2段昇ることは連続しないものとする.15段の階段を昇る昇り方は何通りあるか.(07 京都大 文 )

競プロが大学入試にも役立つ好例ですね!!中高生も胸をはって競プロにいそしみましょう!

ABC186 解説(A~C)

A - Brick

A - Brick

N=12w = 5のときは,2個の荷物を載せることができる(3個目を載せると15キログラムとなりオーバーする). これを素直に式に表すと 12÷5 = 2\cdots 3となる(\cdotsは余りを表す).

従って,この計算の商の部分が答えになる.pythonでは切り捨て処理は//で記述できる.

N, W = map(int,input().split())
print(N//W)

B - Blocks on Grid

B - Blocks on Grid

ブロックを取り除くことしかできないので,すべてのマスの中でブロック数が一番少ないマスのブロック数に他のマスのブロック数を合わせるしかない.

おおむね次のような処理とした.

  • 入力の1行ごとに,その行の最小値を保存するようにして,すべての入力が終わったあとで,それらの中から全体の最小値を取得
  • H\times W個の要素を走査し,その中で先の最小値との差を合計していく
H, W = map(int,input().split())
A = []
mins = []
for i in range(H):
  a = list(map(int,input().split()))
  A.append(a)
  mins.append(min(a))
ans = 0
m = min(mins)
for i in range(H):
  for j in range(W):
    ans += A[i][j] - m

print(ans)

C - Unlucky 7

少し難しかった.

  • 各桁に7が出てくるかどうかのチェックが必要であり,それは整数型のままではできないので,文字列に変換して文字列の7を含むかどうかを判定する.

  • 10進数については,ただ文字列に変換して上記の処理を行えばよい

  • 8進数については,10進数を8進数に変換する処理が必要になる.

8進数への変換

実は,pythonには関数が用意されている(https://docs.python.org/ja/3/library/functions.html#oct). ただ,ここでは向学のため8進数への変換も実装することとする.

進数について

カンジをつかむ

そもそも10進数とはどのような数の表し方かを確認する.例えば2345(二千三百四十五)は  2345 = 2000 + 300 + 40 + 5 = 2 \times 10^{3} + 3 \times 10^{2} + 4 \times 10^{1} + 5 \times 10^{0} と書き直すことができる. この各位の数2,3,4,5以外の部分に注目して10^{x}という形になっている.この部分が10なので10進法と呼んでいる.

では,8進数で3456_8と表されているという数は(10進数では)どのような数になるかというと,それは 345_8 = 3\times 8^{3} + 4\times 8^{2} + 5\times 8^{1} + 6 \times 8^{0}となる.ちなみにこれを計算すると1880である(もちろんこれは10進数).※3456_8の右下の小さい8は,8進数で表していることを明示するためにつけている)

8進数を10進数に変換する

これで,8進数,10進数のカンジはつかめたのではないかと思うので,次は10進数で表された数を8進数に変換することを考える. 先の2345 _{10}を8進数に変換することを考える.8進数での表記は8^{x}というかたまりを作れば良い.下の桁から順番に調べよう.一番下の桁はk\times 8^{0}となっており,k1~7のいずれかである(もしk=8なら,繰り上がって,8^{1}の桁の方に出てくることになる).

したがって一番下の桁は,元の数字を8で割った余りを取ればよい. 2345÷8 = 293\cdots 1となり,最下位桁は1とわかる.

次に下から2番目の桁を求める.今,最下位桁は「●●▲◆」の◆の部分を8で割った余りとして求めたので,次の桁は一番下の◆を切り落とした「●●▲」に対して8 で割った余りを求めればよい.この一番下の◆を切り落とす方法を考える.

実は簡単である.10進法で考えると,1234123にするには,10で割って小数点以下を切り落とせばよい.ここで10で割ることで一番下の桁が落ちるのは10進数だからである.

したがって今は8進法で考えているので8で割って小数点以下を切り捨てれば目的のものが得られ,それを8で割った余りを求めればよい.

2345÷8=293.125なので293とし,さらに293÷8=36\cdots 5となり下から2番目の桁は5だとわかる.

あとはこれを繰り返せばよい.計算式のみ記す.

293÷8 = 36.625となり36÷8 = 4\cdots4

36÷8 = 4.5となり4÷8 = 0\cdots4

4÷8 = 0となり0÷8 = 0\cdots0となりここで終わり.

したがって,2345_{10} = 4451_8であることがわかった.これを実装すると次のようになる.

def to_oct(n):
  s = ''
  while(n):
    s = str(n%8) + s
    n //= 8
  return s

ans = 0
N = int(input())
for i in range(1,N+1):
  if '7' not in str(i)  and '7' not in to_oct(i):
    ans += 1
print(ans)

ABC187 解説(D - Choose Me)

D - Choose Me

D - Choose Me

  • 貪欲法を用いる

何もしなければ,青木君はA_iすべての票を,高橋君は0票となる.もし,町iで高橋君が演説をすれば,青木君の票がA_i票減り,高橋君の票がB_i票増える.注意点は「 青木君の総得票数」<「高橋君の総得票数」となるときの演説回数なので,高橋君が得票すること以外にも青木君の票を減らすことも重要である.

どの町で演説するのがよいか

ある町の青木派が a人,高橋派が b人いたとする.この町で演説する場合としない場合の青木君と高橋君の得票数の差を調べる.

演説なし 演説あり
青木君 a  0
高橋君 0 a+b

となることから,演説ありと,演説なしのときの得票数の差の差 (a+b) - 0 )- (0-a) = 2a+bである.つまり,この町で演説した場合2a+b票だけ青木君の得票数と,高橋君の得票数の差が縮まることがわかる.したがって,この値が大きい町から順番に演説をすればよい.したがって,次のような実装になる.

N = int(input())
AB = []
for i in range(N):
  a,b = map(int,input().split())
  AB.append([2*a+b,a,b])

AB.sort(reverse = True)
sumA = 0
sumB = 0
for x in AB:
  sumA += x[1]

ans = 0
if sumA < sumB:
  print(ans)
  exit()
for i in range(N):
  sumA -= AB[i][1]
  sumB += AB[i][1] + AB[i][2]
  ans += 1
  if sumA < sumB:
    print(ans)
    exit()

ABC187 解説(A~C)

はじめに

Twitterを見ていると,意外と競技プログラミングに出てくる高校数学に慣れ親しんでいない人が多いという話だったので,簡単な問題でも解説記事は需要があるかもしれないと思ったので,解説記事を書くことにしました.また,最近ABCにはあまり参加できていなかったのですが公式Editorialはテキストベースから動画ベースに変わったのでしょうか?動画を見るのがめんどくさい,移動中なのでテキストが良いという人もいそうなのでそういう意味でも解説記事は価値がある(と思いたい).なお,Pythonでの解説とする.

A - Large Digits

A - Large Digits - 3桁の文字列を1桁ずつに分割する - 文字列をint型に変換する という2つのことができればOK

A, B = input().split()

if int(A[0]) + int(A[1]) + int(A[2]) < int(B[0]) + int(B[1]) + int(B[2]):
  print(int(B[0]) + int(B[1]) + int(B[2]))
else:
  print(int(A[0]) + int(A[1]) + int(A[2]))

Pythonでは文字列はリストのようにindex(何文字目か)を指定してその文字を取り出すことができます.さらにそれをintで囲んで整数型に変換して和を求めればOKです.
別解

sumA = sum(int(i) for i in A)

のようにしていっぺんに整数に変換することもできます.

A, B = input().split()
sumA = sum(int(i) for i in A)
sumB = sum(int(i) for i in B)
if sumA < sumB:
  print(sumB)
else:
print(sumB)

B - Gentle Pairs

B - Gentle Pairs - 2点の座標から直線の傾きを求める ことができればOKです.ここで,その方法を復習します.

そもそも,( xy平面上の)直線は y = ax + bという形で表すことができます(実はこの形ではx=kというようなy軸に平行な直線を表すことができない.しかし,このようなことが起こるのは2点のx座標が一致するときであり,今の問題では条件からこのような状況は除外されている).このaを傾き,bを(y)切片といいます.今の問題では切片は関係ないのでaについてだけ考えます.

傾きaの求め方

公式的に書けば,直線の傾きはyの増加量/xの増加量」となります.

f:id:masuTomo:20210105212407p:plain
つまり,2点のx座標の差とy座標の差を計算すればよい.
   したがって,2点の座標をそれぞれ(x_1,y_1),(x_2,y_2)とすると,傾きを\frac{y_2-y_1}{x_2-x_1}として求めることができる.したがって,問題文に書かれている条件は -1 \leq \dfrac{y2-y1}{x2-x1} \leq 1ということになる.しかし,これをそのまま実装してしまうとWAとなってしまう.テストケースがわからないので想像だが,傾きを求めるときの除算の処理で誤差が発生したものによると考えられる.

除算での誤差への対処

では,どうすればよいかと言えば条件の不等式-1 \leq \frac{y_2-y_1}{x_2-x_1} \leq 1の分母を払ってしまえばよい.つまり不等式全体にx_2-x_1を掛けるのである.ただし,ここでも注意が必要で,それは不等式に掛け算をするときは掛ける値がマイナス(負)の場合は不等号の向きが反対になってしまうのである.しかも,今のままではx_1x_2のどちらが大きいかわからないので,x_2-x_1が正なのか負なのかが確定しない(iによって異なる).そこで,傾きを計算する前にx_1x_2の大小をチェックして,次のようにしてx_1の方を小さくなるようにしておけばよい(あるいは絶対値を用いても良い).

if x1 > x2: x1, x2 = x2, x1

こうしておくことで,分母を払うときに不等号の向きを変えなくて済むようになる.

以上のことを考慮して実装すると次のようになる.

N = int(input())
XY = []
for i in range(N):
  x, y = map(int,input().split())
  XY.append([x,y])

ans = 0
for i in range(N-1):
  for j in range(i+1,N):
    x1, y1 = XY[i][0], XY[i][1]
    x2, y2 = XY[j][0], XY[j][1]
    #(x1,y1)を左側にする
    if x1 > x2:
      x1, x2 =x2, x1
      y1, y2 =y2, y1
    if x1 - x2 <= y2-y1 <= x2-x1: ans += 1

print(ans)   

C - 1-SAT

C - 1-SATは,与えられた文字列の中に,すべての文字列について「abc」だけ,または「!abc」だけがあるような状況になっているときに限り「satisfiable」である.したがって,Pythonではsetを用いて「!」が混じっている文字列のセットと「!」が混じっていない文字列のセットを用意し,それらのセットを比べればよい.

N = int(input())
SE = set()
S = set()
for i in range(N):
  s = input()
  if '!' == s[0]:
    SE.add(s[1:])
  else:
    S.add(s)
for s in S:
  if s in SE:
    print(s)
    exit()

for s in SE:
  if s in S:
    print(s)
    exit()
    
print('satisfiable')